Euler定理

hbghlyj

Latin: Observationes de theoremate quodam Fermatiano aliisque ad numeros primos spectantibus
1732 年 9 月 26 日提交给圣彼得堡国立大学  (St. Petersburg Academy)
(Leonhard Euler 合集: eulerarchive.maa.org/)
English: Observations on a certain theorem of Fermat and on others concerning prime numbers


Theorem 4
$2n+1$为素数.
$3^n+1$被$2n+1$整除, 若$n\equiv2,3\pmod6$;
$3^n-1$被$2n+1$整除, 若$n\equiv0,5\pmod6$.

Theorem 5
$3^n+2^n$被$2n+1$整除, 若$n\equiv3,5,6,8\pmod{12}$;
$3^n-2^n$被$2n+1$整除, 若$n\equiv0,2,9,11\pmod{12}$.

Theorem 6
$6^n+1$被$2n+1$整除, 若$n\equiv3,5,6,8\pmod{12}$;
$6^n-1$被$2n+1$整除, 若$n\equiv0,2,9,11\pmod{12}$.

hbghlyj

Theorem 4
$2n+1$为素数.
$3^n+1$被$2n+1$整除, 若$n\equiv2,3\pmod6$;
$3^n-1$被$2n+1$整除, 若$n\equiv0,5\pmod6$.

$\varphi(2n+1)=2n$且$\gcd(3,2n+1)=1$,由Euler定理,$3^{2n}\equiv1\pmod{2n+1}⇒3^n\equiv\pm1\pmod{2n+1}$.
若$n\equiv2,3\pmod6$, 则$2n+1\equiv5,7\pmod{12}$, 3是$\bmod2n+1$的二次剩余, $3^n\equiv1\pmod{2n+1}$;
若$n\equiv0,5\pmod6$, 则$2n+1\equiv\pm1\pmod{12}$, 3是$\bmod2n+1$的非二次剩余, $3^n\equiv-1\pmod{2n+1}$.

又见math.stackexchange.com/questions/2162033