위수 (정수론): 두 판 사이의 차이

2018년 12월 17일 (월) 19:14 기준 최신판

정의[편집 | 원본 편집]

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번 성질과 나누어떨어짐의 성질을 이용하자.

사실 위 모든 성질은 일반적인 군에 대해서도 성립한다.

같이 보기[편집 | 원본 편집]

@@ 2번째 줄: / 2번째 줄: @@
 == 정의 ==
-이상의 [[정수]] \(m\)에 대해 \(a\)가 \((a,m)=1\)인 정수일 때,
+이상의 [[정수]] <math>m</math>에 대해 <math>a</math>가 <math>(a,m)=1</math>인 정수일 때,
 : <math>a^r \equiv 1 \pmod m</math>
-인 가장 작은 양의 정수 \(r\)을 법 \(m\)에 대한 \(a\)의 '''위수(order)'''라고 하고, \(\operatorname{ord}_m a\)로 표기한다.
+인 가장 작은 양의 정수 <math>r</math>을 법 <math>m</math>에 대한 <math>a</math>의 '''위수(order)'''라고 하고, <math>\operatorname{ord}_m a</math>로 표기한다.
 === 존재성 ===
-[[오일러의 정리]]에 의해 \(a^{\phi(m)}\equiv 1 \pmod m\)이고 \(\phi(m)>0\)이므로 \(a^r\equiv 1 \pmod m\)인 양의 정수 \(r\)이 존재한다. 따라서 [[정렬순서원리]]에 의해 원하는 결론을 얻는다.
+[[오일러의 정리]]에 의해 <math>a^{\phi(m)}\equiv 1 \pmod m</math>이고 <math>\phi(m)>0</math>이므로 <math>a^r\equiv 1 \pmod m</math>인 양의 정수 <math>r</math>이 존재한다. 따라서 [[정렬순서원리]]에 의해 원하는 결론을 얻는다.
 == 성질 ==
-#\(a\equiv b\pmod m\)이면 \(\operatorname{ord}_m a=\operatorname{ord}_m b\)이다.
+#<math>a\equiv b\pmod m</math>이면 <math>\operatorname{ord}_m a=\operatorname{ord}_m b</math>이다.
 #*<math>a\equiv b\pmod m</math>이면 <math>a,\,b</math>는 같은 congruence class 안에 있다는 뜻이다. 그렇기 때문에 위수도 당연히 같다.
 #<math>a</math>의 위수를 <math>n</math>이라 하고, <math>a^k\equiv1\pmod m</math>일 때, <math>n\mid k</math>이다.