Divisibility by large powers Show that $2^{111} + 1$ divides $2^{555} + 1$ but does not divide $2^{444} + 1$.
My try:
$(2^{111}+1)^5 = 2^{555}+5*2^{444}+10*2^{333}+10*2^{222}+5*2^{111}+1$
$2^{555} + 1$ = $(2^{111}+1)^5$ - $(5*2^{444}+10*2^{333}+10*2^{222}+5*2^{111})$
= $(2^{111}+1)^5$ - ($5*2^{333}(2^{111}+1)+5*2^{222}(2^{111}+1)+5*2^{111}(2^{111}+1))$
Each term is divisible by $(2^{111} + 1)$ and hence divisible by $2^{111} + 1$.
Such a nice distribution is not possible for $2^{444} + 1$
I could answer the first part and the second part of indivisibility is not as clean as I would like.  Could someone let me know how I could prove the second part.
 A: Note that $2^{111}\equiv -1\pmod{2^{111}+1}$. Thus $2^{555}\equiv (-1)^5=-1\pmod{2^{111}+1}$.
Similarly, $2^{444}\equiv (-1)^4=1\pmod{2^{111}+1}$, and therefore $2^{111}+1$ divides $2^{444}-1$. It follows that $2^{111}+1$ cannot divide $2^{444}+1$. 
A: Using Binomial expansion, 
$$\displaystyle 2^{111n}=(2^{111})^n=(\underbrace{2^{111}+1}-1)^n$$
$$\sum_{0\le r\le n}\binom nr(2^{111}+1)^{n-r}(-1)^r\equiv(-1)^n\pmod {2^{111}+1}$$ for positive integer $n$ as  Binomial Coefficients are integers and each term except the last is divisible by $2^{111}+1$
This is actually a formula in congruence : $a\equiv b\pmod m\implies a^n\equiv b^n\pmod m$
Here $2^{111}\equiv-1 \pmod {2^{111}+1}\implies (2^{111})^n\equiv(-1)^n\pmod {2^{111}+1}$
A: $a^{odd}+b^{odd}$ is always divisible through $a+b$, and $a^{even}-b^{even}$ is always divisible through $a-b$.
$$a^{2n+1}+b^{2n+1}=(a+b)\cdot\sum_{k=0}^{2n}(-1)^k\cdot a^k\cdot b^{2n-k}$$
E.g., for $n=1$ we have the well-known formula $a^3+b^3=(a+b)(a^2-ab+b^2)$. Likewise, for $n=2$ we have $a^5+b^5=(a+b)(a^4-a^3b+a^2b^2-ab^3+b^4)$. In your case, $a=2^{111}$ and $b=1$
