Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Feb 1, 2010 #1
    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. jcsd
  3. Feb 1, 2010 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  4. Feb 1, 2010 #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!
     
  5. Feb 3, 2010 #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!
     
  6. Feb 3, 2010 #5

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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)
    ?
     
  7. Feb 3, 2010 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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)​
    ....
     
  8. Feb 3, 2010 #7
    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.
     
  9. Feb 3, 2010 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Why is this true?
     
  10. Feb 4, 2010 #9
    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).
     
  11. Feb 4, 2010 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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)
     
  12. Feb 7, 2010 #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!
     
  13. Feb 7, 2010 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Chinese Remainder Theorem.
     
  14. Feb 7, 2010 #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!
     
  15. Feb 7, 2010 #14

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  16. Feb 7, 2010 #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.
     
  17. Feb 7, 2010 #16

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    No, it actually constructs a solution.
     
  18. Feb 7, 2010 #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) ?
     
  19. Feb 7, 2010 #18

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  20. Feb 10, 2010 #19
    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.
     
  21. Feb 10, 2010 #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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: F(x)≡0 (mod 15) Find all roots mod 15
  1. X^2 + 1 = 0 (mod 5^3). (Replies: 2)

  2. Ab ≡ 0 (mod N) (Replies: 1)

Loading...