이산수학 - 정수론, 나눗셈, 베주의 항등식, 유클리드 호제법, 나머지 연산, 소수와 소인수 분해, RSA 암호

1. 나눗셈 

 

a는 정수이고 b는 양의 정수라 할 때, 다음을 만족하는 유일한 정수 q, r이 존재한다.

$$a=bq+r\text{단,}0\le r<b$$

 

 

이 정리는 어떤 정수 $a$를 양의 정수 $b$로 나누면, 몫 $q$와 나머지 $r$가 존재하며, 나머지 $r$는 0 이상 $b$ 미만의 범위에 속한다는 것을 의미한다. 

예를 들어, $a=17$이고 $b=5$인 경우를 생각해보자. $a$를 $b$로 나누면 다음과 같이 나타낼 수 있다.

$$17=5\cdot 3+2$$

여기서 몫 $q=3$이고 나머지 $r=2$이다. 또한, 나머지 $r$는 0 이상 5 미만의 범위에 속한다.

(1) 약수와 배수 

a, b가 정수이고 $a\ne 0$일 때, $b=ac$를 만족시키는 정수 c가 있다면 “a가 b를 나머지 없이 나눈다” 또는 “a는 b를 정제한다” 또는 “b는 a로 나누어떨어진다”고 표현한다. 이 경우 a는 b의 약수(divisor) 또는 인수(factor), b는 a의 배수(multiple)라고 하며, 기호 $a\mid b$로 나타낸다. 만약 a가 b를 나누지 않을 때에는 기호 $a\nmid b$로 쓴다.

 

 

나누어떨어짐(divisibility)의 성질 

a를 0이 아닌 정수, b와 c를 임의의 정수라고 할 때
1. $a\mid b$이고 $a\mid c$이면, $a\mid (b+c)$이다.
2. $a\mid b$이면, $a\mid bc$이다.
3. $a\mid b$이고 $b\mid c$이면, $a\mid c$이다.

 

증명 

(1) $a\mid b$이고 $a\mid c$이면, $a\mid (b+c)$이다.

가정으로부터 $b=as$이고 $c=at$인 정수 $s,t$가 존재한다. $b+c=as+at=a(s+t)$이므로, $b+c$는 $a$로 나누어떨어진다.

(2) $a\mid b$이면, $a\mid bc$이다.

가정으로부터 $b=ad$인 정수 $d$가 존재한다. 양변에 $c$를 곱하면 $bc=adc$이고 $dc$는 정수이므로, $bc$는 $a$로 나누어떨어진다.

 

(3) $a\mid b$이고 $b\mid c$이면, $a\mid c$이다.

가정으로부터 $b=ad$이고 $c=be$인 정수 $d,e$가 존재한다. $c=be=(ad)e=a(de)$이므로, $c$는 $a$로 나누어떨어진다. $\text{Q.E.D.}$

 

 

(2) 최대공약수 

0이 아닌 두 정수 $a,b$에 대하여 $d\mid a$이고 $d\mid b$인 최대의 양의 정수 $d$를 $a$와 $b$의 최대공약수라 하고 $d=gcd(a,b)$로 표시한다.

- 공약수 (common divisor): 2개 이상의 정수에서 공통인 약수
- 0이 아닌 두 정수의 최대공약수는 유일하게 존재함.
- $gcd(a,b)\ge 1$
- $gcd(a,b)=1$인 경우, $a,b$는 서로소 (relatively prime)라고 함.

 

 

베주의 항등식 

적어도 하나는 0이 아닌 정수 $a,b$가 임의로 주어져 있다고 하자. 그러면 $gcd(a,b)=d$라고 할 때, $ax+by=d$를 만족하는 정수 $x,y$가 존재한다.

- $a,b$가 서로소 $⟺gcd(a,b)=1$
  $⟺\mathrm{\exists }x,y\in \mathbb{Z},ax+by=1$

 

 

📌 gcd(a,b) = gcd(a, a-b)임을 증명하시오. 

 

✘ 증명 : 

 

$$gcd(a,b)=d,gcd(a,a-b)=e\text{라고 하자.}$$

먼저, $d$는 $a$와 $b$의 공약수이므로 $a=md$, $b=nd$라고 둘 수 있다 ($m,n$은 정수). 

