정수론 #3-3 :: 역원

gcd(a, m)=1인 경우 ax ≡ c mod m은 유일한 해만 존재한다.

gcd = 1이므로 당연히 해 1개. (ax - my = c)

⇒ 마치 나눗셈이 가능한 것처럼 이해 가능. (실제로 나눗셈이 가능한 건 아님!!)

 

$\begin{gather*}7x \equiv 1 \mod 15 \\ \Rightarrow x \equiv 1 *\frac{1}{7} \mod 15 \\ \Rightarrow x \equiv 13 \mod 15 \\ \Rightarrow \frac{1}{7} \equiv 13 \end{gather*}$

 

$\begin{gather*}7x\equiv2 \mod 15 \\ \Rightarrow x\equiv 2*\frac{1}{7} \mod 15 \\ \Rightarrow x \equiv 2*13 \mod 15 \\ \Rightarrow x \equiv 26 \mod 15 \\ \therefore x \equiv 11 \mod 15 \end{gather*}$

 

위처럼 역원을 사용하여 모든 x를 계산할 수 있다. (이때 x는 유일하다.)

 

---

 

Inverse of a mod #

p가 소수일 때, a와 p가 서로소라면 (a ≠ 0 mod p)

ax ≡ c mod p는 유일한 해가 있다.

 

ex) p = 7, ax ≡ 1 mod 7

a	0	1	2	3	4	5	6
x	-	1	4	5	2	3	6

a는 1부터 p-1까지만 가능하다. (그 다음부턴 mod로서 중복)
a가 0일때는 해가 없다. x ≡ 1/0이 불가능 하기 때문.
a가 1일때와 a가 p-1일때의 x는 a와 동일한 값이다. 위 예시에서 a=1, a=6이 그에 해당.
x들은 1부터 p-1내의 값을 하나씩만 가진다.

위의 x를 inverse of a mod 7이라고 한다. 각각 1/a의 기능(a의 역원)을 수행한다.

 

---

 

정의

prime p에 대하여 ax ≡ 1 mod p이 되도록하는 x를 inverse of a mod p라고 한다.

 

정리

p가 소수일 때, a !≡ 0 mod p이면 inverse of a mod p가 유일하게 존재한다.

소수가 아니라면 해가 존재하지 않는 경우도 있다.

 

증명

$\begin{gather*}\{a, 2a, 3a,...,(p-1)a\}, \ \ \ \ a\not≡ 0 \mod p \end{gather*}$

 

위와 같이 a와 p는 서로소이고 p-1개의 원소를 가지는 집합을 가정하면

모든 원소는 mod p에서 서로 다르다. 이유는 다음과 같다.

 

$\begin{gather*}ka≡la \mod p \end{gather*}$

 

위처럼 집합내에 mod p에서 같은 원소가 있다고 가정하면

 

$\begin{gather*} \Rightarrow (k-l)a ≡ 0 \mod p \\ \Rightarrow p|(k-l)a \\ \Rightarrow p|(k-l) \ \ \ \ \because p \not|a \\ \Rightarrow k≡ l \mod p \end{gather*}$

 

$\begin{gather*} 1 \le k,l \le p-1 \Rightarrow k=l \end{gather*}$

 

위에 의하여 k와 l은 동일할 수 밖에 없다. 즉, 모든 원소는 mod p에서 서로 다르다.

 

$\begin{gather*} \{1, 2, ..., p-1\} \end{gather*}$

 

$\begin{gather*} \{a, 2a, 3a,...,(p-1)a\}, \ \ \ \ a\not≡ 0 \mod p \end{gather*}$

 

따라서 위의 두 집합은 mod p에서 모든 원소가 서로 다르므로 같은 집합이라고 볼 수 있다.

 

이때 1이랑 맵핑되는 애는 ka들중 딱 하나랑만 맵핑된다. 따라서 유일하고 무조건 존재한다.

즉 , 어떤 k에 대하여 ka ≡ 1 mod p가 성립한다.

 

⇒ 소수p이면 모든 x의 계수 a에 대하여 inverse of a mod p인 x가 존재한다.