# Prove that $89|2^{44}-1$ [duplicate]

Is there any easier (less no. of steps or calculations) proof for this using congruences: $89|2^{44}-1$. My proof: $$2^6\equiv-25\mod89$$ $$2^5\equiv32\mod89$$ Now square both equations: $$2^{12}\equiv625\equiv2\mod89$$ $$2^{10}\equiv-44\mod89$$ Now multiplying: $$2^{22}\equiv-88\equiv1\mod89$$ Since $2^{44}-1=(2^{22}+1)(2^{22}-1)$, it is proved.

• You want a solution that takes less than 3-5 steps? Exactly which calculations are costly for you? The modulo or the raising to a power? Jan 18, 2015 at 15:52
• @Axoren: the calculations like finding the remainder after squaring both equations. Jan 18, 2015 at 15:54
• If one uses some theory, one does not need to calculate at all. Note that $2$ is a quadratic residue of $89$. Now use Fermat's Theorem. Jan 18, 2015 at 15:59
• How do we note $2$ is a quadratic residue of 89? Although that does finish quite nicely. Jan 18, 2015 at 16:06
• Standard result, $2$ is a QR of primes of the form $8k\pm 1$, and a NR for primes of the form $8k\pm 3$. Jan 18, 2015 at 16:53

Hint: $2^{44}-1=(2^{22}-1)(2^{22}+1)=(2^{11}-1)(2^{11}+1)(2^{22}+1)=2047\cdot2049\cdot(2^{22}+1)=$ $=(23\cdot89)\cdot2049\cdot(2^{22}+1).\quad$ Of course, this assumes a certain familiarity with the powers of $2$.
Essentially all you would like to know is if $2$ is a primitive root $\bmod 89$. We know that primitive roots exist because $89$ is prime. This is generally hard to do. Here is a question discussing how to find primitive roots.
In this case it turns out $2^{11}$ is already congruent to $1\bmod 89$ so $2^{44}$ will also..
• $\;2^{11}=1\pmod{89}\implies 2\;$ is not a a primitive root $\;\pmod{89}\;$ , of course. Jan 18, 2015 at 16:58
• I like the intuitiveness of this answer. Given $2^{11}\equiv1\mod89$ and $11|44$, then $2^{44}\equiv1\mod89$, therefore of course $2^{44}-1\equiv0\mod89$. I'm left curious how @Jorge got to $2^{11}\equiv1\mod89$ in the first place, though.