Results 1 to 10 of 10
Like Tree2Thanks
  • 1 Post By johng
  • 1 Post By SlipEternal

Math Help - congruence equation

  1. #1
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    109
    Thanks
    14

    congruence equation

    Hi'
    I need help in solving the equation:

    x^25=2 (mod 133)

    Thank's in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    639
    Thanks
    257

    Re: congruence equation

    Hi,
    Here's some help. If you still have problems, post again.

    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    109
    Thanks
    14

    Re: congruence equation

    If we tart with the second equation we get x=2(mod7) and we lose the other solutions.where is my mistake?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    109
    Thanks
    14

    Re: congruence equation

    How do the solutions of the separate equations provide solutions for the original one?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    109
    Thanks
    14

    Re: congruence equation

    the solutions 14 and 3 of the second equation are incorrect.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,879
    Thanks
    742

    Re: congruence equation

    Suppose x \equiv 3 \pmod{19} and x \equiv 2 \pmod{7}. Then, by the Chinese Remainder Theorem, x \equiv 79 \pmod{133}. Indeed, 79^{25} \equiv 2 \pmod{133}. This is a solution (so the solutions 14 and 3 of the second equation are not incorrect... at least 3 is correct).

    Suppose x \equiv 2 \pmod{19}, x\equiv 2 \pmod{7}. Then, x \equiv 2\pmod{133}, and 2^{25} \equiv 128 \pmod{133}, so this is not a solution.

    Suppose x \equiv 14 \pmod{19}, x\equiv 2\pmod{7}. Then, x \equiv 128 \pmod{133}, and 128^{25} \equiv 79 \pmod{133}, so again, this is not a solution.

    Hence, the only solution is x \equiv 79 \pmod{133}.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    109
    Thanks
    14

    Re: congruence equation

    How do you compute 79 and 128 from the chineese remainder theorem?sorry'i am not quite famikiar with this subject.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,879
    Thanks
    742

    Re: congruence equation

    Use an online Chinese Remainder Theorem Calculator? You need familiarity with the subject to be able to calculate solutions otherwise.

    Here is a link to a calculator that will do it for you: Chinese Remainder Theorem Calculator

    How it works: Suppose x \equiv 3 \pmod{19}, x \equiv 2 \pmod{7}

    Then, we know x = 3+19a for some integer a. So, the possible equivalence classes of x \pmod{133} are 3, 22, 41, 60, 79, 98, 117. We check each \pmod{7} and discover that only 79 \equiv 2 \pmod{7}.

    Do the same for x \equiv 2 \pmod{19} or x \equiv 14 \pmod{19}.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    109
    Thanks
    14

    Re: congruence equation

    so x=79mod(133) is the unique solution of the two equation.theoretically'why should it be the solution of the original equation?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    109
    Thanks
    14

    Re: congruence equation

    It is obvious in second tought.
    Thank's
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 18th 2010, 06:26 AM
  2. congruence equation
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: September 2nd 2010, 06:20 AM
  3. 2^x in a congruence equation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 15th 2009, 05:08 PM
  4. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 28th 2008, 05:54 PM
  5. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 15th 2006, 07:10 PM

Search Tags


/mathhelpforum @mathhelpforum