정수론 | 합동식(Congruence)

합동식이란

고정된 양의 정수 $m(\ne1)$에 대하여, 두 정수 $a,\ b\in Z$가 $m|a-b$를 만족하면 정수 $a,\ b$는 정수 $m$을 법으로 한 합동(Congruent modulo m) 또는 합동식이라 부르고 기호로는 $a\equiv b\ \pmod{m}$으로 표시한다.

정리: 고정된 양의 정수 $m$에 대하여 다음과 같은 합동식이 성립한다.

1. $a \equiv a\ \pmod{m}\quad \forall\ a\in Z$
2. $a\equiv b\ \pmod{m} \Rightarrow\ b\equiv a\ \pmod{m}$
3. $a\equiv b\ \pmod{m},\ b \equiv c\ \pmod{m} \Rightarrow\ a\equiv c\ \pmod{m}$

정리: 합동식의 연산법칙

1. $a\equiv b\ \pmod{m},\ c\equiv d\ \pmod{m}$이면

   • $a+c\equiv b+d\ \pmod{m}$
   • $a\cdot c \equiv b\cdot d\ \pmod{m}$, $a^k\equiv b^k\ \pmod{m},\ \forall k\in N$

   [증명] $a\equiv b\ \pmod{m},\ c\equiv d\ \pmod{m}$이므로 $a-b=k_1m,\ c-d=k_2m$을 만족하는 정수 $k_1,\ k_2$가 존재한다.

   • $(a+c)-(b+d)=(a-b)+(c-d)=(k_1+k_2)m$이므로 성립한다.
   • $ac-bd=ac-ad+ad-bd=a(c-d)+d(a-b)=ak_2m+dk_1m$이므로 성립한다.

2. $ab\equiv ac\ \pmod{m},\ gcd(a,m)=d$이면 $b\equiv c\ (mod\ \cfrac{m}{d})$이고 $gcd(a,m)=1$이면 $b\equiv c\ \pmod{m}$이다.

   [증명] $ab\equiv ac\ \pmod{m}$이므로 $ab-ac=ym$을 만족하는 정수 $y$가 존재한다.

   • $a(b-c)=ym$에서 양변을 $d$로 나누면 $\cfrac{a}{d}(b-c)=y\cfrac{m}{d}$이다. 즉, $\cfrac{m}{d}|\cfrac{a}{d}(b-c)$이고 $gcd(\cfrac{m}{d},\cfrac{a}{d})=1$이므로 $\cfrac{m}{d}|(b-c)$가 된다.

정리: $S\equiv a\ \pmod{m},\ S\equiv a\ \pmod{n},\ gcd(m,n)=1$이면 $S\equiv a\ \pmod{mn}$

[증명] 주어진 식에 따라 $m|S-a,\ n|S-a$이다. $gcd(m,n)=1$이므로 $mn|S-a$이다.

예제: $2^{2^{1989}}+1$의 일의 자리 수를 구하여라.

$2^4\equiv 6\ (mod\ 10)$이고 $2^{1989}=4\cdot 2^{2^{1987}}$이므로 $2^{2^{1989}}=(2^{4})^{2^{1987}}\equiv 6\ \pmod{10}$이 된다. 그러므로 주어진 식의 일의 자리 수는 7이다.

예제: $77|36^{36}+41^{41}$이 성립함을 보여라.

$41\equiv (-36)\ \pmod{77}$이므로 주어진 식을 $36^{36}+(-36)^{41}$로 치환할 수 있다. 정리하면 $36^{36}(1-36^5)$이다. $36\equiv 1\ \pmod{7},\ 36\equiv 3\ \pmod{11}$이므로 $36^2\equiv 9\ \pmod{11},\ 36^3\equiv 5\ \pmod{11}$이 된다. $36^5\equiv 1\ \pmod{11}$이므로 $36^5\equiv 1\ \pmod{77}$이 된다. $\therefore 1-36^5\equiv1-1=0\ \pmod{77}$

예제: $5^{(2^k)}$을 $2^{1000}$으로 나눈 나머지가 1이 되도록 하는 양의 정수 $k$ 중 가장 작은 것을 구하여라.

$2^{1000}|5^{(2^k)}-1$을 만족하는 가장 작은 양의 정수를 구해야 한다.

• $k=1$ 일 때, $5^2-1$이고 $2^3|5^2-1$이 성립한다.
• $k=2$ 일 때, $5^4-1$이고 인수분해하면 $(5^2+1)(5+1)(5-1)$이 된다. 그리고 $2|5^2+1$이므로 $2^4|5^4-1$이 성립한다.
• $k=3$ 일 때, $5^8-1$이고 인수분해하면 $(5^4+1)(5^2+1)(5+1)(5-1)$이다. 동일한 방법으로 $2^5|5^8-1$이 성립한다.
• $k=l$ 일 때, $5^{(2^l)}$은 $2^{l+2}$로 나누어 떨어짐을 알 수 있다.

따라서 주어진 조건을 만족하는 가장 작은 양의 정수는 998이다.

예제: $a^4+a^2+1$이 13의 배수가 되도록 하는 30 이하의 자연수 $a$값들의 합을 구하여라.

$a^4+a^2+1=a^4+a^2-12+13=(a^2+4)(a^2-3)+13\equiv 0\ \pmod{13}$을 만족해야 한다.

• $a^2+4\equiv 0\ \pmod{13}$인 경우

  $a^2\equiv 9\ or\ -4$여야 하므로 $a\equiv 3\ or\ -3\ (mod\ 13)$의 형태를 갖는다. 따라서, 만족하는 수는 3, 10, 16, 23, 29이다.

