自然数の冪乗の和に関する定理の「フェルマーの大定理」あるいは「フェルマーの最終定理」とは異なります。
数論において、フェルマーの小定理(フェルマーのしょうていり、英: Fermat's little theorem)は、素数の性質についての定理であり、実用としてもRSA暗号に応用されている定理である。 p {\displaystyle p} を素数とし、 a {\displaystyle a} を整数とすると、 a p ≡ a ( mod p ) {\displaystyle a^{p}\equiv a{\pmod {p}}} が成立すると言う定理である。また、 p {\displaystyle p} を素数とし、 a {\displaystyle a} を p {\displaystyle p} の倍数でない整数( a {\displaystyle a} と p {\displaystyle p} は互いに素)とするときに、 a p − 1 ≡ 1 ( mod p ) {\displaystyle a^{p-1}\equiv 1{\pmod {p}}} が成立する。すなわち、 a {\displaystyle a} の p − 1 {\displaystyle p-1} 乗を p {\displaystyle p} で割った余りは 1 {\displaystyle 1} である。有名なフェルマーの最終定理と区別するためにあえて「小」定理と称されている。 この定理はピエール・ド・フェルマーの名を冠するが、フェルマーの他の予想と同じく、フェルマー自身によって証明が与えられていたことが確認されているわけではない。この定理に対する証明はゴットフリート・ライプニッツによって初めて与えられた。 3通りの証明を示す。 二項定理から、数学的帰納法を用いて証明する方法が簡便である。 補題:「 ( m + 1 ) p {\displaystyle \left(m+1\right)^{p}} を p {\displaystyle p} で割った余りは m p + 1 {\displaystyle m^{p}+1} を p {\displaystyle p} で割った余りに等しい。」 (補題の証明) ( m + 1 ) p = m p + p C 1 m p − 1 + p C 2 m p − 2 + ⋯ + p C p − 1 m + 1 {\displaystyle (m+1)^{p}=m^{p}+{}_{p}\mathrm {C} _{1}m^{p-1}+{}_{p}\mathrm {C} _{2}m^{p-2}+\dotsb +{}_{p}\mathrm {C} _{p-1}m+1} (二項定理) 右辺の両端以外の二項係数 p C k {\displaystyle {}_{p}\mathrm {C} _{k}} はすべて p {\displaystyle p} の倍数である。なぜなら、 p C k = p ( p − 1 ) ⋯ ( p − k + 1 ) k ( k − 1 ) ⋯ 1 {\displaystyle {}_{p}\mathrm {C} _{k}={\frac {p(p-1)\dotsb (p-k+1)}{k(k-1)\dotsb 1}}} であり、 p {\displaystyle p} は素数であって k < p {\displaystyle k<p} なので、分子に含まれる p {\displaystyle p} が約分されることはないからである。 したがって、 ( m + 1 ) p {\displaystyle \left(m+1\right)^{p}} を p {\displaystyle p} で割った余りは、両端の項 m p + 1 {\displaystyle m^{p}+1} を p {\displaystyle p} で割った余りに等しい。(補題の証明終) 命題「 a p ≡ a ( mod p ) {\displaystyle a^{p}\equiv a{\pmod {p}}} 」を、 a {\displaystyle a} についての数学的帰納法で証明する。 補題に m = 1 {\displaystyle m=1} を代入すると、 2 p = ( 1 + 1 ) p {\displaystyle 2^{p}=\left(1+1\right)^{p}} を p {\displaystyle p} で割った余りは 1 p + 1 = 2 {\displaystyle 1^{p}+1=2} となり、 a = 2 {\displaystyle a=2} のとき成り立つ。 命題が、 a = k {\displaystyle a=k} のとき成り立つと仮定する。 補題から、 ( k + 1 ) p {\displaystyle \left(k+1\right)^{p}} を p {\displaystyle p} で割った余りは k p + 1 {\displaystyle k^{p}+1} を p {\displaystyle p} で割った余りに等しい。帰納法の仮定によって k p {\displaystyle k^{p}} を p {\displaystyle p} で割った余りは k {\displaystyle k} を p {\displaystyle p} で割った余りに等しいから、 ( k + 1 ) p {\displaystyle \left(k+1\right)^{p}} を p {\displaystyle p} で割った余りは k + 1 {\displaystyle k+1} を p {\displaystyle p} で割った余りに等しい。 したがって、命題は a = k + 1 {\displaystyle a=k+1} のときも成り立つ。 数学的帰納法によって、命題は a ≧ 2 {\displaystyle a\geqq 2} に対して成り立つ。また、 a = 0 , 1 {\displaystyle a=0,\ 1} のときは、代入してみると明らかに成り立つので、命題は a ≧ 0 {\displaystyle a\geqq 0} に対して成り立つ。 (証明終) 上の補題と同様に、 ( x + y ) p ≡ x p + y p ( mod p ) {\displaystyle (x+y)^{p}\equiv x^{p}+y^{p}{\pmod {p}}} が示せる。これより、 a p = [ 1 + ( a − 1 ) ] p ≡ 1 p + [ 1 + ( a − 2 ) ] p ≡ 1 + 1 p + [ 1 + ( a − 3 ) ] p ≡ a ( mod p ) {\displaystyle {\begin{aligned}a^{p}&=[1+(a-1)]^{p}\\&\equiv 1^{p}+[1+(a-2)]^{p}\\&\equiv 1+1^{p}+[1+(a-3)]^{p}\\&\equiv a{\pmod {p}}\end{aligned}}} (証明終) p {\displaystyle p} を素数とし、 a {\displaystyle a} と p {\displaystyle p} が互いに素とするときに、 a p − 1 ≡ 1 ( mod p ) {\displaystyle a^{p-1}\equiv 1{\pmod {p}}} が成立することを、ここで証明する。 集合 { 1 , 2 , 3 , … , p − 1 } {\displaystyle \left\{1,\ 2,\ 3,\ldots ,\ p-1\right\}} は、全体として法 p {\displaystyle p} の下で { a , 2 a , 3 a , … , ( p − 1 ) a } {\displaystyle \left\{a,\ 2a,\ 3a,\ldots ,\ \left(p-1\right)a\right\}} と合同である。(背理法による証明)もし後者の集合内に i a ≡ j a ( mod p ) {\displaystyle ia\equiv ja{\pmod {p}}}
概要
証明
証明(1)
証明(2)
証明(3)
Size:34 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef