Divisibility

cubrikal · #1 $Old$ November 2nd, 2009, 12:32 AM

A friend sent me the problem: Show that $2^{111} + 1$ divides $2^{555} + 1$ but does not divide $2^{444} + 1.$ . So just rearranging terms, I get:
$\begin{array} {lcr} 2^{555} + 1 = \\ (2^{444} + 1)(2^{111} + 1) - (2^{444} + 2^{111}) = \\(2^{444} + 1)(2^{111} + 1) - ((2^{444} - 1) + (2^{111}+1)) = \\(2^{444} + 1)(2^{111} + 1) - ((2^{111} + 1)(2^{111} - 1)(2^{222} + 1) + (2^{111} + 1)) \end{array}$
So the last line has a factor of 2^111 + 1 in each term, and I used the same method to show the second part. But is there a way to solve this question with modular arithmetic? I think it would be clearer.