# f(x)≡0 (mod 15) Find all roots mod 15

• Feb 1st 2010, 06:43 PM
kingwinner
f(x)≡0 (mod 15) Find all roots mod 15
Example:
f(x) = x^2 + 2x +1
f(x)≡0 (mod 15)
Find ALL roots mod 15.

======================

Solution:
15=3x5
Consider f(x)≡0 (mod3).
mod 3: check 0,1,2. Only 2 solves it.

Consider f(x)≡0 (mod5).
mod 5: check 0,1,2,3,4. Only 4 solves it.

So x≡2(mod 3) and x≡4(mod 5). Looking at x≡4(mod 5), we take x=4,9,14 and check each of these in x≡2(mod 3). Only 14 works.
Thus, x≡2(mod 3) and x≡4(mod 5) => x≡14 (mod 15)
and the final answer is x≡14 (mod 15).
===============================

My questions:

1) The above says that x≡2(mod 3) and x≡4(mod 5) => x≡14 (mod 15). But to show that x≡14 (mod 15) is a solution to the system x≡2(mod 3),x≡4(mod 5), don't we have to show the CONVERSE? i.e. x≡14 (mod 15) => x≡2(mod 3) and x≡4(mod 5)? Do we need to show both directions(iff)?

2) So x≡14 (mod 15) solves the system f(x)≡0 (mod3),f(x)≡0 (mod5). Why does this imply that x≡14 (mod 15) also solves f(x)≡0 (mod 15)?

3) Why are there no other roots mod 15? i.e. why can we be sure that x≡14 (mod 15) is the only solution to f(x)≡0 (mod 15)?

Any help is much appreciated!

[note: also under discussion in Math Links forum]
• Feb 1st 2010, 07:09 PM
tonio
Quote:

Originally Posted by kingwinner
Example:
f(x) = x^2 + 2x +1
f(x)≡0 (mod 15)
Find ALL roots mod 15.
======================

Solution:
15=3x5
Consider f(x)≡0 (mod3).
mod 3: check 0,1,2. Only 2 solves it.

Consider f(x)≡0 (mod5).
mod 5: check 0,1,2,3,4. Only 4 solves it.

So x≡2(mod 3) and x≡4(mod 5). Looking at x≡4(mod 5), we take x=4,9,14 and check each of these in x≡2(mod 3). Only 14 works.
Thus, x≡2(mod 3) and x≡4(mod 5) => x≡14 (mod 15)
and the final answer is x≡14 (mod 15).
===============================

My questions:

1) The above says that x≡2(mod 3) and x≡4(mod 5) => x≡14 (mod 15). But to show that x≡14 (mod 15) is a solution to the system x≡2(mod 3),x≡4(mod 5), don't we have to show the CONVERSE? i.e. x≡14 (mod 15) => x≡2(mod 3) and x≡4(mod 5)? Do we need to show both directions(iff)?

2) So x≡14 (mod 15) solves the system f(x)≡0 (mod3),f(x)≡0 (mod5). Why does this imply that x≡14 (mod 15) also solves f(x)≡0 (mod 15)?

3) Why are there no other roots mod 15? i.e. why can we be sure that x≡14 (mod 15) is the only solution to f(x)≡0 (mod 15)?

Any help is much appreciated!

Much simpler, imo: $\displaystyle 0=x^2+2x+1=(x+1)^2\Longrightarrow$ either there's some nilpotent element in $\displaystyle \mathbb{Z}_{15}$ or else $\displaystyle x+1=0\!\!\!\pmod {15}\Longleftrightarrow x=-1=14\!\!\!\pmod {15}$.

But we know that an element $\displaystyle a\in\mathbb{Z}_n$ is nilpotent iff every prime that divides n divides a, so in $\displaystyle \mathbb{Z}_{15}$ there are no nonzero nilpotent element and thus the only solution is $\displaystyle 14\!\!\!\pmod {15}$.

Tonio
• Feb 1st 2010, 07:20 PM
kingwinner
Thanks, but your method is beyond my background of number theory that I have so far. I haven't learnt nilpotent and Z15, etc. Your method is likely better, but for me it's best to use the topics that I've learnt up to this point.

So could somebody kindly explain the solution provided in the example (most importantly, the answer to question 2)?

