페르마의 소정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

수론에서, 페르마의 소정리(Fermat의小定理, 영어: Fermat’s little theorem)는 어떤 수가 소수일 간단한 필요조건에 대한 정리이다.

정의[편집]

p소수이고, a정수이며, a\nmid p라고 하자. 페르마의 소정리에 따르면, 법 p에서 a^pa는 서로 합동이다.

a^p \equiv a \pmod p

위 식은 a=0일 때 자명하게 성립한다. 만약 a\ne0일 경우, 양변을 약분하여 다음과 같이 쓸 수 있다.

a^p \equiv a \pmod p\qquad(a\ne0)

이는 모든 소수가 만족시키는 필요조건이지만, 충분조건이 아니다. 즉, 페르마의 소정리에 나타난 합동식을 만족하는 수가 반드시 소수가 되지는 않는다.

a^{b-1} \equiv 1 \pmod{b}

를 만족하면서 소수가 아닌 b를, a를 밑수로 하는 카마이클 수라고 부른다.

역사[편집]

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

증명[편집]

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

  1. a와 서로소인 소수 p에 대해 a, 2a, 3a, ..., (p-1)a인 p-1개의 수를 살펴보자. 이 수들을 p로 나눴을 때 나오는 나머지는 모두 다르다.
    1. 증명 : 귀류법으로, 서로 같은 나머지를 가진 두 수, ia와 ja가 있다고 하자(0 < i < j < p인 정수). 그렇다면 이 두 수의 차는 p로 나누어질 것이다. 두 수의 차는 (j-i)a이다. 그러나 0<j-i<p이므로 j-i는 p와 서로소이며, 문제의 가정에 따라 a는 p와 서로소이다.
    2. 따라서 같은 나머지를 가지는 수가 없으므로, p-1개의 수는 모두 그 나머지가 다르다.
  2. 또 0 < i < p인 i에 대해 ia 역시 p의 배수가 아니다. 이에 대한 증명은 위와 같으므로 생략한다.
  3. 이제 집합
    A = \left\{x|x = ia,\;i\in\{1,\dots,p-1\}\right\}
    를 정의하자. 이는 첫 번째에 가정한 p-1개의 수들의 집합이다. 또, 집합
    B = \{1,2\dots,p-1\}
    를 보자. 이는 p와 서로소인 수를 p로 나눌 때 생기는 모든 나머지들의 집합이다. 처음에 했던 증명에 의해, A와 B의 크기는 같다.
  4. 따라서,
    a \times 2a \times 3a \times \cdots\times(p-1)a\equiv 1\times2\times\cdots\times(p-1)\not\equiv0\pmod p
    이다. 양변을 (p-1)!로 나누면,
    a^{p-1} \equiv 1 \pmod p
    을 얻는다.

일반화[편집]

오일러의 정리[편집]

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

a^{\varphi(n)} \equiv 1 \pmod{n}

이 성립한다. 식에서 \varphi(n)오일러 피 함수를 나타낸다.

유한체론[편집]

유한체 이론에서 다항식의 나눗셈에 관련된 결과를 통해 페르마의 소정리를 일반화할 수도 있다.[1] 표수p인 유한체 \mathbb F_{p^r}에 대하여, 다음 두 명제가 성립한다.

  1. 기약 다양식 g\in \mathbb F_{p^r}[x]에 대하여, g\mid x^{p^n} - x라면 \deg g\mid n이다.
  2. k \mid n인 두 양의 정수 k,n\in\mathbb Z^+에 대하여, C(p,k)g\mid x^{p^n} - x인 k차 기약 다항식 g\in\mathbb F_{p^r}[x]들의 수라고 하자. 그렇다면
\sum_{j\mid k} jC(p, j) = p^k
이다.

여기서, 뫼비우스 반전 공식에 따라 C(p, k)를 얻는 일반적인 공식을 구하면 다음과 같다.

C(p, k) = \frac1k \sum_{j \mid k} \mu(j)p^{k/j}

여기서 \mu(j)뫼비우스 함수이다.

참고 문헌[편집]

  1. Joseph A. Gallian (2006), Contemporary Abstract Algebra, Houghton Mifflin Company(Boston, New York), p.388.
  • (영어) Golomb, Solomon W. (1956년 12월). Combinatorial proof of Fermat’s “little” theorem. 《The American Mathematical Monthly》 63 (10): 718–718. doi:10.2307/2309563. JSTOR 2309563.
  • (영어) Alkauskas, Giedrius (2009년 4월). A curious proof of Fermat’s little theorem. 《The American Mathematical Monthly》 116 (4): 362–364. arXiv:0801.0805. Bibcode2008arXiv0801.0805A. JSTOR 40391097.

바깥 고리[편집]