페르마의 소정리

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

페르마의 소정리(Fermat's little theorem, -小定理)는 페르마의 이름이 붙은 정리 가운데 하나이며, 그 내용은 다음과 같다.

p가 소수이고 a를 p의 배수가 아닌 자연수라 할 때, 즉, gcd(a,p)=1임이 성립할 때,

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

이 성립한다.

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

1 × 2 × 3 × ... × (p-1)은 법 p에 대해 합동이다. 또, 이는 p와 서로소이다. 따라서 합동식의 양변에서 1 × 2 × 3 × ... × (p-1)를 나눠줄 수 있다. 그러면 원하는 식, a^{p-1} \equiv 1 \pmod{p}이 나온다.

일반화[편집]

오일러의 정리[편집]

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

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

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

유한체론[편집]

유한체론에서 다항식의 나눗셈에 관련된 결과를 통해 페르마의 소정리를 일반화할 수도 있다.[1] 이는 다음과 같이 쓸 수 있다.

  • 위수 p인 유한체 상의 다항식 g(x) 에 대하여, 다음 두 명제가 성립한다.
  1. g(x) 가 기약이며 x^{p^{n}} - x 을 나눈다면, deg(g(x)) | n이다.
  2. 어떤 n에 대해, k | n이고 기약이며 x^{p^{n}} - x 을 나눈다는 조건을 만족하는 k차 다항식 g(x) 의 개수를 C(p, k)라 정의하자. 그러면,  \sum_{j|k} jC(p, j) = p^{k} \qquad \frac{}{} 이다.

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

  • C(p, k) = \frac{1}{k} \sum_{j|k} \mu(j)p^{k/j}

가소수(假素數)[편집]

페르마의 소정리에 나타난 합동식을 만족하는 수가 반드시 소수가 되지는 않는다.

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

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

주석[편집]

  1. Joseph A. Gallian (2006), Contemporary Abstract Algebra, Houghton Mifflin Company(Boston, New York), p.388.