(→정의) |
잔글 (문자열 찾아 바꾸기 - "\)" 문자열을 "</math>" 문자열로) |
||
(사용자 2명의 중간 판 3개는 보이지 않습니다) | |||
1번째 줄: | 1번째 줄: | ||
== 정의 == | == 정의 == | ||
2 이상의 [[정수]] | 2 이상의 [[정수]] <math>m</math>에 대해 <math>a</math>가 <math>(a,m)=1</math>인 정수일 때, | ||
: <math>a^r \equiv 1 \pmod m</math> | : <math>a^r \equiv 1 \pmod m</math> | ||
인 가장 작은 양의 정수 | 인 가장 작은 양의 정수 <math>r</math>을 법 <math>m</math>에 대한 <math>a</math>의 '''위수(order)'''라고 하고, <math>\operatorname{ord}_m a</math>로 표기한다. | ||
=== 존재성 === | === 존재성 === | ||
[[오일러의 정리]]에 의해 | [[오일러의 정리]]에 의해 <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>이 존재한다. 따라서 [[정렬순서원리]]에 의해 원하는 결론을 얻는다. | ||
== 성질 == | == 성질 == | ||
# | #<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\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>이다. | #<math>a</math>의 위수를 <math>n</math>이라 하고, <math>a^k\equiv1\pmod m</math>일 때, <math>n\mid k</math>이다. |
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번 성질과 나누어떨어짐의 성질을 이용하자.
사실 위 모든 성질은 일반적인 군에 대해서도 성립한다.