이를 통해 $a-b=md-nd=(m-n)d$가 된다. 따라서, $d$는 $a-b$의 약수이기도 하다. 즉, $d\mid (a-b)$임을 알 수 있다. 또한, $d$는 $a$와 $b$의 공약수이므로 $d\mid a$이고 $d\mid b$이다.

반대로, $e$는 $a$와 $a-b$의 공약수이므로 $a=se$, $a-b=te$라고 둘 수 있다 ($s,t$는 정수).

이를 통해 $b=a-(a-b)=se-te=(s-t)e$가 된다. 따라서, $e$는 $b$의 약수이기도 하다. 즉, $e\mid b$임을 알 수 있다. 또한, $e$는 $a$와 $a-b$의 공약수이므로 $e\mid a$이고 $e\mid (a-b)$이다.

이로써, $d$는 $a$와 $b$의 공약수이고, $e$는 $a$와 $a-b$의 공약수이므로, 다음과 같은 관계를 만족하게 된다.

$$d\le e\text{그리고}e\le d$$

따라서, $d=e$가 되어 $gcd(a,b)=gcd(a,a-b)$임을 증명할 수 있다.

 

 

유클리드 호제법 

 

최대공약수는 기원전 300년 전부터 사용했던 유클리드 호제법을 사용해서 쉽게 계산할 수 있다. 

 

$$a,b,q,r$$이 정수일 때, $$a=bq+r$$이면 $$gcd(a,b)=gcd(b,r)$$이다.

 

✘ 증명 : 

 

$gcd(a,b)=G$라 하자. 그럼 적당한 서로소인 정수 $A,B$에 대해 $a=AG$, $b=BG$가 성립한다. 이것을 $a=bq+r$에 대입하면,

$$AG=BGq+r$$

이고,

$$r=AG-BGq=G(A-Bq)$$

이다. 따라서 $G$는 $b$와 $r$의 공약수임을 알 수 있다. 

만일 $B$와 $A-Bq$가 서로소이면, 즉 $gcd(B,A-Bq)=1$이면 $gcd(b,r)=G$가 되므로 증명이 끝난다. 

이제 $gcd(B,A-Bq)=m$ (여기서 $m$은 1이 아닌 정수)라고 두면 적당한 서로소인 정수 $s,t$에 대해 $B=ms$, $A-Bq=mt$가 성립한다.

이것을 다시 $A=mt+Bq=mt+msq=m(t+sq)$로 나타낼 수 있다. 따라서, $A$와 $B$는 $m$의 배수임을 알 수 있다. 그러나 이는 $A$와 $B$가 서로소라는 가정에 모순이 된다. 

따라서 $gcd(B,A-Bq)=1$이어야 하며, 이로 인해 $gcd(b,r)=G$가 성립한다. 

결론적으로, $gcd(a,b)=gcd(b,r)$임을 증명할 수 있다.

 

알고리즘 

유클리드 호제법의 정리를 알고리즘으로 표현하면 다음과 같다. 

 

1. 만일 $b\mid a$이면 $gcd(a,b)=b$이다.

2. 만일 $b\nmid a$이면 다음과 같은 나눗셈 알고리즘을 적용한다.

$$\begin{array}{rlr}a& =bq+r& 0<r<b\\ b& =r{q}_1+r_1& 0<r_1<r\\ r& =r_1{q}_2+r_2& 0<r_2<r_1\\ r_1& =r_2{q}_3+r_3& 0<r_3<r_2\\ & ⋮\\ r_{n-2}& =r_{n-1}{q}_n+r_n& 0<r_n<r_{n-1}\\ r_{n-1}& =r_n{q}_{n+1}+0\end{array}$$

따라서 $gcd(a,b)=gcd(b,r)=gcd(r,r_1)=\cdots =gcd(r_{n-1},r_n)=r_n$이 된다.

 

 

📌 예제: 유클리드 호제법을 통해 gcd(287, 91)을 구하시오. 

 

✘ 풀이:


1. 첫 번째 단계:
$$287=91\times 3+14$$
여기서 $287$을 $91$로 나눈 몫은 $3$이고, 나머지는 $14$이다.

