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

[kingwinner]

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

 

[Hurkyl]

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

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.

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

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

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

Because that's what the proof proved.

 

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

 

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

 

[CRGreathouse]

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

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

 

[Hurkyl]

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!

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)​

...

 

[kingwinner]

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)​

...

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.

 

[Hurkyl]

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

Why is this true?

 

[kingwinner]

Why is this true?

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).

 

[Hurkyl]

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

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)

 

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

 

[Hurkyl]

Chinese Remainder Theorem.

 

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

 

[Hurkyl]

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.

 

[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.

 

[CRGreathouse]

The CRT just says that the LHS has a solution.

No, it actually constructs a solution.

 

[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) ?

 

[Hurkyl]

The CRT just says that the LHS has a solution.

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

 

[JSuarez]

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

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.

 

[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.

 

[Hurkyl]

The problem isn't "what are the mod 15 roots of (x+1)^2"... the problem is "how to remove kingwinner's mental blocks that prevent him from understanding that y=0 (mod 3) and y=0 (mod 5) is logically equivalent to y=0 (mod 15)".

(And it's surprising that he has this block, because he seems to have no problem with "z=2 (mod 3) and z=4 (mod 5) is logically equivalent to z=14 (mod 15)")

 

[icystrike]

In actual fact, it is not necessary to execute Chinese remainder theorem.

Instead, for the x values that f(x)=0, will give us f(x)==0(mod 15).
By some corollary which states that if a is a solution of f(x)==0(mod n) and a==b(mod n) , then b is also a solution.

Therefore, f(-1)=0 , x=-1(mod 15) x=15k-1 such that k is some arbitrary integers.

 

[Hurkyl]

In actual fact, it is not necessary to execute Chinese remainder theorem.

Instead, for the x values that f(x)=0, will give us f(x)==0(mod 15).
By some corollary which states that if a is a solution of f(x)==0(mod n) and a==b(mod n) , then b is also a solution.

That's not where kingwinner was having trouble. I assume he has no problem with "If a==b (mod n) then f(a) == f(b) (mod n)". His problem was, as far as I can tell, the "If y == 0 (mod 3) and y == 0 (mod 5) then y == 0 (mod 15)" bit. (Possibly due to confusion when we substitute y --> f(x))

 

[srijithju]

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

why at all should mn divide f(x) ?


consider f(x) = 18 , thus possible values for m and n are 6 and 9 , but clearly 6 x 9 = 54 does not divide 18 , but had m and n been coprime then we would have a completely different answer.

 

[JSuarez]

why at all should mn divide f(x)

In the context of this thread, m and n are coprime (in fact, they are distinct primes).

 

[CRGreathouse]

In the context of this thread, m and n are coprime (in fact, they are distinct primes).

Yes. I was actually hoping that kingwinner would be able to figure out that restriction (and see that it was true in his case), thus my open phrasing.