Number Theory - 4.1, 4.2 합동의 기본 정리

합동의 정의

Definition 4.1

양의 정수 $n$이 $a-b$를 나누면, 즉, $a-b = kn$ 이면,

두 개의 정수 $a$와 $b$를 법modular $n$에 대해 합동 congruent modulo n 이라 하고, 다음과 같이 표현한다.

$$ a \equiv b \pmod {n} $$

예를 들어,

$a = qn + r ~\Longleftrightarrow ~ a \equiv r \pmod {n}$

로 표현할 수 있다.

완전 잉여계

$n$개의 정수 $a_1, a_2,\dots a_n$의 모임이 법 $n$에 대해 정확히 하나의 $a_k$와 합동이면, 법 $n$대한 완전잉여계라고 한다.

즉, $a_1, a_2, \dots, a_n$은 법 $n$에 대해 $0 \sim n-1$의 나머지를 하나씩 갖는다.

합동 정리

Theorem 4.1

임의의 정수 $a$와 $b$에 대해 $a \equiv b \pmod {n}$일 필요충분조건은 $a$와 $b$를 $n$으로 나누었을 때, 음이 아닌 같은 나머지를 갖는다는 것이다.

증명

$a \equiv b \pmod {n}$이면, $a=b+kn$이다.

$n$으로 나누었을 때 $b$는 나머지 $r$이 남는다.

$$ b=qn+r~(0 \le r < n) $$

$a=qn+r+kn=(q+k)n+r$이므로, $a$도 $n$으로 나누면 나머지 $r$를 갖는다.

역으로, $a$와 $b$가 $n$으로 나누었을 때 나머지가 같다고 하면,

$a=q_1n+r,~ b=q_2n+r$

$a-b=(q_1-q_2)n$이므로 $n \mid (a-b)$가 되어 다시 표현하면 $a \equiv b \pmod {n}$이다.

합동의 성질

중요한 성질들이고 더 주의해서 봐야할 것도 있다.

Theorem 4.2 합동의 성질

$(a)$ $a \equiv a \pmod {n}$

$(b)$ $a \equiv b \pmod {n}$이면, $b \equiv a \pmod n$

$(c)$ $a \equiv b \pmod n$이고, $b \equiv c \pmod n$이면, $a \equiv c \pmod n$

$(d)$ $a \equiv b \pmod n$이고 $c \equiv d \pmod n$이면 $a+c \equiv b + d \pmod n$ 그리고 $ac \equiv bd \pmod n$

$(e)$ $a \equiv b \pmod n$이면 $a+c \equiv b+c \pmod n$이고 $ac \equiv bc \pmod n$

$(f)$ $a \equiv b \pmod n$이면 모든 양의 정수 $k$에 대해 $a^k \equiv b^k \pmod n$

증명들

$(a)$ $a-a=0$이고 $n \mid 0$이므로 성립

$(b)$ $n \mid a-b$ 이므로 $a-b=kn$이고, $k’=-k$를 대입하면 $b-a$도 성립

$(c)$ $n \mid a-b$이고 $n \mid c-b$이므로 $n \mid a-b-(c-b)$ 따라서 합동식 표현으로 $a \equiv c \pmod n$

$(d)$ $n \mid a-b$이고 $n \mid c-d$이므로 $n \mid a+c-b-d$, 합동식 표현으로 $a+c \equiv b+d \pmod n$ 이다.

$a=q_1n+b$이고 $c=q_2n+d$이므로 $ac=(q_1n+b)(q_2n+d)=n(q_1q_2n+q_1d+q_2b)+bd$

정리하면 $ac-bd=nk$이므로 $n \mid ac-bd$, 합동식 표현으로 $ac \equiv bd \pmod n$

$(e)$ $(d)$에 $d$에 $c$를 넣음으로 성립

$(f)$ 귀납적으로 $a \equiv b \pmod n$이고, $a^k \equiv b^k \pmod n$일 때, $(d)$를 이용해서 양변에 $a, b$를 곱해줘도 $a^{k+1} \equiv b^{k+1} \pmod n$이 성립

예시

$2^{20}-1 \pmod {41}$를 구하라.

$2^5 \equiv 32 \equiv -9 \pmod {41}$ 이다.

양변에 $4$제곱을 하면, $2^{20} \equiv 81^2 \equiv (-1)^2 \equiv 1 \pmod {41}$

즉, $2^{20}-1 \equiv 0 \pmod {41}$

합동식에서의 공통인수 소거

합동식에서는 공통인수를 바로 소거할 수 없다.

$$ a \equiv b \pmod n \Longrightarrow ca \equiv cb \pmod n $$

에서 역은 성립하지 않는다는 의미이다.

하지만 소거할 수 있는 조건이 있다.

Theorem 4.3

만일 $ca \equiv cb \pmod n$이면, $a \equiv b \pmod {n/d},~~d=gcd(c,n)$

증명

$n \mid c(a-b)$이고 $c(a-b)=kn$이라 하자.

$c=dr, n=ds$라 할 때, $gcd(r,s)=1$

$dr(a-b)=kds$

$r(a-b)=ks$

$gcd(r,s)=1$ 이므로 유클리드 보조정리에 의해 $s \mid (a-b)$

그런데 $s=n/d$이므로 $a \equiv b \pmod {n/d=s}$ $\square$

Corollary 1

$ca \equiv cb \pmod n$이고, $gcd(c,n)=1$ 이면, $a \equiv b \pmod n$

Corollary 2

$ca \equiv cb \pmod p$ 이고 $p \in \Rho$ 이며 $p \nmid c$일 때, $a \equiv b \pmod p$

$\because gcd(p,c)=1$