2. 두 번째 단계:
$$91=14\times 6+7$$
여기서 $91$을 $14$로 나눈 몫은 $6$이고, 나머지는 $7$이다.

3. 세 번째 단계:
$$14=7\times 2+0$$
여기서 $14$를 $7$로 나눈 몫은 $2$이고, 나머지는 $0$이다.

나머지가 $0$이 되었으므로, 이때의 나누는 수가 최대공약수이다. 따라서,
$$gcd(287,91)=7$$

결론:

$gcd(287,91)$은 $7$이다.

 

 

📌 예제: 24m X 15m 크기의 직사각형 바닥에 빈자리가 없도록 타일을 깔고자 한다. 동일한 크기의 정사각형 타일만 사용한다고 할 때, 유클리드 호제법을 이용하여 필요한 타일의 최소 개수를 구하시오. 

 

✘ 풀이: 

유클리드 호제법을 이용하여 24m X 15m 크기의 직사각형 바닥에 빈자리가 없도록 깔 수 있는 동일한 크기의 정사각형 타일의 한 변의 길이를 구해보자.

1. 두 수 24와 15의 최대공약수를 구한다.

   첫 번째 단계:
   $$24=15\times 1+9$$
   여기서 24를 15로 나눈 몫은 1이고, 나머지는 9이다.

   두 번째 단계:
   $$15=9\times 1+6$$
   여기서 15를 9로 나눈 몫은 1이고, 나머지는 6이다.

   세 번째 단계:
   $$9=6\times 1+3$$
   여기서 9를 6으로 나눈 몫은 1이고, 나머지는 3이다.

   네 번째 단계:
   $$6=3\times 2+0$$
   여기서 6을 3으로 나눈 몫은 2이고, 나머지는 0이다.

   나머지가 0이 되었으므로, 이때의 나누는 수가 최대공약수이다. 따라서,
   $$gcd(24,15)=3$$

2. 한 변의 길이가 3m인 정사각형 타일을 사용하여 24m X 15m 크기의 직사각형 바닥을 빈자리 없이 깔 수 있다.

3. 24m X 15m 직사각형을 한 변의 길이가 3m인 정사각형으로 나눈다.

   가로에 필요한 타일의 개수:
   $$24÷3=8$$

   세로에 필요한 타일의 개수:
   $$15÷3=5$$

4. 따라서 필요한 타일의 최소 개수는 가로와 세로에 필요한 타일 개수를 곱한 값이다.
   $$8\times 5=40$$

필요한 타일의 최소 개수는 40개이다.

 

 

 

2. 나머지 연산 

 

(1) 모듈로 합동 

a, b가 정수이고 $m$이 양의 정수일 때, $a-b$가 $m$으로 나누어떨어진다면 $a$와 $b$는 모듈로-m 합동이라고 한다. 모듈로-m 합동(congruence)은 기호로 $a\equiv b(\mathrm{mod}m)$으로 표기한다.

$m\mid (a-b)$  $\Rightarrow$ $a\equiv b(\mathrm{mod}m)$

25 - 11 = 14 = 2 $\times$ 7 $\Rightarrow$ 7 $|$ (25 - 11) $\Rightarrow$ 25 $\equiv$ 11 $(\mathrm{mod}7)$
25 = 3 $\times$ 7 + 4 and 11 = 1 $\times$ 7 + 4 $\Rightarrow$ 25 $\mathrm{mod}7=11\mathrm{mod}7$

 

 

$$a,b$$가 정수이고 $$m$$이 양의 정수라 하자. 그러면 $$a\equiv b(\mathrm{mod}m)$$은 $$a\mathrm{mod}m=b\mathrm{mod}m$$과 필요충분조건이다.

 

 

 

(2) 합동의 기본 정리 

 

$m>1$이 고정되고 $a,b,c,d$를 임의의 정수라 할 때, 다음 성질이 성립한다.