• $a^2-3\equiv 0\ \pmod{13}$인 경우

  $a^2\equiv3\ \pmod{13}$의 형태를 가져야 하므로 $a\equiv 4\ or\ -4$의 형태를 갖는다. 따라서, 만족하는 수는 4, 9, 17, 22, 30이다.

만족하는 값들을 모두 더하면 163이다.

예제: 자연수 $n$에 대하여 $1^n+2^n+3^n+4^n$을 십진법으로 표시했을 때, 일의 자리에서부터 연속하여 나오는 0의 개수를 $f(n)$이라 하자. $f(n)$의 최댓값을 구하여라.

주어진 식을 $g(n)$이라 하자.

• $g(1)=10$이므로 $f(1)=1$
• $g(2)=30$이므로 $f(2)=1$
• $g(3)=100$이므로 $f(3)=2$

$f(n)=3$이 되려면, $g(n)$은 1000으로 나누어져야 한다. 그리고 1000은 8의 배수이므로 $8|g(n)$을 만족해야 한다. $2^n,\ 4^n$은 8의 배수이지만, $1^n,\ 3^n$은 8의 배수가 아니므로 이후의 값에 대해서도 1000의 배수는 존재하지 않는다. 따라서 최댓값은 2이다.

예제: 양의 정수 $n$의 모든 자리 수의 합을 $a(n)$이라 하자. 모든 자리의 수가 홀수인 세 자리 양의 정수 $n$ 중, $a(n)=a(2n)$을 만족하는 것의 개수를 구하여라.

[참고사항] 모든 자리 수의 합은 해당 수를 9로 나눈 나머지와 같다. ($\because\ 10^k\equiv 1\ \pmod{9}$이므로 $a\cdot10^2+b\cdot10+c\equiv a\cdot1+b\cdot1+c\ \pmod{9}$)

$a(n)\equiv n\ \pmod{9},\ a(2n)\equiv 2n\ \pmod{9}$이므로 주어진 조건이 성립되려면 $n\equiv 2n\ \pmod{9}$을 만족해야 한다. 따라서, $n\equiv0\ \pmod{9}$이다.

• $a(n)=9$일 때, 만족하는 순서쌍은 $(1,1,7),\ (1,3,5),\ (3,3,3)$이다.
• $a(n)=18$일 때, 모든 자리의 수가 홀수인 조건을 만족하지 못한다.
• $a(n)=27$일 때, 만족하는 순서쌍은 $(9,9,9)$이다.

따라서, 만족하는 조합의 개수는 3+6+1로 10이다.

예제: 양의 정수 $n$에 대하여 $f(n)$은 완전제곱이 아닌 양의 정수 중 $n$ 번째 수라 하자, 예를 들어, $f(1)=2,\ f(2)=3,\ f(3)=5,\ f(4)=6$이다. 이 때, $f(2010)$을 $1000$으로 나눈 나머지를 구하여라.

$f(3)=2^2+1,\ f(7)=3^2+1,\ f(13)=4^2+1$이다. 이에 대한 일반식을 세워보면 $f(k^2+1-k)=k^2+1$임을 알 수 있다. ($\because$ 완전제곱수 $k^2$이후 처음 나오는 $k^2+1$은 그 전까지의 제곱수들을 제외한 값이기 때문이다.)

따라서, $44^2\le 2010\le45^2$이고 $45^2+1$을 값으로 갖는 $f(k)$의 $k$값은 $2026-45=1981$이다. $f(2010)=f(1981)+29=2055 \equiv 55\ \pmod{1000}$이다.

예제: $2^{10}$보다 작은 양의 정수 $n$ 중 $n^{32}-1$이 $2^{10}$의 배수가 되게하는 것의 개수를 구하여라.

$n^{32}-1=(n^{16}+1)(n^8+1)(n^4+1)(n^2+1)(n+1)(n-1)$이고 문제에서 주어진 조건에 따라 $n^{32}-1$이 짝수라면 $n$은 홀수이다. $n=2k+1$이라 하면 $n^2\equiv 1\ \pmod{4}$이다. 즉, $n^2,\ n^4,\ n^8,\ n^{16}\equiv 1\ \pmod{4}$가 성립하여 주어진 식에서 $(n+1)(n-1)$이 $2^6$을 인수로 가져야 함을 알 수 있다. $2k+1$을 대입하면 $2^6|2^2k(k+1)$이고 $2^4|k(k+1)$이다. 해당 조건을 만족하려면 $k=16m\ or\ 16m-1$이 되어 $n=32m\pm1$의 형태를 만족해야 한다.

$2^{10}$보다 작은 수는 $m$의 값이 0인 경우 1, $2^5$의 경우 $2^{10}-1$이고 나머지 범위의 값의 경우 2개씩 존재하므로 $2^5\cdot 2=64$이다.

예제: 서로소인 양의 정수 $a,\ b$에 대하여, $a+b$와 $\frac{a^{2005}+b^{2005}}{a+b}$의 최대공약수가 될 수 있는 양의 정수를 모두 구하여라.

$a^{2005}+b^{2005}=(a+b)(a^{2004}b^0-a^{2003}b^1+\cdots+a^0b^{2004})$이고 $b\equiv (-a)\ (mod\ a+b)$이므로 치환하면 $(a+b)(a^{2004}+a^{2004}+\cdots+a^{2004})$가 된다. 따라서 $\cfrac{a^{2005}+b^{2005}}{a+b}\equiv2005\cdot a^{2004}$이다.

$gcd(a+b,a)=gcd(a,b)=1$이므로 $gcd(a^{2004},a+b)=1$ 이 되어 $ gcd(a+b,2005\cdot a^{2004})=gcd(a+b,2005)$이다. $2005=5\cdot401$이므로 최대공약수로 가능한 값은 1, 5, 401, 2005이다.

작성에 도움이 된 자료

• KMO 수학경시 정수론, 장환수학, 임장환 저