Number Theory with Code - 4. Congruence

정수 $n$의 나머지 동네를 공부한다. 시계를 볼 줄 안다면, 12에 관한 나머지 동네를 이해한거다.

congruence $$ a \equiv b \;(mod \; n) \Leftrightarrow n \;|\; b-a \Leftrightarrow \exists k \in \mathbb{Z} : nk=b-a $$ 세 가지 표기법을 마구 오갈 것이니 숙지해두자.

$a \equiv b \;(mod \; n)$ 일 때, $a,b$를 $n$에 관해서 합동(congruent)이라고 한다.

기본적인 성질들을 정리하자.

Let a,b,c be integers. Then

1. $a \equiv a \; (mod \;n)$
2. $a \equiv b \Leftrightarrow b \equiv a$
3. If $ a \equiv b (mod \; n)$ and $b \equiv c (mod \; n)$, then $a \equiv c (mod \; n)$.
4. If $c\in \mathbb{Z}$ and $ a \equiv b (mod \; n)$, then $ ac \equiv bc (mod \; n)$.

마지막 성질만 증명한다. $ a \equiv b (mod \; n)$는 $\exists k \in \mathbb{Z} : nk=b-a$ 이므로 $ nk \cdot c = bc-ac $ (혹은 $n |bc-ac$)이고 결국 $ ac \equiv bc \; (mod \; n) $이다.

Suppose that $ a \equiv b \; (mod \;n)$ and $ c \equiv d \; (mod \;n)$. Then

5. $a+c \equiv b+d \; (mod \; n)$
6. $a-c \equiv b-d \; (mod \; n)$
7. $ ac \equiv bd \; (mod \; n)$

이번에도 마지막 것만 증명한다. 다음 식이 모두 설명해준다. $$ bd-ac=bd-bc+bc-ac=b(d-c)+(b-a)c $$ 4번 성질에 의해 $ n | b(d-c) $ 이고 $n | (b-a)c$이므로 $$ n\;|\; bd - ac \Leftrightarrow bd \equiv ac \; (mod \; n) $$ 를 얻는다.

동네가 조성되면 그 위에서 함수를 생각하는 것이 기본이다.

$f$가 정수 계수 다항식이면 위의 성질들에 의해 $$ a \equiv b \;(mod \; n) \Rightarrow f(a) \equiv f(b) \; (mod \; n) $$ 이 성립한다.

0이 모든 수의 배수임을 기억하자. $f$가 정수 계수 다항식일 때, $f(x)=0$이 정수해를 가지면 $$ \forall n \in \mathbb{Z} , \; f(x) \equiv 0 \; (mod \; n) $$ 이 정수해를 가지게 된다.

위 명제의 대우를 생각하자. 어떤 $n$에 대해 $f(x) \equiv 0 \; (mod \; n)$이 해가 없음을 보이면, 방정식 $ f(x)=0 $은 정수해를 가질 수 없다!

더 일반화해서 $f(x_1, x_2, \cdots, x_n)=0$ 역시 마찬가지이다.

다음 방정식 $$ x^2-4y^2=2 $$ 의 정수해가 존재하지 않음을 이제 보일 수 있다. 4에 관한 나머지의 동네에서 생각하면 된다.

나머지 동네를 부르는 공식적인 명칭이 등장한다.

완전잉여계(complete residue system)

잉여(residue)는 나머지를 일컫는다. $n$으로 나눈 나머지는 $$0,1,\cdots, n-1$$ 중의 하나일 것이다.

위를 표준으로 해서 합동이라는 측면에서 위와 동등한 $n$ 개의 정수의 집합을 완전잉여계라고 부른다. 조금 형식을 갖추어 다시 쓰면 다음과 같다.

임의의 정수 $x$를 $n$으로 나눈 나머지가 $$r_1, r_2,\cdots, r_n$$ 중의 하나와 합동이고 오직 하나와 합동일 때, $r_1, r_2,\cdots, r_n$ 를 $n$ 에 관한 완전잉여계라 한다.

예를 들어 $$ -5, -4, \cdots, 0, 1, \cdots, 6 $$ 은 12의 완전잉여계이고, $$ 30, 101, -2 $$ 는 3의 완전 잉여계가 된다.

동네와 그 위에서 정의된 연산이 잘 정의되면, 다음으로 생각할 것은 방정식이다.

초등학교 시절 사칙 연산을 배우고 나면 다음과 같은 질문을 받게 된다.

'3에 무엇을 곱하면 21이 될까?' 혹은 '2배하면 13이 되는 수를 구하라.'

생각해보면 역원(inverse)가 핵심적인 역할을 했던 것 같다.

Arithmetic Inverse of modulo n

Let $a$ be and integer. $a^*$ is an arithmetic inverse of modulo n if it satisfies that $$ a^* a \equiv 1 \; (mod\; n). $$

그런데, 나머지 동네는 역원을 항상 제공하지는 않는다.

$a$ has an arithmetic inverse $a^*$ modulo $n$ iff $\gcd(a,n)=1$.

'최대공약수'라는 단어가 나오면 일차결합부터 떠올려야 한다. $$ \gcd(a,n)=1 \Leftrightarrow \exists x,y \in \mathbb{Z} : ax+ny=1 $$ 따라서, $ax \equiv 1 \; (mod \; n)$ 이므로 $a^*=x$ 로 두면 된다.

이제 역원이 있으면 소위 '나눗셈'을 할 수 있게 된다.

Suppose that $\gcd(a,n)=1$ and that $ax \equiv ay\; (mod\;n)$. Then $$x\equiv y\;(mod\;n).$$

$a$와 $n$에 따라서 역원이 없을 수 있음을 염두에 두고 있어야 한다.

Suppose that $\gcd(a,n)=d$ and $ax \equiv ay\; (mod\;n)$. Then $$ x\equiv y \; (mod\; \frac{n}{d}).$$

마침내 일차방정식 이야기를 할 수 있게 되었다.

The congruence(or the equation) $ax \equiv b\;(mod\;n)$ has a solution iff $$ \gcd(a,n) \;|\;b .$$