[친절한 수론 길라잡이] 8장. 합동

만일 m이 a-b를 나눌 때, a와 b가 모듈러 m에 대해 합동이다.

 

특히, a를 m으로 나눈 나머지가 r이면, a와 r는 모듈러 m에 대해 합동이다.

이떄, 나머지 r은 0 <= r < m을 만족하므로, 모든 정수들은 0과 m-1사이의 수와 모듈러 m에 대해 합동이다.

 

정해진 모듈러에 의한 합동은 여러 가지 의미에서 일반적인 방정식과 비슷하다.

 

이면,

이다.

 

그러나, 나눗셈에서 성립하는 건 아니다! 예를 들어, 15 * 2 와 20 * 2는 모듈러 10에 의해 합동이지만, 15와 20은 모듈러 10에 의해 합동이 아니다.

uv 가 0과 mod n에 대해 합동이지만, u가 0과 mod n에 합동이 아니면서, v도 0과 mod n에 합동이 아닐 수 있다.

(u = 6, v = 4, n = 12)를 생각해보자.

하지만 만일 gcd(c, m) = 1이면 합동식 ac 와 bc 는 mod m에서 합동일 때, c를 소거할 수 있다.

 

합동방정식의 풀이

합동방정식을 푸는 것은 방정식을 푸는 것과 비슷하다.

을 풀려면, 양변에서 12를 뺴고,

과 같이 정리한다. 이 결과도 좋지만, 

이 더 좋아보인다.

 

다른 예를 보자.

합동방정식 

의 해를 찾기 위해 양변에 5를 곱하면,

이다.

이므로, 

를 만족한다.

따라서 합동방정식의 해는 

이다.

 

모듈러 m의 합동방정식을 풀고싶다면, 모든 변수에 0부터 m-1사이의 값을 대입해 보면 된다.

예를 들어, 합동방정식

을 풀려면, 0부터 6까지 대입해보면 된다.

그러면, 

이란 답이 나온다. 9도 답이 될 수 있겠지만, 2와 합동이므로 같은 해나 마찬가지이다.

 

그럼, 

의 해를 구할 수 있을까?

물론, 항상 해를 가지는 것은 아니다. 좌변이 홀수이고, m이 짝수인 경우를 생각해보면, 해를 가지지 않음을 알 수 있다.

 

를 풀어보자.

22가 18x-8을 나누는 x를 찾아야 한다는 뜻으로, 18x - 8 = 22y를 만족하는 x를 찾아야 한다.

18x - 22y = 8의 해를 찾으면 된다.

다음 방정식 18u - 22v = gcd(18, 22) = 2는 해가 있다.(6장 참조)

실제로 u = 5, v = 4를 쉽게 찾을 수 있다.

 

우리가 찾고자 하는 것은 방정식의 우변이 8인 경우이므로, 양변에 4를 곱하면

18 * (5 * 4) - 22*(4*4) = 8이 된다.

따라서 18 * 20 은 8과 모듈러 22에 대해 합동이므로, x는 20과 모듈러 22에 대해 합동이다.

 

이제, 일반화된 식을 풀어보자.

m이 ax-c를 나누도록 하는 x를 찾아야 한다. 

m이 ax-c를 나눈다는 것은 어떤 정수 y에 대해 ax-c = my를 만족한다는 뜻이다.

가 정수해를 갖느냐는 것과 동치이다.

 

공식을 깔끔하게 하기 위해, g = gcd(a, m)이라 하자.

모든 ax - my모양의 수는 g의 배수여야 한다는 것을 관찰할 수 있다.

따라서 g가 c를 나누지 못한다면, ax - my = c는 해를 갖지 못하고, 합동방정식 또한 해를 갖지 못한다.

 

g가 c를 나눈다고 가정하자. 6장의 일차방정정식 정리에 의해 

au + mv = g가 해를 갖는다는 것을 안다.

유클리드 호제법을 이용하여 u = u0, v = v0의 해를 찾았다고 해보자.

g가 c를 나눈다고 가정하였으므로, c/g를 양변에 곱하면, 

 

를 얻는다.

 

즉, 

은 합동방정식의 해가 된다.

 

다른 해가 더 있을까? 

