잔글 (→성질) |
(→정의) |
||
| 4번째 줄: | 4번째 줄: | ||
2 이상의 [[정수]] \(m\)에 대해 \(a\)가 \((a,m)=1\)인 정수일 때, | 2 이상의 [[정수]] \(m\)에 대해 \(a\)가 \((a,m)=1\)인 정수일 때, | ||
: <math>a^r \equiv 1 \pmod m</math> | : <math>a^r \equiv 1 \pmod m</math> | ||
인 가장 작은 양의 정수 \(r\)을 법 \(m\)의 '''위수(order)'''라고 하고, \(\operatorname{ord}_m a\)로 표기한다. | 인 가장 작은 양의 정수 \(r\)을 법 \(m\)에 대한 \(a\)의 '''위수(order)'''라고 하고, \(\operatorname{ord}_m a\)로 표기한다. | ||
=== 존재성 === | === 존재성 === | ||
2015년 11월 12일 (목) 22:05 판
정의
2 이상의 정수 \(m\)에 대해 \(a\)가 \((a,m)=1\)인 정수일 때,
- [math]\displaystyle{ a^r \equiv 1 \pmod m }[/math]
인 가장 작은 양의 정수 \(r\)을 법 \(m\)에 대한 \(a\)의 위수(order)라고 하고, \(\operatorname{ord}_m a\)로 표기한다.
존재성
오일러의 정리에 의해 \(a^{\phi(m)}\equiv 1 \pmod m\)이고 \(\phi(m)>0\)이므로 \(a^r\equiv 1 \pmod m\)인 양의 정수 \(r\)이 존재한다. 따라서 정렬순서원리에 의해 원하는 결론을 얻는다.
성질
- \(a\equiv b\pmod m\)이면 \(\operatorname{ord}_m a=\operatorname{ord}_m b\)이다.
- [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번 성질과 나누어떨어짐의 성질을 이용하자.
사실 위 모든 성질은 일반적인 군에 대해서도 성립한다.