# 32^n = 167x + 2

• Nov 18th 2010, 05:42 PM
elemental
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.
• Nov 19th 2010, 10:11 AM
chiph588@
Quote:

Originally Posted by elemental
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)}$
• Nov 19th 2010, 10:20 AM
elemental
What theorem is that?
• Nov 19th 2010, 10:29 AM
chiph588@
Quote:

Originally Posted by elemental
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.
• Nov 19th 2010, 10:30 AM
elemental
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?
• Nov 19th 2010, 10:47 AM
melese
Quote:

Originally Posted by chiph588@
$\displaystyle \displaystyle 2^{5n}\equiv 2^{831} \bmod{167}\implies 5n \equiv 831 \bmod{\varphi(167)}$

That's actually not accurate...(Doh) 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}$.
• Nov 19th 2010, 11:02 AM
chiph588@
Quote:

Originally Posted by melese
That's actually not accurate...(Doh) 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$...