1. $a\equiv a(\mathrm{mod}m)$
2. $a\equiv b(\mathrm{mod}m)$이면 $b\equiv a(\mathrm{mod}m)$이다.
3. $a\equiv b(\mathrm{mod}m)$이고 $b\equiv c(\mathrm{mod}m)$이면 $a\equiv c(\mathrm{mod}m)$이다.
4. $a\equiv b(\mathrm{mod}m)$이고 $c\equiv d(\mathrm{mod}m)$이면 $a+c\equiv b+d(\mathrm{mod}m)$이고 $ac\equiv bd(\mathrm{mod}m)$이다.
5. $a\equiv b(\mathrm{mod}m)$이면 $a+c\equiv b+c(\mathrm{mod}m)$이고 $ac\equiv bc(\mathrm{mod}m)$이다.
6. $a\equiv b(\mathrm{mod}m)$이면 모든 양의 정수 $k$에 대해 $a^k\equiv b^k(\mathrm{mod}m)$이다.

 

 

3. 소수와 소인수 분해 

 

1보다 큰 모든 자연수는 최소한 두 개의 자연수로 나누어 떨어진다. 왜냐하면, 1보다 크 자연수는 항상 1과 자기 자신으로 나누어 떨어지기 때문이다. 어떤 자연수는 1과 자기 자신 외에는 약수를 가지지 않는데 이러한 자연수를 소수(prime)라고 한다. 

 

 

(1) 소수와 합성수 

1보다 큰 자연수 $p$는 $p$의 양의 인수가 1과 $p$뿐일 때 소수라고 한다. 1보다 크면서 소수가 아닌 자연수는 합성수라고 부른다.

- $\mathbb{N}=\{1\}\cup \{\text{소수들}\}\cup \{\text{합성수들}\}$
- 소인수: 주어진 자연수의 약수 중에서 소수인 것
- 소인수분해: 합성수를 소인수들의 곱으로 표현하는 것.

 

 

보조정리 

1. $p$가 소수이고 $p\mid ab$이면, $p\mid a$ 또는 $p\mid b$이다.
2. $p$가 소수이고 $p\mid a_1{a}_2\cdots a_n$이면, $1\le k\le n$인 $k$에 대해 $p\mid a_k$이다.
3. $p,q_1,q_2,\dots ,q_n$이 소수이고 $p\mid q_1{q}_2\cdots q_n$이라면, $1\le k\le n$인 $k$에 대해 $p=q_k$이다.

 

 

산술의 기본정리 

$$n$$이 2 이상의 자연수이면 $$n$$은 소수이거나 소수의 곱으로 유일하게 표현할 수 있다.

- Fundamental theorem of arithmetic
- 소인수분해: 합성수를 소인수들의 곱으로 표현하는 것.

$$25200=2^5\times 3^2\times 5^2\times 7^1$$
$$17640=2^3\times 3^2\times 5^1\times 7^2$$

 

 

✘ 증명: 

 

$n$은 소수 또는 합성수이다. $n$이 소수이면 주어진 정리는 참이므로 $n$이 합성수인 경우를 가정하자. $n$이 합성수이면, $1<d<n$이며 $d\mid n$인 정수 $d$가 존재한다. 이를 만족하는 정수 중에서 가장 작은 $p_1$을 선택한다면, $p_1$은 소수이어야 한다. $p_1$이 합성수라면 $p_1$의 인수 중 가장 작은 값이 아니기에 모순이다. $n=p_1{n}_1$으로 표현할 수 있고, $p_1$은 소수가 되며 $1<n_1<n$이다.

만약 $n_1$이 소수이면 $n$은 소수의 곱으로 표현되고 정리는 참이 되므로 $n_1$은 합성수라고 가정하자. 그러면 동일한 논리의 적용으로 $n_1$의 양의 약수 중 소수인 것이 존재한다. 그것을 $p_2$라고 하면 $n_1=p_2{n}_2$로 표현할 수 있고 $1<n_2<n_1$이다. 따라서 $n=p_1{p}_2{n}_2$가 성립한다. 만약 $n_2$가 소수이면 $n$은 소수의 곱으로 표현되고 정리는 참이 되므로 $n_2$는 합성수이고, $n_2$의 양의 약수 중 소수인 것이 존재한다. 그것을 $p_3$라고 하면 $n_2=p_3{n}_3$로 표현할 수 있고 $1<n_3<n_2$이다. 따라서 $n=p_1{p}_2{p}_3{n}_3$가 성립한다.

