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

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.

Tags:

Elementary Number Theory

Related

If a polynomial ring is a free module over some subring, is that subring itself a polynomial ring? Closed form for the area of a convex cyclic n-gon, given the set of edge lengths Giving a specific example of a positive sequence increasing to 1 and with its partial products having a positive limit Limits of integrals If $f$ is entire and $\lim_\limits{z\to\infty} \frac{f(z)}{z} = 0$ show that $f$ is constant What is the optimal path between $2$ fixed points around an invisible obstructing wall? Why doesn't this definition of natural numbers hold up in axiomatic set theory? Hypersurfaces have no embedded points (Vakil 5.5.I) The Marginal Distribution of a Multinomial When are differentials actually useful? Real analysis for a non-mathematician. How do I show that $\frac {a^2}b + \frac {b^2}c + \frac {c^2}d + \frac {d^2}a \ge 4$ for $a^2 + b^2 + c^2 + d^2 = 4$?

Recent Posts