페르마의 소정리 문서 원본 보기

[[수론]]에서 '''페르마의 소정리'''(Fermat小定理, {{llang|en|Fermat’s little theorem}})는 어떤 수가 [[소수 (수론)|소수]]일 간단한 [[필요 조건]]에 대한 정리이다. 추상적으로, [[소수 (수론)|소수]] 크기의 [[유한체]] 위의 [[프로베니우스 사상]]이 [[항등 함수]]임을 의미한다.

== 정의 ==
<math>p</math>가 [[소수 (수론)|소수]]이고, <math>a</math>가 [[정수]]라고 하자. '''페르마의 소정리'''에 따르면, 법 <math>p</math>에서 <math>a^p</math>와 <math>a</math>는 서로 [[합동 (수론)|합동]]이다.
:<math>a^p \equiv a \pmod p</math>
위 식은 <math>p\mid a</math>일 때 자명하게 성립한다. 만약 <math>p\nmid a</math>일 경우, 양변을 약분하여 다음과 같이 쓸 수 있다.
:<math>a^{p-1} \equiv 1 \pmod p\qquad(a\ne0)</math>

이는 모든 소수가 만족시키는 [[필요조건]]이지만, [[충분조건]]이 아니다. 즉, 페르마의 소정리에 나타난 합동식을 만족하는 수가 반드시 [[소수 (수론)|소수]]가 되지는 않는다.
:<math>a^{b-1} \equiv 1 \pmod{b}</math>
를 만족하면서 소수가 아닌 <math>b</math>를, <math>a</math>를 밑수로 하는 ''' [[카마이클 수]]'''라고 부른다.

== 역사 ==
[[피에르 드 페르마]]의 이름이 붙어 있지만, 페르마는 이 정리를 언급했을 뿐, 정확한 증명을 제시하지는 않았다. 현재 기록상 남아 있는 증명 가운데 최초는 [[고트프리트 라이프니츠]]의 것이다.

== 증명 ==
페르마의 소정리를 증명하는 방법은 여러 가지가 있을 수 있지만, 가장 쉬운 방법으로 [[합동식]]을 이용하는 방법이 있다. 그 증명 방법을 나타내면 다음과 같다.

<ol>
<li> <math>a</math>와 서로소인 소수 <math>p</math>에 대해 <math>a,\ 2a,\ 3a,\ \cdots\ ,\ (p-1)a</math>인 <math>p-1</math>개의 수를 살펴보자. 이 수들을 <math>p</math>로 나눴을 때 나오는 [[나머지]]는 모두 다르다.
* 증명 : [[귀류법]]으로, 두 수 <math>ia</math>와 <math>ja</math>가 존재해서 그 나머지가 같다고 하자(<math>0 < i < j < p</math>인 정수). 그렇다면 그 두 수의 차 <math>(j-i)a</math>는 <math>p</math>로 나누어질 것이다. 그러나 <math>0<j-i<p</math>이므로 <math>j-i</math>는 <math>p</math>의 배수가 아니며, 문제의 가정에 따라 <math>a</math>는 <math>p</math>와 서로소이다.
* 따라서 같은 나머지를 가지는 수가 없으므로, <math>p-1</math>개의 수는 모두 그 나머지가 다르다.
<li> 또 <math>0 < i < p</math>인 <math>i</math>에 대해 <math>ia</math> 역시 <math>p</math>의 배수가 아니다. 이에 대한 증명은 위와 같으므로 생략한다.
<li> 이제 [[집합]]
:<math>A = \left\{x|x = ia,\;i\in B\right\}</math>

를 정의하자. 이는 첫 번째에 가정한 <math>p-1</math>개의 수들의 집합이다. 여기서 집합
:<math>B = \{1,\ 2,\ \cdots\ ,\ p-1\}</math>
인데, <math>p</math>와 서로소인 수를 <math>p</math>로 나눌 때 생기는 모든 나머지들의 집합이다. 처음에 했던 증명에 의해, <math>A</math>와 <math>B</math>의 [[기수 (수학)|크기]]는 같다.

