오일러 정리

오일러 정리는 레온하르트 오일러가 발견한, 정수론과 군론에서 중요한 정리이다.

정수론에서의 오일러 정리

정수론에서 오일러 정리는 다음과 같이 정의된다:

• a와 n이 서로소인 양의 정수일 때, 다음이 성립한다.

  a^φ(n) ≡ 1 (mod n)
  

  여기서 φ(n)은 오일러 피 함수이며, n보다 작으면서 n과 서로소인 양의 정수의 개수를 나타낸다.

페르마의 소정리는 오일러 정리의 특수한 경우로, n이 소수 p일 때 φ(p) = p-1이므로 a^(p-1) ≡ 1 (mod p)가 된다.

군론에서의 오일러 정리

군론에서 오일러 정리는 다음과 같이 일반화될 수 있다:

• 유한군 G의 모든 원소 g에 대해, 다음이 성립한다.

  g^|G| = e
  

  여기서 |G|는 군 G의 크기(원소의 개수)이고, e는 군 G의 항등원이다.

정수론에서의 오일러 정리는 곱셈군 (Z/nZ)* 에 대한 군론적 오일러 정리의 특별한 경우로 볼 수 있다. (Z/nZ)* 는 n을 법으로 하는 기약 잉여류 군이며, 그 크기는 φ(n)이다.

응용

오일러 정리는 RSA 암호화 알고리즘과 같은 암호학에서 핵심적인 역할을 한다. 또한, 큰 수의 거듭제곱의 나머지를 효율적으로 계산하는 데에도 사용된다.