5
$\begingroup$

Show that $233$ divides $2^{29} - 1$.

At first I've tried to find some trivial congruence to brute force my way to the 29th exponent, however it seems that only $2^{29} \equiv 1 \pmod{233} $.

\begin{align} 2^8 &\equiv 23 &\pmod{233}\\ 2^{12} &\equiv 135 &\pmod{233}\\ 2^{16} &\equiv 63 &\pmod{233}\\ 2^{24} &\equiv 51 &\pmod{233}\\ 2^{29} &\equiv 1 &\pmod{233} \end{align}

Is there some clever congruence to make this brute force less... brute or is little Fermat a must in this situation?

$\endgroup$
4
$\begingroup$

Exponentiation by squaring is the usual technique. This isn't so different from what you did. \begin{align*} 2^1 &= 2 \pmod{233} \\ 2^2 &= 4 \pmod{233} \\ 2^4 &= 16 \pmod{233} \\ 2^8 &= 23 \pmod{233} \\ 2^{16} &= 23^2 \cong 23(10 + 10 + 3) \cong -3 -3 +69 \cong 63 \pmod{233} \\ \text{and } 29 &= 16+8+4+1 , \text{ so} \\ 2^{29} &\cong 63 \cdot 23 \cdot 16 \cdot 2 \cong 46\,368 \cong 1 \pmod{233} \\ \end{align*}

Generally, there is no shortcut known for determining the order of an element modulo a prime. (Here, we showed that the order of $2$ mod $233$ divides $29$. Since $29$ is prime, and the order of $2$ is not $1$, its order is $29$.)

Addition-chain exponentiation is a method for shortcutting some of the above. However, finding minimal addition chains is an NP-complete problem, so maybe this isn't the best choice for hand calculation.

$\endgroup$
  • 1
    $\begingroup$ $2^{16}\equiv 63\implies 2^{32}$ $\equiv 3969 \equiv$ $8=2^3 \implies 2^{29}\equiv 1,$ because $\gcd (2,233)=1.$ $\endgroup$ – DanielWainfleet Apr 17 '16 at 6:48
  • $\begingroup$ @user254665 : And that would use an addition-subtraction chain, also described at the addition-chain page. $\endgroup$ – Eric Towers Apr 17 '16 at 7:24
1
$\begingroup$

Fermat's Little Theorem is pretty useful and probably the easiest way to solve this. Notice that $233$ is prime and that $29\mid 232$. Particularly, $\frac{232}{29}=8$ So, by Fermat's Little Theorem,

$$2^{232}\equiv 1\pmod{233}$$

and $232=29\cdot 8$ should get you to the solution.

$\endgroup$
1
$\begingroup$

As has already been pointed out, since $233$ is prime, we can by Fermat's Theorem infer that

$$ 2^{232} = 2^{(29)(8)} \equiv 1 \pmod{233}.$$

However, to get to the desired solution, observe that $ (2^{29})^{8} \equiv 1 \pmod{233}$.

This means that either $2^{29} - 1 \equiv 0 \pmod{233} $ or $ 2^{29} + 1 \equiv 0 \pmod{233}$.

Now, as $2^{29}$ is not a very large number, we can verify by calculator that $233 | 2^{29} - 1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.