위 과정을 반복하면, 유한 번의 과정 후에 $n_{k-1}$은 소수가 되고 이를 $p_k$라 하자. 이로부터 합성수 $n$은 소수의 곱 $n=p_1{p}_2{p}_3\cdots p_k$로 표현할 수 있다.

곱하는 순서를 무시했을 때, 표현방법은 유일하다. $n$을 두 가지 형태의 소수의 곱으로 표현한 것을 $n=p_1{p}_2{p}_3\cdots p_r$와 $n=q_1{q}_2{q}_3\cdots q_s$라고 하자. 여기서 소수는 증가하는 형태로 $p_1\le p_2\le \cdots \le p_r$, $q_1\le q_2\le \cdots \le q_s$이다. $p_1\mid q_1{q}_2\cdots q_s$를 만족하므로,  에 따라 어떤 $k$에 대해 $p_1=q_k$임을 알 수 있다. 이 경우 $p_1=q_1$이고, 반대로 $q_1{p}_2{p}_3\cdots p_r$인 경우 $q_1\ge p_1$이 되어 $p_1=q_1$이다.

양변을 같은 수 $p_1$으로 나누면 $\frac{n}{p_1}=p_2{p}_3\cdots p_r=q_2{q}_3\cdots q_s$가 되고 같은 과정을 반복하면 $p_2=q_2$가 된다. 유한 번의 과정 후에는 $r\le s$와 $q_r+1q_r+2\cdots q_s$가 도출되지만, 소수의 곱은 1보다 크다는 모순이 생긴다. 따라서 $r=s$가 되어 $n=p_1{p}_2\cdots p_r=q_1{q}_2\cdots q_r$이고 이것은 곧 두 소수의 곱이 유일한 형태임을 의미한다. $\boxed{{\displaystyle Q.E.D.}}$

 

 

소수판별법

만약 $n$이 합성수라면, $n$의 소인수 중 하나는 $\sqrt{n}$보다 같거나 작다.

 

만약 $n$이 합성수라면, 합성수의 정의에 의해 $1<a<n$인 인수 $a$가 존재한다. 양의 인수에 대한 정의에 따라 $n=ab$로 표현할 수 있고 $b$는 1보다 큰 양수이다. 만약 $a>\sqrt{n}$이고 $b>\sqrt{n}$이라면 $ab>\sqrt{n}\times \sqrt{n}=n$이 되는데 이는 $n=ab$와 모순이 된다. 따라서 $a\le \sqrt{n}$이거나 $b\le \sqrt{n}$이어야 한다. (Q.E.D.)

 

 

📌 예제: 101은 소수인가?

✘ 풀이: 만일 101이 합성수라면, 101의 소인수 중 하나는 $\sqrt{101}$보다 크지 않다. $\sqrt{101}\approx 10.05$. 10.05보다 작은 소수는 2, 3, 5, 7인데, 이들로 101을 나눌 수 있는지 확인해보자:

- 101 ÷ 2 ≠ 정수
- 101 ÷ 3 ≠ 정수
- 101 ÷ 5 ≠ 정수
- 101 ÷ 7 ≠ 정수

따라서 101은 10.05보다 작은 소수로 나눌 수 없으므로 101은 소수이다.

 

 

 

에라토스테네스의 체

 

에라토스테네스의 체는 특정한 정수 $n$ 이하의 소수를 모두 찾기 위한 확실한 접근 방법이다. 이 방법은 $\sqrt{n}$ 이하의 소수를 이용하여 $n$을 차례대로 나누어 나누어지지 않고 남아 있는 수를 구하는 방식이다. 다음은 100 이하의 모든 소수를 찾기 위한 에라토스테네스의 체의 과정이다.

1. 1에서 100까지 모든 수를 나열한다.

2. 2는 소수이므로, 2를 제외한 2의 배수들을 모두 지운다.
   - 지워지는 숫자들: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, .....

3. 3은 남아 있는 수 중 2보다 큰 첫 번째 소수이므로, 3을 제외한 3의 배수들을 모두 지운다.
   - 지워지는 숫자들: 6, 9, 12, 15, 18, 21, 24, 27, 30, ..... 

4. 5는 남아 있는 수 중 3보다 큰 첫 번째 소수이므로, 5를 제외한 5의 배수들을 모두 지운다.
   - 지워지는 숫자들: 10, 15, 20, 25, 30, .....

