Processing math: 100%

ABOUT ME

Today
Yesterday
Total
  • [정수론] 합동식1. 합동식의 정의
    Math/Number Theory 2023. 7. 4. 21:41

    합동식의 정의

    Definition. 양의 정수 n과 두 정수 a,b에 대하여 만약 n|(ab)라면, 법 n에 대하여 ab는 합동이라고 하며, 기호로는 abmodn 으로 나타낸다. 

     

     

    즉, 정수 nab를 나눈다면, 즉 abn으로 나누어 떨어진다면 n에 대하여 ab는 합동인 것이다. 

    반대로 abn으로 나누어 떨어지지 않는다면 ab는 합동이 아니다. 

     

     

    다르게 표현한다면, kZs.t.ab=nk 라면 abmodn 이다.

     

     

     

    몇가지 예시를 생각해보자. 

    324=21인데, 7|21이므로 324mod7이다. 

    2512=13인데, 713이므로 2512mod7이다. 

     

     


     

    합동식의 성질

    1이 아닌 양의 정수 n과 임의의 네 정수 a,b,c,d에 대하여 다음이 성립한다.

     

    a. aamodn

    b. If abmodn then bamodn

    c. If abmodn and bcmodn then acmodn

    d. If abmodn and cdmodn then a+cb+dmodn

    e. If abmodn and cdmodn then acbdmodn

    f. If abmodn then a+cb+cmodn and acbcmodn

    g. If abmodn then akbkmodn for any kN

     

     

    한마디로 정리하면, 합동 기호는 나눗셈을 제외하고는 정수 끼리의 덧셈, 곱셈, 뺄셈과 거듭제곱 연산에 대하여 마치 등호처럼 사용할 수 있다는 것이다!

     

     


     

    합동식의 나눗셈?

    합동식의 나눗셈을 살펴보기 전에, 아래 도움정리를 먼저 증명해보자.

     

    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 kZ, k>1 이다.

    이때, a/d, b/d는 자명하게 정수이므로, 최대공약수를 정의할 수 있다. 정수인 이유는 스스로 생각해보자...

     

    a/db/d의 최대공약수가 1이 아닌 정수 k라면 다음이 만족한다.

    a/d=ks1, b/d=ks2 for some s1,s2Z

     

    즉, a=ks1d, b=ks2d가 성립한다.

    따라서 dka,b의 공약수이므로, 최대공약수인 d보다 큰 공약수가 존재하게 된다.

    결과적으로 모순이 발생하므로, 우리는 가정이 틀렸음을 알 수 있다.

     

     

     

    이제, 이 보조 정리를 이용해서 아래 theorem을 증명해보겠다.

     

     

     

    Theorem. 정수 a,b,c,n에 대하여 cacbmodn일 때, abmod(n/d) (단, d=gcd(c,n)) 이다. 

     

    Proof. cacbmodn라면, 정의에 의해 n|(cacb) 이므로 n|c(ab)(1)이다. 

     

    이때, d=gcd(c,n)이라고 하자. 즉, c=k1d, n=k2d를 만족시키는 정수 k1,k2가 존재한다. 

    (1)을 다시 쓰면, k2d|k1d(ab) 이므로, 어떤 정수 k에 대해 k1d(ab)=k2dk 이다. 

     

    양변을 d로 나누면 k1(ab)=k2k 이므로, k2|k1(ab)이다. 

    이때, k1=c/d,k2=n/d이므로, lemma 1에 의해서 gcd(k1,k2)=1이다. 

    따라서 k2|k1(ab)라면 k2|ab가 성립한다.

    즉, abmodk2 이므로, abmod(n/d)임을 알 수 있다.

     

     

     

    예를 들어서, 142mod12 일 때, 71mod6이다.

    양변을 2로 나누는 것 처럼 위의 정리를 사용할 수 있다는 것이다.

     

    특수한 상황으로, 만약 nc가 서로소라면, cacbmodn일 때 abmodn이다.

    예를 들어서, 3545mod8일 때,  58이 서로소이므로, 79mod8이다.

    이러한 특수한 경우에는, 합동식 양변을 5로 나누어도 성립한다는 것이다. 

     

    *이 글은 Elementary Number Theory를 참고하여 작성하였다.*

    댓글

Designed by Tistory.