합성수 법에도 적용
법이 소수일 필요는 없지만 밑 a와 법 m은 서로소여야 한다. m=10이면 φ(10)=4이고 3⁴=81≡1 (mod 10)이다. 3과 10은 서로소이므로 정리를 적용할 수 있다.
지수 계산 줄이기
3⁴≡1 (mod 10)을 이용하면 43=4×10+3에서 3⁴³≡3³≡7 (mod 10)이다. 큰 거듭제곱의 정수값을 전부 만들지 않고 필요한 나머지를 계산할 수 있다.
조건이 빠지면
2와 10은 서로소가 아니다. 실제로 2⁴=16은 법 10에서 1에 합동이 아니다. 따라서 지수에 φ(m)이 들어간다는 형식만 보고 모든 밑에 같은 결론을 적용해서는 안 된다.
소정리와의 관계
m이 소수 p라면 φ(p)=p−1이므로 p가 a를 나누지 않을 때 aᵖ⁻¹≡1을 얻는다. 이는 페르마의 소정리의 한 형태다. 오일러 정리는 서로소 조건을 유지하며 법을 합성수까지 넓힌다.
관련 문서
오일러 피 함수 / 페르마의 소정리 / 합동식 / 서로소 / 최대공약수 / 거듭제곱 / 나머지 / 모듈러 역원 / 소수 (수론)