<li> 따라서,
:<math>a \times 2a \times 3a \times \cdots\times(p-1)a\equiv 1\times2\times\cdots\times(p-1)\not\equiv0\pmod p</math>
이다. 양변을 <math>(p-1)!</math>로 나누면,
:<math>a^{p-1} \equiv 1 \pmod p</math>
을 얻는다.
</ol>

== 일반화 ==
=== 오일러 정리 ===
{{본문|오일러 정리}}

이 정리는 [[오일러 파이 함수]]를 이용하여, [[소수]]가 아닌 [[정수]] n에 대해서까지 [[다음]]과 같이 [[일반화]]할 수 있다. n이 [[자연수]], a가 n과 [[서로소 정수|서로소]]인 [[자연수]]일 때,

:<math>a^{\varphi(n)} \equiv 1 \pmod{n}</math>

이 성립한다. 식에서 <math>\varphi(n)</math>는 [[오일러 파이 함수]]를 나타낸다.

=== 유한체론 ===
[[유한체]] 이론에서 다항식의 나눗셈에 관련된 결과를 통해 페르마의 소정리를 일반화할 수도 있다.<ref>Joseph A. Gallian (2006), ''Contemporary Abstract Algebra'', Houghton Mifflin Company(Boston, New York), p.388.</ref>
[[환의 표수|표수]]가 <math>p</math>인 유한체 <math>\mathbb F_{p^r}</math>에 대하여, 다음 두 명제가 성립한다.
# [[기약 다항식]] <math>g\in \mathbb F_{p^r}[x]</math>에 대하여, <math>g\mid x^{p^n} - x</math>라면 <math>\deg g\mid n</math>이다.
# <math>k \mid n</math>인 두 양의 정수 <math>k,n\in\mathbb Z^+</math>에 대하여, <math>C(p,k)</math>를 <math>g\mid x^{p^n} - x</math>인 k차 [[기약 다항식]] <math>g\in\mathbb F_{p^r}[x]</math>들의 수라고 하자. 그렇다면

:::<math>\sum_{j\mid k} jC(p, j) = p^k</math>
::이다.

여기서, [[뫼비우스 반전 공식]]에 따라 C(p, k)를 얻는 일반적인 공식을 구하면 다음과 같다.
:<math>C(p, k) = \frac1k \sum_{j \mid k} \mu(j)p^{k/j}</math>
여기서 <math>\mu(j)</math>는 [[뫼비우스 함수]]이다.

== 같이 보기 ==
* [[프로베니우스 사상]]
* [[모듈러 역원]]
== 참고 문헌 ==
<references/>
* {{저널 인용|성=Golomb|이름=Solomon W.|제목=Combinatorial proof of Fermat’s “little” theorem|url=https://archive.org/details/sim_american-mathematical-monthly_1956-12_63_10/page/n32|저널=The American Mathematical Monthly|권=63|호=10|날짜=1956-12|쪽=718–718|doi=10.2307/2309563|jstor=2309563|언어=en}}
* {{저널 인용|성=Alkauskas|이름=Giedrius|제목=A curious proof of Fermat’s little theorem|url=https://archive.org/details/sim_american-mathematical-monthly_2009-04_116_4/page/n75|저널=The American Mathematical Monthly|권=116|호=4|날짜=2009-04|쪽=362–364|arxiv=0801.0805|bibcode=2008arXiv0801.0805A|jstor=40391097|언어=en}}

== 외부 링크 ==
* {{eom|title=Fermat's little theorem}}
* {{매스월드|id=FermatsLittleTheorem|title=Fermat's little theorem}}

{{전거 통제}}
{{위키데이터 속성 추적}}

[[분류:소수에 관한 정리]]
[[분류:사람 이름을 딴 낱말]]
[[분류:모듈러 산술]]