<s>[INST] Show that $89|(2^{44})-1$ Show that $89|(2^{44})-1$
My teacher proved this problem using mod can someone explain the process step by step? Thank you so much!
 [/INST] With a bit of calculation. 
Need to prove $2^{44}\equiv 1\pmod{89}$.
$2^8=256=2\cdot 89+78=3\cdot 89-11$, so $2^8\equiv 78\equiv -11\pmod{89}$ $-$ it is a definition of $\pmod{}$ operation.
Then $2^3\cdot 2^8\equiv 8\cdot 2^8\equiv8\cdot 11\equiv-88 \equiv 1\pmod{89}$ $-$ because $1=1\cdot 89-88$.
So, you have $2^{11}\equiv 1\pmod{89}$ which means $2^{11}=k\cdot 89 +1$, where $k$ is an integer.
You can obtain from it that $(2^{11})^4=m\cdot 89 +1$, where $m$ will be another integer.
</s>