Modular Root

n 3 3 n + 7 0 ( m o d n 5 ) 2 n 2 n + 2 0 ( m o d n + 6 ) n^3 - 3n +7 \equiv 0 \pmod{n-5} \\ 2n^2 - n +2 \equiv 0 \pmod{n+6}

What integer n 5 n \geq 5 satisfies the above system of congruence equations?


The answer is 14.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Since x a ( m o d x a ) x \equiv a \pmod{x-a} for any integer a a , f ( x ) f ( a ) ( m o d x a ) f(x) \equiv f(a) \pmod{x-a} .

x 3 3 x + 7 5 3 3 5 + 7 117 0 ( m o d x 5 ) x^3 - 3x +7 \equiv 5^3 - 3\cdot 5 +7 \equiv 117 \equiv 0 \pmod{x-5}

2 x 2 x + 2 2 ( 6 ) 2 ( 6 ) + 2 80 0 ( m o d x + 6 ) 2x^2 - x +2 \equiv 2(-6)^2 -(-6) + 2 \equiv 80 \equiv 0 \pmod{x+6}

From the first equivalence, 117 117 has factors of { 1 , 3 , 9 , 13 , 39 , 117 } \left\{{1, 3, 9, 13, 39, 117}\right\} , and so x { 6 , 8 , 14 , 18 , 44 , 122 } = A x \in \left\{{6, 8, 14, 18, 44, 122}\right\} = A

Then for the latter, 80 80 has { 1 , 2 , 4 , 5 , 8 , 10 , 16 , 20 , 40 , 80 } \left\{{1, 2, 4, 5, 8, 10, 16, 20, 40, 80}\right\} , and so x { 2 , 4 , 10 , 14 , 34 , 74 } = B x \in \left\{{2, 4, 10, 14, 34, 74}\right\} = B .

A B = { 14 } A\cap B = \left\{{14}\right\} .

Thus, x = 14 x = \boxed{14} .

Checking answers:

1 4 3 3 14 + 7 5 3 3 5 + 7 117 0 ( m o d 9 ) 14^3 - 3\cdot 14 +7 \equiv 5^3 - 3\cdot 5 +7 \equiv 117 \equiv 0 \pmod{9}

2 ( 1 4 2 ) 14 + 2 392 12 380 0 ( m o d 20 ) 2(14^2) - 14 +2 \equiv 392 -12 \equiv 380 \equiv 0 \pmod{20}

For clarity, instead of saying "we can simply substitute the value within each polynomial", you should instead explain that f ( x ) f ( a ) ( m o d x a ) f(x) \equiv f(a) \pmod{ x - a } .

Chung Kevin - 4 years, 2 months ago

Log in to reply

Oh, OK. Thanks.

Worranat Pakornrat - 4 years, 2 months ago

Yes, exactly. As far as I can understand, it is definitely true only when f(x) is a polynomial.

A Former Brilliant Member - 3 years, 4 months ago

x = 2 x=2 also satisfies the equation

Kushal Bose - 4 years, 2 months ago

Log in to reply

Is mod -3 usable though? I thought modulus should have positive integer.

Worranat Pakornrat - 4 years, 2 months ago

Log in to reply

Okk thanks

Kushal Bose - 4 years, 2 months ago

Anyway, I've already edited it.

Worranat Pakornrat - 4 years, 2 months ago

x>5 or x=5

Filip Jerleković - 1 year, 10 months ago
Abhishek Yadav
Jun 20, 2019

Since, n 3 3 n + 7 0 n^3 - 3n + 7 \equiv 0 (mod n 5 n -5 ) n 5 n 3 3 n + 7 \implies n - 5 | n^3 - 3n + 7 \\ Similarly, 2 n 2 n + 2 0 2n^2 - n + 2 \equiv 0 (mod n + 6 n+6 ) n + 6 2 n 2 n + 2 \implies n + 6 |2n^2 - n + 2 \\ Factoring n 3 3 n + 7 n^3 - 3n + 7 in terms of n 5 , n - 5, \\ n 3 3 n + 7 = n 3 5 n 2 + 5 n 2 25 n + 25 n 3 n + 7 n^3 - 3n + 7 = n^3 - 5n^2 + 5n^2 - 25n + 25n - 3n + 7 \\ = n 2 ( n 5 ) + 5 n ( n 5 ) + 22 n + 7 n 5 22 n + 7 = n^2(n - 5) + 5n(n - 5) + 22n + 7 \implies n - 5|22n+7 \\ Similarly, Factoring 2 n 2 n + 2 2n^2 - n + 2 in terms of n + 6 n + 6\\ 2 n 2 n + 2 = 2 n 2 + 12 n 12 n n 78 + 78 + 2 2n^2 - n + 2 = 2n^2 + 12n - 12n -n - 78 + 78 + 2 \\ = 2 n ( n + 6 ) 13 ( n + 6 ) + 80 n + 6 80 = 2n(n + 6) - 13(n + 6) + 80 \implies n + 6| 80 \\ Possible divisors of 80 are - 2 , 4 , 5 , 8 , 10 , 16 , 20 , 40 , 80 , 2, 4, 5, 8, 10, 16, 20, 40, 80,\\ From the given condition n 5 , n = 14 n \geq 5, n = 14 , satisfies both the conditions.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...