정수론에서의 합동
a ≡ b mod m
정수 a, b를 m으로 나눈 나머지가 같을 때(modulo 연산), a와 b는 m에 대해서 합동이다.
합동식의 성질
a±c ≡ b±c mod m
ac ≡ bc mod m
정수 a, b가 합동일 때, 양변에 덧셈, 뺄셈, 곱셈을 취해도 성립한다.
나눗셈은??
합동식에서 곱셈의 역원이 존재할 때, 가능하다.
항등원과 역원
항등원: 임의의 연산 *에 대해서 a*e = e*a = a 를 만족하는 원소 e
연산 +(덧셈)의 항등원은 0
연산 X(곱셈)의 항등원은 1
역원: 원소 a의 연산 *에 대해서 재귀 시키는 원소
5의 +(덧셈)에 대한 역원은 -5
5의 X(곱셈)에 대한 역원은 1/5
a의 곱셈에 대한 역원이 존재하지 않는 경우가 발생한다면, 그 경우 나눗셈은 정의할 수 없다.
a=0 일 때, a의 곱셈에 대한 역원은 존재하지 않는다.
따라서 0으로 나누기는 정의하지 않는다.
modulo 식에서 곱셈에 대한 역원을 찾기 위해서는 일일히 대입해봐야 한다(찾기 쉽지 않다).
mod 9에 대해서, 5의 항등원: 1
mod 9에 대해서, 5의 역원:
5xA ≡ 1 mod 9 를 만족하는 Amod 9이기 때문에 A={0, 1, 2, ..., 8}를 대입해보면 찾을 수 있고 결과적으로 A=2 이다.
역원의 유일성은 항상 보장되어 있다. (A=2 이외의 값은 역원이 아니다)
modulo 식에서 곱셈에 대한 역원을 찾지 못하는 수 A에 대해서, 어떤 수도 다음 식을 만족하지 못한다.
Ax(역원) ≡ 1 mod 9
따라서 A의 역원은 존재하지 않는다.
곱셈의 역원이 존재할 조건
A x A^(-1) ≡ 1 mod m
위의 식을 만족시키는 A^(-1)이 존재한다면 역원이 존재한다.
A의 역원을 x라고 했을 때,
Ax ≡ 1 mod m
Ax = mK + 1
Ax - mK = 1
위와 같은 형태가 된다.
베주 항등식에 의해서 두 정수 A, M의 gcd(A, M)=D 일 때, Ax+My=D 를 만족하는 (x, y) 쌍은 무조건 존재한다.
따라서 위의 식을 만족하려면 A와 m의 gcd(A, m)=1 이어야 한다.
결론적으로 역원이 존재하기 위해서는 A와 m이 서로소여야 한다.
