Number Theory - 4.1, 4.2 합동의 기본 정리
합동의 정의
Definition 4.1
양의 정수 $n$이 $a-b$를 나누면, 즉, $a-b = kn$ 이면,
두 개의 정수 $a$와 $b$를 법modular $n$에 대해 합동 congruent modulo 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$이 남는다.
$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}$
합동식에서의 공통인수 소거
합동식에서는 공통인수를 바로 소거할 수 없다.
에서 역은 성립하지 않는다는 의미이다.
하지만 소거할 수 있는 조건이 있다.
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$
Comments