x_1이 합동방정식의 다른 해라고 해보자.

에서 m이 ax_1 - ax0을 나눈다.

 

 

다시 말해, 적당한 정수 k에 대해 

을 만족한다.

차가 m의 배수인 두 해는 모듈러 m의 합동방정식에서 같은 해로 간주하므로, k = 0, 1, ..., g-1일때, 정확히 g개의 서로 다른 해를 갖는다.

 

정수 a, c, m은 m >= 1이고 gcd(a, m) = g를 만족한다고 하자.
만일 g !| b이면, 합동방정식 은 해를 가지지 않는다.
만일 g | b이면, 합동방정식 정확히 g개의 서로 다른 해를 가진다.

모든 해를 찾으려면, 우선 일차방정식 au + mv = g의 해 (u0, v0)을 찾는다.
x0 = cu/g가  의 해가 되고, 모든 합동이 아닌 해는

과 같이 나타낼 수 있다.

 

 

주의

선형 합동방정식 정리에서 가장 중요한 경우는 gcd(a, m) = 1인 경우이다.

이 경우, 합동방정식은 단 하나의 해를 가진다.

 

 

고차 합동방정식

고차 합동방정식도 수론에서 매우 중요하다.

실수 계수의 d차 방정식은 최대 d개의 실수 해를 갖는다는 사실을 알고 있을 것이다.

그러나, 이 결과는 합동방정식에서는 성립하지 않는다.

예를 들면, 

은 0, 2, 3, 5를 갖는다.

하지만, 소수 p에 대한 합동방정식에서는 그대로 성립한다.

 

소수 p와 정수 계수의 다항식 

에 대하여 차수가 d >= 1이고 p !| a0을 만족한다면, 합동방정식 은 최대 p개의 서로 다른 해를 가진다.

(법 p에 대한 합동다항식의 근 정리)

 

위 정리를 귀류법으로 증명하려고 한다.

 

명제 가정: 소수 p에 대하여 적어도 하나의 정수 계수 다항식 F(x)가 존재하여 최고차항의 계수는 p로 나누어지지 않고 합동방정식

F(x) \equiv 0 (mod p)

는 F(x)의 차수모다 많은 서로 다른 해를 가진다.

 

그리고 r1, r2, ..., r{d+1}을 합동방정식 F(x) \equiv 0 (mod p)의 서로 다른 해라고 하자.

 

어떤 r가 주어지더라도, 차 F(x) - F(r)를 인수분해할 수 있다는 사실을 이용하려 한다.

 

 

이기 때문에 F(x) - F(r)의 각 항에 나타나는 x^i - r^i는 x-r로 나누어진다.

모든 항을 (x-r)로 묶을 수 있으므로, 

F(x) - F(r) = (x-r)(복잡한 d-1)차 다항식으로 쓸 수 있다.

F(x) - F(r) = (x-r)G(x)를 만족하는 d-1차 다항식 

을 찾을 수 있다.

 

특히 r = r1이라고 하고, F(r1) \equiv 0 (mod p)임을 이용하면, 다음의 합동식을 얻는다.

 

우리는 x = r1, ... ,r{d+1}이 F(x) \equiv 0 (mod p)의 서로 다른 해라고 가정하였다.

위에서 얻은 합동방정식에 대입하면

 

가 된다.

k >=2이면, 서로 다르다는 가정에 의해 r1 과 rk는 p에 대해 합동이 아니다.

7장의 가약성 정리에 따르면, G(rk) = 0(mod p)이다.

 

이제 r2, ... r{d+1}이 G(x) \equiv 0 (mod p)의 해가 됨을 확인하였다.

즉, G(x)는 적어도 d-1개의 서로 다른 근을 갖는 d-1차 다항식이다.

하지만, F(x)가 자신의 차수보다 많은 서로 다른 해를 가지는 다항식 중에서 가장 낮은 차수의 다항식이라는 가정에 모순이 된다.

따라서 우리의 처음 명제는 잘못된 것이고, 법 p에 대해 자신의 차수보다 많은 해를 가지는 다항식은 없다는 것을 증명하였다.

 

긍정적인 명제로 다시 쓰면, 모든 d차 다항식은 법 p에 대해 최대 d개의 해를 가질 수 있다.