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

1. Feb 1, 2010

### kingwinner

Example:
f(x) = x2 + 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!

2. Feb 1, 2010

### Hurkyl

Staff Emeritus
All you need to do is to show that f(14)≡0 (mod 15).

Of course, by the CRT, you can do that by showing that f(14)≡0 (mod 3) and f(14)≡0 (mod 5).

Now, your right, the proof failed to explicitly argue that 14 is a root -- all it proved was "if x is a root mod 15, then x≡14 (mod 15)". Depending on the setting, it probably should have said something about verifying it, or mentioned the appropriate steps were if-and-only-if, or whatnot.

Well, how do mod 3 and mod 5 arithmetic relate to mod 15 arithmetic?

Because that's what the proof proved.

3. Feb 1, 2010

### 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!

4. Feb 3, 2010

### 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?

Thanks for explaining!

5. Feb 3, 2010

### CRGreathouse

foo ≡ 0 (mod m) is, by definition, m | foo. So if
m | f(x)
and
n | f(x)
can you say that
mn | f(x)
?

6. Feb 3, 2010

### Hurkyl

Staff Emeritus
I don't understand where your confusion is coming from, because you seem to have no problem with the statement
x≡2(mod 3) and x≡4(mod 5) <=> x≡14 (mod 15)​
....

7. Feb 3, 2010

### kingwinner

Right, I have no problem with the following:
f(x)≡0 (mod 3) and f(x)≡0 (mod 5)
<=> x≡2(mod 3) and x≡4(mod 5)
<=> x≡14 (mod 15)

But I don't understand why f(x)≡0 (mod 3) and f(x)≡0 (mod 5) <=> f(x)≡0 (mod 15). In other words, why can we solve f(x)≡0 (mod 15) by looking at mod 3 and mod 5? I don't understand the logic/reasoning behind this step.

thanks.

8. Feb 3, 2010

### Hurkyl

Staff Emeritus
Why is this true?

9. Feb 4, 2010

### kingwinner

x≡2(mod 3) and x≡4(mod 5)
Looking at x≡4(mod 5), we take x=4,9(=4+5),14(=4+5+5) and check each of these in x≡2(mod 3). Only 14 works, so only 14 satisfies both.
Thus, x≡2(mod 3) and x≡4(mod 5) <=> x≡14 (mod 15)

But I don't understand why f(x)≡0 (mod 3) and f(x)≡0 (mod 5) <=> f(x)≡0 (mod 15).

10. Feb 4, 2010

### Hurkyl

Staff Emeritus
Why can't you use the exact same method to answer this that you used to answer my question?

(P.S. in my opinion, Chinese Remainder Theorem is an easier answer to my question)

11. Feb 7, 2010

### kingwinner

Actually I figured out a way to understand this...
f(x)≡0 (mod m), f(x)≡0 (mod n), AND (m,n)=1 => f(x)≡0 (mod mn)

More generally, what if f(x)≡0 (mod m), 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!

12. Feb 7, 2010

### Hurkyl

Staff Emeritus
Chinese Remainder Theorem.

13. Feb 7, 2010

### kingwinner

How exactly does the CRT answers both directions of the question: f(x)≡0 (mod 3) and f(x)≡0 (mod 5) <=> f(x)≡0 (mod 15)? I can't figure it out...

CRT:
Suppose n1, n2, …, nk are positive integers which are pairwise coprime. Then, for any given integers a1,a2, …, ak, there exists an integer x solving the system of simultaneous congruences
x≡a1 (mod n1)
x≡a2 (mod n2)
...
x≡ak (mod nk)

Furthermore, all solutions x to this system are congruent modulo the product N = n1 n2…nk.

Thanks!

14. Feb 7, 2010

### Hurkyl

Staff Emeritus
I assumed one direction (<=) was obvious, and you were just wondering about the other one (=>), which you can use CRT for. Actually, the CRT in this case is an if-and-only-if, but to use that, I think you have to already know (<=) anyways.

15. Feb 7, 2010

### kingwinner

Yes, the <= direction is obvious, and I'm wondering how to get the => direction by the CRT.

Why does the CRT give that
f(x)≡0 (mod 3) and f(x)≡0 (mod 5) => f(x)≡0 (mod 15)?

The CRT just says that the LHS has a solution.

thanks.

16. Feb 7, 2010

### CRGreathouse

No, it actually constructs a solution.

17. Feb 7, 2010

### kingwinner

But looking at the statement of the CRT, it is still not clear to me why
f(x)≡0 (mod 3) and f(x)≡0 (mod 5) => f(x)≡0 (mod 15) ?

18. Feb 7, 2010

### Hurkyl

Staff Emeritus
It doesn't just say that there exists an a with f(x)=a (mod 15) -- it says that a is unique.

This was double-posted. I deleted the one that appeared before kingwinner's previous statement

19. Feb 10, 2010

### JSuarez

Because the CRT also states that the solution of the system is unique (this was already said by Hurkyl) mod M, where M is the product of the individual moduli, in this case 3 and 5.

20. Feb 10, 2010

### JSuarez

Actually, in this particular case, the CRT complicates things; notice that:

$$x^{2}+2x+1=\left(x+1\right)^2$$

So the congruence may be written:

$$\left(x+1\right)^{2}\equiv 0 \left(\rm{mod} 15\right)$$

But 15 divides $\left(x+1\right)^2$ iff it also divides $x+1$ (one of the directions is obvious, the other uses the fact that 15 is squarefree) therefore, the solutions are given by:

$$\left(x+1\right)\equiv 0 \left(\rm{mod} 15\right)$$

So, the only solution mod 15 is 14.