高校数学の裏技コミュのフェルマー小定理・オイラー関数など

■1．フェルマーの小定理
pを素数，nをpで割り切れない自然数とすると
　n^(p-1)をpで割った余りは1
となる．合同式では
　n^(p-1)≡1 (mod p)
【証明】(証明方法はいくつもありますが，京大型の証明で)
1≦k≦p-1のとき
C[p,k]=(p/k)C[p-1,k-1]
p＞kよりC[p-1,k-1]がkで割り切れ，右辺はpの倍数．
∴C[p,k]はpで割り切れる．
n^p={(n-1)+1}^p
　=(n-1)^p+C[p,1](n-1)^(p-1)+…+C[p,p-1](n-1)+1
　≡(n-1)^p+1 (mod p)
以下同様に
n^p≡(n-1)^p+1≡(n-2)^p+2
　≡…≡{n-(n-1)}^p+(n-1)
　≡n (mod p)
となり，これよりn^(p-1)≡1 (mod p)となり，命題は真である．

整数問題では非常に強力な定理で，これを題材にした問題は数多く見られます．

■2．オイラー関数
整数Nが素因数a[1],a[2],…,a[n]をもつとき
　ψ(N)=N(1-1/a[1])(1-1/a[2])…(1-1/a[n])
と関数ψ(N)を定める．このとき，ψ(N)はN以下の自然数でNと互いに素なものの個数を表す．これをオイラー関数と呼ぶ．

■3．オイラー関数の定理

【定理3-1】
pを素数として
　ψ(p^n)=p^n-p^(n-1)

【定理3-2】
a,bを互いに素な自然数として
　ψ(ab)=ψ(a)ψ(b)

【定理3-3】(オイラーの公式)
aとmが互いに素な自然数であるとき，
　a^ψ(m)をmで割った余りは1
　a^ψ(m)≡1 (mod m)
※この定理はフェルマーの小定理を包括しているともいえます．

■4．余談
nが2でも5でも割り切れない自然数であるとき
●n^4の下1桁は1⇔n^5とnの下1桁は等しい
●n^20の下2桁は01
●n^100の下3桁は001
●n^500の下4桁は0001