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

  • Thread starter kingwinner
  • Start date
  • Tags
    Roots
That is, if x and x' are two solutions then x≡x' (mod N).In our case, n1=3, n2=5, n=15, which are pairwise coprime, so the CRT applies.So if we solve for x, we get:x≡a1 (mod n1) => x≡0 (mod 3)x≡a2 (mod n2) => x≡0 (mod 5)And since 3 and 5 are coprime, all solutions x to this system are congruent modulo 15, which is what we wanted to show. So x≡0 (mod 3) and x
  • #1
kingwinner
1,270
0
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!
 
Physics news on Phys.org
  • #2
kingwinner said:
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.
 
  • #3
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
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
kingwinner said:
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)
?
 
  • #6
kingwinner said:
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)​
...
 
  • #7
Hurkyl said:
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.
 
  • #8
kingwinner said:
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?
 
  • #9
Hurkyl said:
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).
 
  • #10
kingwinner said:
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)
 
  • #11
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
Chinese Remainder Theorem.
 
  • #13
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
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
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
kingwinner said:
The CRT just says that the LHS has a solution.

No, it actually constructs a solution.
 
  • #17
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
kingwinner said:
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
 
  • #19
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.
 
  • #20
Actually, in this particular case, the CRT complicates things; notice that:

[tex]
x^{2}+2x+1=\left(x+1\right)^2
[/tex]

So the congruence may be written:

[tex]
\left(x+1\right)^{2}\equiv 0 \left(\rm{mod} 15\right)
[/tex]

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

[tex]
\left(x+1\right)\equiv 0 \left(\rm{mod} 15\right)
[/tex]

So, the only solution mod 15 is 14.
 
  • #21
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)")
 
  • #22
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.
 
  • #23
icystrike said:
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))
 
  • #24
CRGreathouse said:
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.
 
  • #25
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).
 
  • #26
JSuarez said:
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.
 

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

What does the notation "≡0 (mod 15)" mean?

The notation "≡0 (mod 15)" means that the expression on the left side is congruent to 0 modulo 15. In other words, the expression is divisible by 15 with no remainder.

What is F(x) in this equation?

In this equation, F(x) represents the function or polynomial that we are trying to find the roots of. It is a common notation used in mathematics to represent a function.

How do you find the roots of this equation mod 15?

To find the roots of this equation mod 15, we can use the method of modular arithmetic. This involves finding the values of x that satisfy the equation when substituted into the function, and then reducing those values modulo 15 to get the roots.

Can there be more than one root mod 15?

Yes, there can be more than one root mod 15 for this equation. In fact, there can be infinitely many roots mod 15, as there are infinitely many integers that are congruent to 0 modulo 15.

Is there a general formula for finding all roots mod 15?

Yes, there is a general formula for finding all roots mod 15. It involves using modular arithmetic and factoring the polynomial into linear factors. However, the specific steps and calculations may vary depending on the complexity of the polynomial.

Similar threads

Replies
1
Views
1K
Replies
3
Views
2K
Replies
7
Views
2K
Replies
6
Views
7K
Replies
3
Views
1K
Replies
3
Views
1K
Back
Top