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

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?

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.

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

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.

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$$.