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

Thread: congruence equation

  1. #1
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    198
    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
    MHF Contributor
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    1,141
    Thanks
    475

    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
    198
    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
    198
    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
    198
    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
    3,339
    Thanks
    1300

    Re: congruence equation

    Suppose $\displaystyle x \equiv 3 \pmod{19}$ and $\displaystyle x \equiv 2 \pmod{7}$. Then, by the Chinese Remainder Theorem, $\displaystyle x \equiv 79 \pmod{133}$. Indeed, $\displaystyle 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 $\displaystyle x \equiv 2 \pmod{19}, x\equiv 2 \pmod{7}$. Then, $\displaystyle x \equiv 2\pmod{133}$, and $\displaystyle 2^{25} \equiv 128 \pmod{133}$, so this is not a solution.

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

    Hence, the only solution is $\displaystyle 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
    198
    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
    3,339
    Thanks
    1300

    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 $\displaystyle x \equiv 3 \pmod{19}, x \equiv 2 \pmod{7}$

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

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

  9. #9
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    198
    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
    198
    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: Oct 18th 2010, 06:26 AM
  2. congruence equation
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: Sep 2nd 2010, 06:20 AM
  3. 2^x in a congruence equation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 15th 2009, 05:08 PM
  4. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 28th 2008, 05:54 PM
  5. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 15th 2006, 07:10 PM

Search Tags


/mathhelpforum @mathhelpforum