정수론 | 완전 잉여계

완전 잉여계, 표준 완전 잉여계

집합 $C=\{a_1,a_2,\cdots,a_n\}\subset Z$가 임의의 정수 $a\in Z$에 대하여 유일한 $a_i\in C$에 대하여 $a \equiv a_i \pmod{m}$을 만족하면 집합 $C$를 $m$데 대한 완전 잉여계라고 정의한다. 즉, 집합 $\{0,1,2,\cdots,m-1\}$은 $m$에 대한 완전 잉여계(complete residue system modulo m)이며 m에 대한 표준 완전 잉여계(standard complete residue system modulo m)이라고도 한다.

정리: $a,\ b$가 0이 아닌 정수라 하면 $ab\equiv0 \pmod{m}$인 경우, $\gcd(a,m)\ne 1\ or \gcd(b,m)\ne 1$이다.

[증명] $ab\equiv 0\ \pmod{m}$이라 하면 정수 $x$가 존재하여 $ab=mx$라고 표현할 수 있다. 따라서 $m|ab$이다.

정리: $p$는 소수이고 $C= \{0,1,2,\cdots,p-1\}$는 $p$에 대한 표준 완전 잉여계(standard complete residue system modulo $p$)일 때, $a,\ b\in C$이고 $ab\equiv0 \pmod{p}$라고 하면 $a=0\ or\ b=0$이다.

[증명] 대우명제를 사용하여 증명할 수 있다. $a,b\in C$이고 $a\ne 0\ and\ b\ne0$이면 $ab\not \equiv0 \pmod{p}$라 하자. $p$는 소수이므로 $\gcd(a,p)=\gcd(b,p)=1$임에 따라 $\gcd(ab,p)=1$이다. 따라서, $ab\not \equiv 0 \pmod{p}$가 된다.

참고사항 해당 정리는 집합 $C$의 원소에 대해 $a+b,\ ab \pmod{p}$라고 연산을 정의하면 덧셈과 곱셉연산의 규칙을 동일하게 가지면서 $p$개의 원소로 표현되는 새로운 연산구조체계를 구성할 수 있다. 이를 갈루아 체라고 부른다.

참고사항 체란 대수학적 개념으로 사칙연산과 일반적 산술 개념의 규칙을 만족하는 대수적 구조를 의미한다. 즉, 갈루아체(유한체라고도 한다)란 일반적으로 우리가 다루는 원소가 무한한 공간이 아닌 유한개의 원소로 표현되며 기존에 우리가 사용하는 연산규칙을 그대로 적용할 수 있는 구조라고 이해하면 되겠다.

정의: $ax\equiv1 \pmod{m}$일 때, 정수 $x$를 정수 $a$의 역원(inverse of a)이라 부른다.

$ay\equiv1 \pmod{m}$이면 $x\equiv y \pmod{m}$이 된다.

정리: 방정식 $ax\equiv1 \pmod{m}$의 해가 유일하게 존재할 필요충분조건은 $\gcd(a,m)=1$이다.

[증명] $ax\equiv 1 \pmod{m}$라 하면 $ax=km+1$을 만족하는 정수 $k$가 존재한다. $\gcd(km+1,km)=1$이기 때문에 $\gcd(a,m)=1$이다. 그리고 $\gcd(a,m)=1$이라 하면 $ax+my=1$을 만족하는 $x,\ y$가 존재하여 역원인 $x$의 존재성을 증명할 수 있다. $ax-1=my$이므로 $ax\equiv1 \pmod{m}$이다.

$a$의 역원 $x$의 유일성을 증명하기 위해 전제를 부정하자. $x'$도 $m$을 법으로 하는 합동식에 대한 $a$의 역원이라고 하여 $ax\equiv ax'\equiv 1 \pmod{m}$이 된다. $ax\equiv 1$에 $x'$을 곱하면 $axx'\equiv x' \Rightarrow (ax')x\equiv x'$가 되어 $x\equiv x' \pmod{m}$이다. 즉, $x=x'+mt\ (t\in Z)$

만약 $\gcd(a,m)=d$라 하자. 디오판토스 방정식을 만족하기 위한 일반해는 $x=x_0+\cfrac{m}{d}t\ (t\in Z)$이다. 그리고 집합 ${x_0,\ x_0+\cfrac{m}{d},\cdots,\ x_0+\cfrac{m(d-1)}{d}}$은 법 $m$에 대해 서로 합동관계가 아니다. 그 외 모든 $x$ 값들은 해당 집합의 적어도 1개의 원소와 합동관계가 성립된다.

$x=x_0+\cfrac{m}{d}t\ (t=qd+r,\ 0\le r<d)$가 또 다른 해라고 하면 $x_0+\cfrac{m}{d}(qd+r)=x_0+qm+\cfrac{m}{d}r\ (0\le r < d)\equiv x_0 \pmod{m}$이다. 따라서, 법 $m$에 대한 합동식의 역원을 구하는 방정식의 해는 $\{x_0, x_0+\cfrac{m}{d},\cdots ,\ x_0+\cfrac{d-1}{d}m\}$집합의 원소들이므로 $\gcd(a,m)=d$인 경우 방정식의 해는 d개이지만 $\gcd(a,m)=1$일 경우 집합의 원소는 1개만 존재할 수 있다. 그러므로 방정식 $ax\equiv 1\pmod{m}$의 해가 유일하게 존재할 필요충분 조건은 $\gcd(a,m)=1$이다.

