Results 1 to 8 of 8

Math Help - f(x)≡0 (mod 15) Find all roots mod 15

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

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

    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!


    [note: also under discussion in Math Links forum]
    Last edited by kingwinner; February 1st 2010 at 08:06 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by kingwinner View Post
    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!

    Much simpler, imo: 0=x^2+2x+1=(x+1)^2\Longrightarrow either there's some nilpotent element in \mathbb{Z}_{15} or else x+1=0\!\!\!\pmod {15}\Longleftrightarrow x=-1=14\!\!\!\pmod {15}.

    But we know that an element a\in\mathbb{Z}_n is nilpotent iff every prime that divides n divides a, so in \mathbb{Z}_{15} there are no nonzero nilpotent element and thus the only solution is 14\!\!\!\pmod {15}.

    I think this answers all your questions.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Thanks, but your method is beyond my background of number theory that I have so far. I haven't learnt nilpotent and Z15, etc. Your method is likely better, but for me it's best to use the topics that I've learnt up to this point.


    So could somebody kindly explain the solution provided in the example (most importantly, the answer to question 2)?

    Thank you!
    Last edited by kingwinner; February 2nd 2010 at 06:45 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    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 for any help!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by kingwinner View Post
    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 for any help!

    Because f(x)=x^2+2x+1=(x+1)^2\Longrightarrow f(14)=(14+1)^2= 15^2=0\!\!\!\pmod {15}

    Tonio
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by tonio View Post
    Because f(x)=x^2+2x+1=(x+1)^2\Longrightarrow f(14)=(14+1)^2= 15^2=0\!\!\!\pmod {15}

    Tonio
    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!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2

    Red face

    Quote Originally Posted by kingwinner View Post
    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?


    6= 0\!\!\!\pmod 6\,\,\,and\,\,\,6= 0\!\!\!\pmod 3 but 6\neq 0\!\!\!\pmod {6\cdot 3=18} , so the proposition isn't true in that generality.

    What is true is that a=0\!\!\!\pmod n\,,\,\,a=0\!\!\!\pmod n\,,\,\,and\,\,\,(n,m)=1\Longrightarrow a=0\!\!\!\pmod{mn} ,and in general, without requiring (n,m)=1 , we have a=0\!\!\!\pmod {\frac{mn}{gcd(m,n)}}

    Tonio

    Thanks for explaining!
    .
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    What if f(x)≡0 (mod m) AND 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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Find x such that x^2≡49 (mod pq)
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 9th 2011, 08:24 AM
  2. Replies: 0
    Last Post: June 28th 2010, 09:32 PM
  3. a^p≡1 (mod p^n) iff a≡1 (mod p^(n-1)), n≥2
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 8th 2010, 09:59 AM
  4. lcm of k,k+1,k+2 where k≡3(mod 4)
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 12th 2010, 02:46 PM
  5. Given 2 imaginary roots find other 2 roots
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: January 26th 2008, 10:24 PM

Search Tags


/mathhelpforum @mathhelpforum