[Euler-Fermat]

1. จาก $3^{\frac{p-1}{2}}+1 \equiv 0 (mod p) $
$3^{p-1} \equiv (-1)^2 \equiv 1 (mod p)$
จากบทกลับของ Fermat's Little theorem
ถ้า $a^{p-1} \equiv 1 (mod p)$ และ $q$ เป็น $prime$ โดย $q\mid (p-1)$ และ $a^{\frac{p-1}{q}} \not\equiv 1 (mod p)$

จาก $p-1 = 2^n \therefore q = 2 $
ซึ่ง $3^{\frac{p-1}{2}} \equiv -1 \not\equiv 1 (mod p)
\therefore p เป็น prime $