01. 합동(Congruence)

● 정의
- a,b를 m으로 나눈 나머지가 같을 때, a와 b가 m에 관하여 합동이라고 하고 a≡b(mod m)으로 나타낸다.

●modular연산
a≡b(mod m)
1. a를 m으로 나눈 나머지와 b를 m으로 나눈 나머지가 같다.
2. a = x*m + b (x는 임의의 정수)

● 합동의 기본 성질
- a≡b(mod m)이고, c≡d(mod m)라면 ( a=m*x1+r1, b=m*y1+r1, c=m*x2+r2, d=m*y2+r2 )
1. a+c≡b+d(mod m)
※ 증명
① a+c = (m*x1+r1) + (c=m*x2+r2) = m(x1+x2) + r1+r2
② b+d = (m*y1+r1) + (c=m*y2+r2) = m(y1+y2) + r1+r2
∵ a+c와 b+d는 모두 m의 배수이며, r1+r2의 값을 나머지로 갖는다.
2. a*c≡b*d(mod m)
※ 증명
위의 증명처럼 a,b,c,d에 각각 대응 되는 수식(ex, a=m*x1+r1 을 넣고 계산해보면 된다.)
3. a*n≡b*n(mod m)
※ 증명
① a*n = n(x*m + b)
② a*n = x*m*n + b*n
∵ a*n은 m의 배수이며, b*n의 값을 나머지로 갖는다.