Thank you!
• Feb 2nd 2010, 05:44 PM
kingwinner
I believe questions of the type "Find ALL roots mod 15" are about "if and only if" statements. We can't just show one direction.
I think for the above solution, they actually meant iff for the last step, i.e. x≡2(mod 3) and x≡4(mod 5) <=> x≡14 (mod 15), because they showed that x≡14 (mod 15) works, i.e. is a solution, and also nothing else works (4 and 9 does not work), i.e. it's the ONLY solution, so we have iff.

So I think we can say that:
f(x)≡0 (mod3) and f(x)≡0 (mod5)
<=> x≡2(mod 3) and x≡4(mod 5)
<=> x≡14 (mod 15)

So x≡14 (mod 15) is the solution to f(x)≡0 (mod3),f(x)≡0 (mod5).
But why is x≡14 (mod 15) the solution to f(x)≡0 (mod 15)? I still don't understand this...

Thanks for any help!
• Feb 2nd 2010, 06:41 PM
tonio
Quote:

Originally Posted by kingwinner
I believe questions of the type "Find ALL roots mod 15" are about "if and only if" statements. We can't just show one direction.
I think for the above solution, they actually meant iff for the last step, i.e. x≡2(mod 3) and x≡4(mod 5) <=> x≡14 (mod 15), because they showed that x≡14 (mod 15) works, i.e. is a solution, and also nothing else works (4 and 9 does not work), i.e. it's the ONLY solution, so we have iff.

So I think we can say that:
f(x)≡0 (mod3) and f(x)≡0 (mod5)
<=> x≡2(mod 3) and x≡4(mod 5)
<=> x≡14 (mod 15)

So x≡14 (mod 15) is the solution to f(x)≡0 (mod3),f(x)≡0 (mod5).
But why is x≡14 (mod 15) the solution to f(x)≡0 (mod 15)? I still don't understand this...

Thanks for any help!

Because $\displaystyle f(x)=x^2+2x+1=(x+1)^2\Longrightarrow f(14)=(14+1)^2=$ $\displaystyle 15^2=0\!\!\!\pmod {15}$

Tonio
• Feb 2nd 2010, 09:11 PM
kingwinner
Quote:

Originally Posted by tonio
Because $\displaystyle f(x)=x^2+2x+1=(x+1)^2\Longrightarrow f(14)=(14+1)^2=$ $\displaystyle 15^2=0\!\!\!\pmod {15}$

Tonio

Is it true in general that f(x)≡0 (mod 3) AND f(x)≡0 (mod 5) IMPLIES f(x)≡0 (mod 15)?

Is it true in general that f(x)≡0 (mod m) AND f(x)≡0 (mod n) IMPLIES f(x)≡0 (mod mn)? Why or why not?

Thanks for explaining!
• Feb 3rd 2010, 01:31 AM
tonio
Quote:

Originally Posted by kingwinner
Is it true in general that f(x)≡0 (mod 3) AND f(x)≡0 (mod 5) IMPLIES f(x)≡0 (mod 15)?

Is it true in general that f(x)≡0 (mod m) AND f(x)≡0 (mod n) IMPLIES f(x)≡0 (mod mn)? Why or why not?

$\displaystyle 6= 0\!\!\!\pmod 6\,\,\,and\,\,\,6= 0\!\!\!\pmod 3$ but $\displaystyle 6\neq 0\!\!\!\pmod {6\cdot 3=18}$ , so the proposition isn't true in that generality.

What is true is that $\displaystyle a=0\!\!\!\pmod n\,,\,\,a=0\!\!\!\pmod n\,,\,\,and\,\,\,(n,m)=1\Longrightarrow a=0\!\!\!\pmod{mn}$ ,and in general, without requiring $\displaystyle (n,m)=1$ , we have $\displaystyle a=0\!\!\!\pmod {\frac{mn}{gcd(m,n)}}$

Tonio

Thanks for explaining!

.
• Feb 3rd 2010, 07:16 PM
kingwinner
What if f(x)≡0 (mod m) AND f(x)≡0 (mod n) AND f(x)≡0 (mod q)?
Under what conditions will this guarantee that f(x)≡0 (mod mnq)? Do we need (m,n)=(m,q)=(n,q)=1? or just (m,n,q)=1? and why?

thanks.