>>327
フェルマーの小定理の対偶を使うんじゃないの？
n=2^15-1 と互いに素な整数aに対して
a^(n-1)-1 が mod n で0にならないならnは素数ではない。

2^16≡2 mod n であることを用いて
2^(2^15-1)=2^(16*2^11-1)≡2^(2^11-1)≡2^(2^3-1)=128≠1