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!
 A: $$\begin{align}a^2-b^2=(a-b)(a+b)\quad=>\quad2^{44}-1&=(2^{22}-1)(2^{22}+1)=\\&=\underbrace{(2^{11}-1)}_{2047{\large=}{\color{red}{89}}\cdot23}(2^{11}+1)(2^{22}+1).\end{align}$$
A: One way is to note that because $89$ is a prime of the form $8k+1$, it follows that $2$ is a quadratic residue of $p$. Thus $x^2\equiv 2\pmod{89}$ for some $x$. It follows that
$$2^{44}\equiv (x^2)^{44}\equiv x^{88}\pmod{89}.$$ 
But $x^{88}\equiv 1\pmod{89}$ by Fermat's Theorem.
A: We're interested in the remainder of $2^n$ upon division by $89$ for increasing values of $n$.  Here are the remainders for $n=1,2,\ldots,11$:
$$2,4,8,16,32,64,39,78,67,45,1$$
Notice that $2^{11}\equiv 1\pmod{89}$.  So that $2^{44}=(2^{11})^4\equiv\ldots$ (see if you can finish the argument).
A: $2^{44} \mod{89} = 2^{32} \times 2^8 \times 2^4 \mod{89}$. Starting with $2^4 = 16 \mod{89}$, and doubling and taking mod, you get $16 \times 78 \times 45  = 1 \mod 89$ .Therefore $89$ divides $2^{44} - 1$.
A: 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.
