Results 1 to 7 of 7

Thread: 32^n = 167x + 2

  1. #1
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    69

    32^n = 167x + 2

    Find the smallest integer n such that this statement is true for some integer x.

    This is what I have so far.

    32^n = 167x + 2

    2^(5n) = 167x + 2

    2^(5n) = 2 mod 167

    Euler's Theorem: 32^(phi(167)) = 1 mod 167

    32^166 = 1 mod 167

    2^830 = 1 mod 167

    2^831 = 2 mod 167

    So, 2^(5n) = 2^831 mod 167.

    How can I solve this modular equation for n?

    This is from a math competition in 2008.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by elemental View Post
    Find the smallest integer n such that this statement is true for some integer x.

    This is what I have so far.

    32^n = 167x + 2

    2^(5n) = 167x + 2

    2^(5n) = 2 mod 167

    Euler's Theorem: 32^(phi(167)) = 1 mod 167

    32^166 = 1 mod 167

    2^830 = 1 mod 167

    2^831 = 2 mod 167

    So, 2^(5n) = 2^831 mod 167.

    How can I solve this modular equation for n?

    This is from a math competition in 2008.
    $\displaystyle \displaystyle 2^{5n}\equiv 2^{831} \bmod{167}\implies 5n \equiv 831 \bmod{\varphi(167)} $
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    69
    What theorem is that?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by elemental View Post
    What theorem is that?
    I don't know if this has a specific name or anything, but I do believe an easy proof would be a proof by contradiction.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    69
    Even if I do that, that yields n = 133.

    However, the answer in my solution guide is n = 50.
    32^50 = 2 mod 167.

    Why does my method fail?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by chiph588@ View Post
    $\displaystyle \displaystyle 2^{5n}\equiv 2^{831} \bmod{167}\implies 5n \equiv 831 \bmod{\varphi(167)} $
    That's actually not accurate... The congruence is rather $\displaystyle 5n\equiv831\pmod{83}$.

    This is due to the following theorem: Suppose $\displaystyle a $ has order $\displaystyle k $ modulo $\displaystyle m $. Then $\displaystyle a^i\equiv a^j\pmod m$ if and only if $\displaystyle i\equiv j\pmod k$.

    The order is found among the divisors of $\displaystyle \phi(167)$, those are $\displaystyle 1, 2, 83,$ and $\displaystyle 166 $. In the problem we can find that $\displaystyle 2^{83}\equiv1\pmod {167}$, so the order is $\displaystyle 83 $. (1 or 2 clearly cannot be the orders)

    The congruence is reduced to $\displaystyle 5n\equiv1\pmod {83}$... Solving this congruence gives $\displaystyle n\equiv{50}\pmod {83}$.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by melese View Post
    That's actually not accurate... The congruence is rather $\displaystyle 5n\equiv831\pmod{83}$.

    This is due to the following theorem: Suppose $\displaystyle a $ has order $\displaystyle k $ modulo $\displaystyle m $. Then $\displaystyle a^i\equiv a^j\pmod m$ if and only if $\displaystyle i\equiv j\pmod k$.

    The order is found among the divisors of $\displaystyle \phi(167)$, those are $\displaystyle 1, 2, 83,$ and $\displaystyle 166 $. In the problem we can find that $\displaystyle 2^{83}\equiv1\pmod {167}$, so the order is $\displaystyle 83 $. (1 or 2 clearly cannot be the orders)

    The congruence is reduced to $\displaystyle 5n\equiv1\pmod {83}$... Solving this congruence gives $\displaystyle n\equiv{50}\pmod {83}$.
    I made a calculation error, I thought $\displaystyle 2 $ was a primitive root modulo $\displaystyle 167 $...
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum