정수론 #3-1 :: 합동

Congruence

$\begin{gather*}a\equiv b\mod m \end{gather*}$

$\begin{gather*}\Leftrightarrow m|(a-b) \\ \Leftrightarrow a-b=km \end{gather*}$

 

정의 : a와 b가 m으로 나눈 나머지가 같다.

“a and b are congruent modulo m”

 

---

 

Properties

1번

$\begin{gather*}a \equiv b, c \equiv d \mod m \ \ \ \Rightarrow \ \ \ a\pm c \equiv b\pm d \mod m \end{gather*}$

 

증명)

$\begin{gather*}m|(a-b), \ \ \ \ m|(c-d) \\ \Rightarrow m|\{(a-b)+(c-d)\} \\ \Rightarrow m \ \ divides \ \ (a-b) + (c-d) = (a+c)-(b+d) \\ \Rightarrow \ \ \therefore a+c \equiv b+d \mod m \end{gather*}$

 

 

2번

$\begin{gather*}a \equiv b, c \equiv d \mod m \ \ \ \Rightarrow \ \ \ ac \equiv bd \mod m \end{gather*}$

 

증명)

$\begin{gather*}a-b=km, \ \ \ \ c-d =lm \\ \Rightarrow ac=(km+b)(d+lm) \\ = bd + m(bl+kd+mkl) \\ \Rightarrow ac-bd = m(bl+kd+mkl) \\ \Rightarrow ac-bd = tm \\ \Rightarrow m|(ac-bd)\\ \therefore ac \equiv bd \mod m \end{gather*}$

 

주의사항 1)

$\begin{gather*}ac \equiv bc \mod m \not\Rightarrow a\equiv b \mod m \end{gather*}$

ac와 bc의 공통인수 c를 함부로 나누지 말것.
(거꾸로는 성립!!)

ex)

$\begin{gather*}3*7 \equiv 4*7 \mod 7 \Rightarrow 3\not\equiv4 \mod 7 \end{gather*}$

주의사항 2)

$\begin{gather*}ab \equiv 0 \mod m \not\Rightarrow a\equiv0 \mod m, \ \ or \ \ b\equiv0 \mod m \end{gather*}$

ex)

$\begin{gather*}2*3 \equiv0 \mod 6, \\ \Rightarrow 2 \not\equiv 0 \mod 6, \ \ \ 3\not\equiv 0 \mod 6 \end{gather*}$

 

---

 

Zero divisors

$\begin{gather*}a \not\equiv0 \mod m, \ \ b\not\equiv0 \mod m \end{gather*}$

 

이지만(그리고)

 

$\begin{gather*}ab \equiv 0 \mod m \end{gather*}$

 

인 짝(a, b)를 영인자(zero divisors)라 한다.

 

ex)

$\begin{gather*}2*3 \equiv 0 \mod 6 \end{gather*}$

 

⇒ (2, 3) : 영인자

 

실수 곱에 대해서는 영인자가 없지만, 정수 곱의 합동 연산은 영인자가 있다.

즉, 영인자를 신경쓰고 합동 연산을 할 것.

 

관찰

• mod 7 연산에는 영인자가 없다.

$\begin{gather*}ab \equiv 0 \mod 7 \\ \Rightarrow 7|(ab-0) \end{gather*}$

 

7이 소수이므로 prime divisor property에 의해

 

$\begin{gather*}\Rightarrow 7|a, \ \ or \ \ 7|b \\ \Rightarrow a=7t, \ \ or \ \ b=7k \\ \end{gather*}$

 

a혹은 b 둘중에 하나는 7의 배수이므로 7로 나눈 나머지는 0.

 

$\begin{gather*}\therefore a\equiv 0, \ \ b\equiv0 \mod 7 \end{gather*}$

 

ex)

$\begin{gather*}(x-2)(x-1)\equiv0 \mod 7 \\ \Rightarrow x\equiv2, \ \ or \ \ x\equiv1 \mod 7 \end{gather*}$