정의[편집 | 원본 편집]
2 이상의 정수 [math]\displaystyle{ m }[/math]에 대해 [math]\displaystyle{ a }[/math]가 [math]\displaystyle{ (a,m)=1 }[/math]인 정수일 때,
- [math]\displaystyle{ a^r \equiv 1 \pmod m }[/math]
인 가장 작은 양의 정수 [math]\displaystyle{ r }[/math]을 법 [math]\displaystyle{ m }[/math]에 대한 [math]\displaystyle{ a }[/math]의 위수(order)라고 하고, [math]\displaystyle{ \operatorname{ord}_m a }[/math]로 표기한다.
존재성[편집 | 원본 편집]
오일러의 정리에 의해 [math]\displaystyle{ a^{\phi(m)}\equiv 1 \pmod m }[/math]이고 [math]\displaystyle{ \phi(m)\gt 0 }[/math]이므로 [math]\displaystyle{ a^r\equiv 1 \pmod m }[/math]인 양의 정수 [math]\displaystyle{ r }[/math]이 존재한다. 따라서 정렬순서원리에 의해 원하는 결론을 얻는다.
성질[편집 | 원본 편집]
- [math]\displaystyle{ a\equiv b\pmod m }[/math]이면 [math]\displaystyle{ \operatorname{ord}_m a=\operatorname{ord}_m b }[/math]이다.
- [math]\displaystyle{ a\equiv b\pmod m }[/math]이면 [math]\displaystyle{ a,\,b }[/math]는 같은 congruence class 안에 있다는 뜻이다. 그렇기 때문에 위수도 당연히 같다.
- [math]\displaystyle{ a }[/math]의 위수를 [math]\displaystyle{ n }[/math]이라 하고, [math]\displaystyle{ a^k\equiv1\pmod m }[/math]일 때, [math]\displaystyle{ n\mid k }[/math]이다.
- 나눗셈 정리를 이용해 증명한다. 한편, [math]\displaystyle{ a^{\phi\left(m\right)}\equiv1\pmod m }[/math]이기 때문에 [math]\displaystyle{ n\mid\phi\left(m\right) }[/math]임을 알 수 있다.
- [math]\displaystyle{ a }[/math]의 위수를 [math]\displaystyle{ n }[/math]이라 하면, [math]\displaystyle{ a^r }[/math] ([math]\displaystyle{ 0\leq r\leq n-1 }[/math])의 값은 전부 다르다.
- 나눗셈 정리를 이용해 증명할 수 있다. 혹은, [math]\displaystyle{ \left\lt a\right\gt }[/math]가 법 [math]\displaystyle{ m }[/math]에 관해 위수 [math]\displaystyle{ n }[/math]을 가지는 순환군임을 이용하면 더 쉽다.
- [math]\displaystyle{ a^k\equiv a^l\pmod m }[/math]이면, [math]\displaystyle{ k\equiv l\pmod n }[/math]이다 ([math]\displaystyle{ n=\operatorname{ord}_m a }[/math]).
- 2번 성질을 이용하면 된다.
- [math]\displaystyle{ a^k }[/math]의 위수는 [math]\displaystyle{ \frac{n}{\gcd\left(k,m\right)} }[/math]이다.
- 2번 성질과 나누어떨어짐의 성질을 이용하자.
- [math]\displaystyle{ a_1,\,a_2 }[/math]의 위수를 각각 [math]\displaystyle{ n_1,\,n_2 }[/math]라 하자. 만약 [math]\displaystyle{ \gcd\left(n_1,n_2\right)=1 }[/math]이면, [math]\displaystyle{ a_1a_2 }[/math]의 위수는 [math]\displaystyle{ n_1n_2 }[/math]이다.
- 역시 2번 성질과 나누어떨어짐의 성질을 이용하자.
사실 위 모든 성질은 일반적인 군에 대해서도 성립한다.