본문 바로가기
스터디/알고리즘

[정수론] 합동 (Congruence)

by 궁금한 준이 2024. 10. 5.
728x90
반응형

합동 (Congruence)

합동 관계 (congruence relation)

m에 대하여 m(ab)인 경우 ab(modm)으로 표기하고, "법(modulo) m에 관한 합동관계"라고 한다. 영어로는 congruence relation modulo m 이다.

※ LaTeX으로 합동을 표기할 때는 \equiv 를 사용하고, modulo는 \mod{m} 또는 \pmod{m} 를 사용한다. 

 

다음 세 문장은 동치이다.

  • ab(modm)
  • a=b+mt인 정수 t가 존재한다.
  • a=mq1+r이고 b=mq2+r를 만족하는 정수 q1,q2,r가 존재한다.

그리고 다음이 성립한다.

  • aa(modm)
  • ab(modm)ba(modm)
  • ab(modm), bc(modm)ac(modm)

 

k개의 정수쌍이 합동이면 합/곱 역시 합동관계이다. 즉,

kZ에 대하여 aibi(modm)이면

  • iaiibi(modm)
  • iaiibi(modm)

특히 ab(modm)인 경우,

  • nanb(modm), a+cb+c(modm)
  • anbn(modm), acbc(modm)

서로 합동이라면, 덧셈, 곱셈, 거듭제곱에서도 합동관계가 보존된다.

Example

32043으로 나눈 나머지를 구해보자.

34=815(mod43)이므로 320=(34)5(5)5=(25)(125)(mod43)

한편 1254(mod43)이므로

(25)(125)(25)(4)=10014(mod43)

따라서 32014(mod43) 이다.

 

다항식에서의 합동

정수 계수를 갖는 다항식이 다음과 같다고 하자.

f(x)=c0+c1x+c2x2++cnxn

g(x)=d0+d1x+d2x2++dnxn

그리고 양의 정수 m에 대하여 ab(modm)라 하자. 그러면 다음이 성립한다.

  • f(a)f(b)(modm)
  • ckdk(modm)(0kn)이면 f(a)g(b)(modm)

 

3의 배수와 9의 배수 판정

초등학교때 "모든 자릿수의 수를 더한 수가 3의 배수이면, 원래 수도 3의 배수이다"

또는 "모든 자릿수의 수를 더한 수가 9의 배수이면, 원래 수도 9의 배수이다"를 배웠다.

위에서 설명한 다항식에서의 합동을 이용하여 증명할 수 있다.

우리가 사용하는 수 체계가 10진법임을 이용한다.

 

높은자리부터 표기하므로 f(x)=anxn+an1xn1+a1x+a0라 하자.

모든 자릿수의 합은 c=f(1)이고, 10진법으로 표기한 수를 b라 하면 b=f(10)이다.

한편, 101(mod3)이므로 b=f(10)f(1)=c(mod3) 이다.

따라서 만약 3b 라면 3bb0(mod3)c0(mod3)3c 이다.

 

9의 배수도 동일하게 증명할 수 있다.

 

11의 배수도 비슷하게 증명할 수 있다.

낮은 자리수부터 차례대로 더하고 뺀 수를 d=a0a1+a2a3++(1)nan이라 하자.

101(mod11)이므로 b=f(10)f(1)=d(mod11) 임을 이용하여 증명이 가능하다.

 

N=583461의 경우, 각 자릿수의 합이 27이고 327, 927이므로 N은 3의 배수이면서 9의 배수이다.

 

합동에서의 나눗셈 (Division in Congruence)

ab(modm)이면 cacb(modm)임을 위에서 설명했다.

그렇다면 그 역도 성립하는가? cacb(modm)ab(modm) ??

NO! 그렇지 않다.

2421(mod6)이지만 41(mod6)이다.

다음이 성립한다.

cacb(modm)ab(modmd), d=gcd(c,n)

 

따라서, collorary로 m이 소수인 경우에는 gcd(p,c)=1이므로 다음이 성립한다.

cacb(modp), and pc where p is primeab(modp)

 

그리고 항등식과 다른 성질을 갖는다. 특히,

ab0(modm)이라고해서 a0(modm)이거나 b0(modm)아니다.

반례) a=4, b=3, m=12

 

728x90
반응형