-
[정수론] 합동식1. 합동식의 정의Math/Number Theory 2023. 7. 4. 21:41
합동식의 정의
Definition. 양의 정수 n과 두 정수 a,b에 대하여 만약 n|(a−b)라면, 법 n에 대하여 a와 b는 합동이라고 하며, 기호로는 a≡bmodn 으로 나타낸다.
즉, 정수 n이 a−b를 나눈다면, 즉 a−b가 n으로 나누어 떨어진다면 n에 대하여 a와 b는 합동인 것이다.
반대로 a−b가 n으로 나누어 떨어지지 않는다면 a와 b는 합동이 아니다.
다르게 표현한다면, ∃k∈Zs.t.a−b=nk 라면 a≡bmodn 이다.
몇가지 예시를 생각해보자.
3−24=−21인데, 7|−21이므로 3≡24mod7이다.
25−12=13인데, 7∤13이므로 25≢12mod7이다.
합동식의 성질
1이 아닌 양의 정수 n과 임의의 네 정수 a,b,c,d에 대하여 다음이 성립한다.
a. a≡amodn
b. If a≡bmodn then b≡amodn
c. If a≡bmodn and b≡cmodn then a≡cmodn
d. If a≡bmodn and c≡dmodn then a+c≡b+dmodn
e. If a≡bmodn and c≡dmodn then ac≡bdmodn
f. If a≡bmodn then a+c≡b+cmodn and ac≡bcmodn
g. If a≡bmodn then ak≡bkmodn for any k∈N
한마디로 정리하면, 합동 기호는 나눗셈을 제외하고는 정수 끼리의 덧셈, 곱셈, 뺄셈과 거듭제곱 연산에 대하여 마치 등호처럼 사용할 수 있다는 것이다!
합동식의 나눗셈?
합동식의 나눗셈을 살펴보기 전에, 아래 도움정리를 먼저 증명해보자.
Lemma 1. 정수 a,b에 대해 d=gcd(a,b) 라면, gcd(a/d,b/d)=1이다.
Proof. 귀류법을 이용해서 증명할 수 있다. gcd(a/d,b/d)≠1이라고 가정해보자.
즉, gcd(a/d,b/d)=k for some k∈Z, k>1 이다.
이때, a/d, b/d는 자명하게 정수이므로, 최대공약수를 정의할 수 있다. 정수인 이유는 스스로 생각해보자...
a/d와 b/d의 최대공약수가 1이 아닌 정수 k라면 다음이 만족한다.
a/d=k⋅s1, b/d=k⋅s2 for some s1,s2∈Z
즉, a=k⋅s1⋅d, b=k⋅s2⋅d가 성립한다.
따라서 d⋅k는 a,b의 공약수이므로, 최대공약수인 d보다 큰 공약수가 존재하게 된다.
결과적으로 모순이 발생하므로, 우리는 가정이 틀렸음을 알 수 있다. ◼
이제, 이 보조 정리를 이용해서 아래 theorem을 증명해보겠다.
Theorem. 정수 a,b,c,n에 대하여 ca≡cbmodn일 때, a≡bmod(n/d) (단, d=gcd(c,n)) 이다.
Proof. ca≡cbmodn라면, 정의에 의해 n|(ca−cb) 이므로 n|c(a−b)⋯(1)이다.
이때, d=gcd(c,n)이라고 하자. 즉, c=k1d, n=k2d를 만족시키는 정수 k1,k2가 존재한다.
식 (1)을 다시 쓰면, k2d|k1d(a−b) 이므로, 어떤 정수 k′에 대해 k1d(a−b)=k2d⋅k′ 이다.
양변을 d로 나누면 k1(a−b)=k2⋅k′ 이므로, k2|k1(a−b)이다.
이때, k1=c/d,k2=n/d이므로, lemma 1에 의해서 gcd(k1,k2)=1이다.
따라서 k2|k1(a−b)라면 k2|a−b가 성립한다.
즉, a≡bmodk2 이므로, a≡bmod(n/d)임을 알 수 있다. ◼
예를 들어서, 14≡2mod12 일 때, 7≡1mod6이다.
양변을 2로 나누는 것 처럼 위의 정리를 사용할 수 있다는 것이다.
특수한 상황으로, 만약 n과 c가 서로소라면, ca≡cbmodn일 때 a≡bmodn이다.
예를 들어서, −35≡45mod8일 때, 5와 8이 서로소이므로, −7≡9mod8이다.
이러한 특수한 경우에는, 합동식 양변을 5로 나누어도 성립한다는 것이다.
*이 글은 Elementary Number Theory를 참고하여 작성하였다.*
'Math > Number Theory' 카테고리의 다른 글
[정수론] 합동식3. 중국인의 나머지 정리 0 2023.08.03 [정수론] 합동식2. 선형 합동식 0 2023.07.06