[정수론] 합동 (Congruence) 2부. 선형합동식(linear congruence) 과 역원
Math/Numbers/Combinatorics2008. 4. 19. 23:27 |
미지수 한개인 선형방정식은 ax + b = 0 꼴이다. 머, ax = b 이렇게 써도 마찬가지다.
이걸 합동식으로 쓰면 ax ≡ b (mod m ) 이다. 이것을 리니어 컨그루언스 라고 한다. ( 언노운은 1개 )
ax = b 는 그냥 양변을 a 로 나누면 되지만, 합동식에서는 나누기가 없다.
우선 곱에 대한 항등원과 역원을 생각해보자. 항등원은 당연히 1 이다. 따라서, 곱해서 나머지가 1 이되는 녀석이 곱에 대한 역원이다.
여기서는, a 의 역원을 a 위에 bar 를 얹어서 나타내기로 하자.
이제, ax ≡ b (mod m ) 와 같은 합동 방정식이 주어졌다면, 양변에 a 의 역원을 곱하므로써, 좌변엔 x 만 남길수 있고, 따라서 우리는 이 방정식을 푼것이 될 것이다. 그.러.나 !
그것은 때때로 여러개의 해를 갖기도 한다. 그럴땐 위와 같은 방법으로는 고작 하나의 해만 구해진다. 따라서, 위와 같은 방법은 별로 좋은 방법은 아니다. 게다가 역원이 존재하지 않는 경우도 있다.
예를들어, mod 15 에 대한 12 의 역원을 구해보라. ( 즉 12 에 몇을 곱하면 15 로 나누었을때, 나머지가 1 이 되겠는가? )
자, 이제 다시 처음의 문제로 돌아가서, 언제 해가 구해지는지, 또 유일하게 결정되는지 등을 조사해볼 것이다.
( 이것은 위의 역원에 대한 문제보다 더 포괄적이므로, 역원의 문제를 포함한다. )
선형 합동식의 해에 대한 정리.
존재증명.
( ax - b ) = m k for some x , k 즉, ax - mk = b 이고 이것은 디오판투스 방정식이다.
그러므로, 해의 존재는 (a,m) | b 를 나누는가 와 동치이다. ( 참고 : http://sciphy.tistory.com/1304 )
해의 개수 증명.
디오판투스 방정식 ax - mk = b 의 주어진 해에 대해, m / (a,m) , a / (a,m) 을 더해도 해가 된다. ( 부호가 반대로 둘다 반대로 바꾸면 상관없다.)
우리의 미지수는 x 이므로, m / (a,m) 을 몇번 더하면, mod m 에 대해서 순환하는가를 보면 해의 개수가 나온다.
m / (a,m) 을 (a,m) 번 더하면 결국, m 을 더하게 되므로, mod m 에 대해서 0 을 더하는 것과 같다. 따라서, 해의 개수는 (a,m) 개이다.
위 정리의 결과들.
(a,m) = 1 이면 항상 그리고 유일하게 해가 존재한다. 1은 b 가 무엇이든 나눌것이고, 해의 개수는 (a,m) = 1
역원이 존재하려면, (a,m) = 1 이어야 한다. 1 을 나눌수있는 수는 1밖에 없으니까...
그러므로, 위에서 구해보라고 했던, mod 15 에 대한 12 의 역원은 존재하지 않는다. ( 서로소가 아니므로... )