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!