<s>[INST] 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.
 [/INST] $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$
</s>