5. 7은 남아 있는 수 중 5보다 큰 첫 번째 소수이므로, 7을 제외한 7의 배수들을 모두 지운다.
   - 지워지는 숫자들: 14, 21, 28, .....

6. 계속해서 남아 있는 수 중 가장 작은 소수를 선택하여, 그 소수의 배수들을 모두 지운다. 이 과정을 $\sqrt{100}\approx 10$ 이하의 소수에 대해 반복한다.

결과적으로, 남아 있는 숫자들은 모두 소수이다.

 

(2) 소수의 무한성 

 

무한히 많은 소수가 존재한다.

 

✘ 증명 

유클리드는 대우를 이용하여 증명한다. 소수가 $n$개로 유한하고, 모든 소수를 $p_1,p_2,p_3,\dots ,p_n$이라고 가정하자. 이제 $Q=p_1{p}_2\cdots p_n+1$이라고 두면 $Q>1$인 소수이거나 합성수이다. 만약 $Q$가 합성수라면 어떤 소수 $p$로 나눌 수 있다. 여기서 $p$는 모든 $n$개의 소수 중 하나이어야 한다. 결국 $p\mid p_1{p}_2\cdots p_n$이면서 동시에 $p\mid Q$를 만족해야 하므로 $p\mid (Q-p_1{p}_2\cdots p_n)$, 즉 $p\mid 1$이 도출된다. 하지만 1의 인수는 1뿐이고 $p_n$는 1이 아니기에 모순이다. 결국 모든 소수의 리스트 $p_1,p_2,p_3,\dots ,p_n$에 없는 소수가 존재한다. 이 소수는 $Q$ 자신이거나 $Q$의 소인수로 존재한다. 결론적으로 유한한 $n$개의 소수에 포함되지 않는 소수가 반드시 있어야 하므로 소수는 무한히 많아야 한다. $\boxed{{\displaystyle Q.E.D.}}$

 

메르센 소수 

Mersenne Prime

- $2^p-1$ (단, $p$는 소수)

  - $n$이 합성수일 때, $2^n-1$은 소수가 아님.
  
✘ 증명
 
  $n=mk$라고 두자.
  $$2^n-1=2^{mk}-1=(2^m-1)(2^{m(k-1)}+2^{m(k-2)}+\cdots +1)$$
  $$\Rightarrow (2^m-1)\mid (2^n-1)$$

  - $2^p-1$이 모두 소수는 아님. (예: $2^{11}-1=23\times 89$)

 

 

 

 

소수 정리 

$$x$$ 이하의 소수의 개수 $\pi (x)$와 $\frac{x}{\ln x}$의 비율은 $$x$$가 무한히 커지면 1로 수렴한다.

$$\underset{x\to \mathrm{\infty }}{lim}\frac{\pi (x)}{\frac{x}{\ln x}}=1[\pi (x)\sim \frac{x}{\ln x}]$$

- 2부터 $$x$$까지 자연수 중에 소수가 될 확률:

$$\frac{\pi (x)}{x}\sim \frac{1}{\ln x}$$

 

 

 

 

4. RSA 암호 

 

 

(1) 페르마의 작은 정리 

 

$p$가 소수이고 $a$가 $p$로 나눌 수 없는 정수이면, 

$$a^{p-1}\equiv 1(\mathrm{mod}p)$$

이다. 또한 모든 정수 $a$에 대하여 

$$a^p\equiv a(\mathrm{mod}p)$$

이다.

 

📌 예제:  $$7^{222}$$를 11로 나누었을 때 나머지를 구하시오.

✘ 풀이:

$$7^{11-1}\equiv 1(\mathrm{mod}11)$$을 이용하자.
- 모든 정수 $k$에 대해 $$(7^{10}{)}^k\equiv 1(\mathrm{mod}11)$$가 성립.

그런데 222 = 22 × 10 + 2 이므로

$$7^{222}=7^{22\times 10+2}=(7^{10}{)}^{22}\cdot 7^2\equiv (1{)}^{22}\cdot 49(\mathrm{mod}11)$$
$$\equiv 5(\mathrm{mod}11)$$

따라서 $7^{222}\mathrm{mod}11=5$.