>>591
n = 4k + r (k:整数, 0≦r≦3) とすると
2^n + 1
= …
= 15*(…) + (2 または 3 または 5 または 9) なので 15で割り切れない

n = 2k のとき
2^n + 1 = 3*(…) + 2 なので 3で割り切れない
n = 2k+1 のとき
2^n + 1 = 5*(…) + 1 ± 2 なので 5で割り切れない

16^k = (15+1)^k, 4^k = (5-1)^k とするあたりがポイント。

もちろん、どっちも広い意味では余りの周期性に注目してる。