정리: 집합 $C$가 소수 $p$에 대한 표준 완전 잉여계라면 임의의 $a\in C\ (a\ne0)$에 대하여 $ab\equiv1 \pmod{p}$를 만족하는 $b\in C$가 유일하게 존재한다.

[증명] 소수 $p$에 대한 표준 완전 잉여계라면 집합 $C$는 $\{0,1,2,\cdots,\ p-1\}$이다. 증명을 위해 임의의 $a\in C$에 대해 소수 $p$를 법으로 하는 합동식의 역원 $b$가 존재하며 그 값이 유일함을 증명하면 된다. $\gcd(a,p)=1$이므로 $ab+pm=1$을 성립하게 하는 $b,m$값이 존재한다. 그리고 $b$는 집합 $C$에 속할 수 밖에 없다.($\because b$가 $b\le p$인 모든 값들은 $p$를 법으로 집합 C의 모든 원소와 대응되게 때문) 그러므로 역원이 존재한다.

그리고 유일성을 증명하기 위해 $a\cdot(1,\ 2,\cdots,\ p-1)$이 서로 $p$에 대해 합동이 아님을 증명하면 된다. $i,j\in C$에 대해 $ai\equiv aj \pmod{p}$라 하면 $p|a(i-j)$이다. 그런데 $\gcd(a,p)=1$임을 이미 알고 있으므로 $p|i-j$여야 하는데 이는 완전 잉여계의 정의에 어긋나므로 모순이다. 따라서, $a\cdot(1,2,\cdots p-1)$은 소수 $p$에 대해 집합 $C=\{1,2,\cdots,\ p-1 \}$과 일대일 대응이 되어 유일성이 증명된다.

정리: 소수 $p$와 $p$에 대한 표준 완전 잉여계인 집합 $C$에 대해 $x^2\equiv 1 \pmod{p}$이면 $x\equiv 1$ 또는 $x\equiv -1 \equiv p-1 \pmod{p}$이다.

[증명] $x^2\equiv 1 \pmod{p}$라 하면 $x^2-1\equiv 0 \pmod{p}$이다. 따라서 $x-1\equiv0\ or\ x+1\equiv 0 \pmod{p}$이다. 정리하면 $x\equiv1\ or -1\pmod{p}$이다.

윌슨의 정리(Wilson's Theorem)

정리: $p$가 소수이면 $(p-1)!\equiv -1 \pmod{p}$이다.

집합 $C=\{0,1,2,\cdots,p-1\}$은 $p$에 대한 표준 완전 잉여계이며 $a\in C\ (a\ne0)$에 대해 $ab\equiv1 \pmod{p}$를 만족하는 $b\in C$가 유일하게 존재한다. 그리고 $1^2\equiv(p-1)^2\equiv 1 \pmod{p}$이다. 따라서, 정수 $2, \cdots,\ p-2$에 대해 $2\cdot3\cdots p-3\cdot p-2\equiv 1 \pmod{p}$가 성립하며($\because$ 2를 제외한 소수는 항상 홀수이므로 항상 짝수개가 서로 대응된다.) 양변에 제외했던 수를 곱하면 $1\cdot2\cdot3\cdots p-1\equiv -1 \pmod{p}$이다.

예제: $\frac{66!}{17}$을 $67$로 나눈 나머지를 구하라.

$66!\equiv -1 \equiv 66 \pmod{67}$이다. 그러므로 $65!\equiv 1\equiv 68 \pmod{67}$이다. 양변을 $17$로 나누면 $\cfrac{65!}{17}\equiv 4 \pmod{67}$이고 양변에 $66\equiv -1 \pmod{67}$을 곱하면 $\cfrac{66!}{17}\equiv -4 \pmod{67}$이다. 따라서 나머지는 63이 된다.

예제: $\frac{1}{1}+\frac{1}{2}+\cdots+\frac{1}{25}=\frac{n}{25!}$을 만족하는 양의 정수 $n$을 13으로 나눈 나머지를 구하여라.

양변에 $25!$을 곱하면 $n=25!\cdot(\cfrac{1}{1}+\cfrac{1}{2}+\cdots+\cfrac{1}{25})$이다. 그리고 문제에서 13으로 나눈 나머지를 구하라고 하였으므로 각 인수에 13의 인수가 있는지 확인해야 한다. 즉, 분모에 13의 인수가 없다면 13으로 나눈 나머지는 0이 되기 때문에 $n=25!\cdot(\cfrac{1}{1}+\cfrac{1}{2}+\cdots+\cfrac{1}{25})\equiv 25!\cdot \cfrac{1}{13}$이다. $(1\cdot2\cdot3\cdots11\cdot12)\cdot(14\cdot15\cdots24\cdot25)$은 13을 기준으로 $(1\cdot2\cdot3\cdots11\cdot12)\cdot(1\cdot2\cdot3\cdots11\cdot12)$과 합동이므로 $n\equiv(12!)^2 \pmod{13}$으로 표현할 수 있다. $12!\equiv -1 \pmod{13}$이므로 $n\equiv (12!)^2 \equiv (-1)^2=1\pmod{13}$이 되어 나머지는 1이 된다.

작성에 도움이 된 자료

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