Prove that $89|2^{44}-1$

Question

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.

Answer 1

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

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