<s>[INST] proving that $89 \mid 2^{44}-1$ i tried to prove that $2^{44} \equiv 1\pmod{89}$.
I noticed that by Fermat's little theorem $2^{88} \equiv 2^{44}\cdot 2^{44} \equiv 1\pmod{89}$
which means that $2^{44}$ is the inverse of itself $\rightarrow 2^{44} \equiv 1 \pmod{89}$ or $2^{44}\equiv 88 \pmod{89}$.
how can I rule out the second option?
 [/INST] $2^{44} - 1 = (2^{22})^2 - 1 = (2^{22}+1)(2^{22} - 1) = (2^{22}+1)(2^{11} + 1)(2^{11} - 1) = (2^{22}+1)(2^{11} + 1)\times 2047 = (2^{22}+1)(2^{11} + 1)\times 23 \times 89$
</s>