정수론

정수론

1보다 크고 자신과 1 이외에는 약수를 가지지 않는 수를 정수라고 한다. 나머지를 합성수라 한다. 모든 합성수는 소수의 곱으로 나타낼 수 있다. 이것을 소인수분해라고 한다.

정리1. 소수의 곱으로 나타낼 수 있는 임의의 정수는 하나의 소인수분해만 존재한다.

<증명>

(p_i,q_j는 소수)

만약, r=1 이라면 a=p1은 소수이므로, 당연히 s=1로서

이라야만 한다. 그래서 로 하고, a의 하나의 소인수분해에 나타나는 소인수의 개수가 r-1일 때는 정리가 성립된다고 가정하여 r의 경우를 증명한다.

만일, 일 때 a는 소수가 아니므로, 당연히 s도 이다. 그리고 소수 p1이 를 나누어떨어지게 할 수 있으므로, 명제3에 의해 q_i중의 적어도 하나가 p₁로 나누어떨어집니다. 필요하다면 번호를 바꾸어 달아서, 이를테면 이라 하면 도 소수이므로 이라야만 합니다. 따라서

의 양끝의 변을 으로 약분하면

가 됩니다. 이 한쪽의 변은 r-1개의 소수의 곱으로 되어 있습니다. 따라서 수학적귀납법의 가정에 의해 r-1=s-1(따라서 r=s)로서, 의 순서를 적당히 바꾸어 배열하면, , ,…,이 됩니다.

증명끝.

※ 합동식과 그 표기법

n을 하나의 주어진 양의 정수라고 했을 때, a, b에 대하여 차 a-b가 n의 배수일 때, a, b는 법(modulus) n에 관하여 합동이다라고 하며,

(mod n)

이라고 씁니다.[주의: 이런 낱말은 수학에서 때때로 쓰이는 색다른 용어라고만 알아두면 됩니다.]

이를테면

(mod 3)

(mod 5)

(mod 12)

입니다.

금방 알 수 있듯이, n을 법으로 하는 합동관계에 관해서는 다음 성질을 갖습니다. ([1]은 반사율, [2]는 대칭률, [3]은 추이율이라고 불립니다.)

[1] (mod n)

[2] (mod n) 이면 (mod n)

[3] (mod n), (mod n) 이면 (mod n)

증명: 0은 임의의 정수의 배수이므로, a-a=0은 n의 배수입니다. 따라서 [1]이 성립됩니다.

또, a-b가 n의 배수라면, -(a-b)=b-a도 n의 배수입니다. 이것은 [2]를 뜻합니다.

마지막으로 a-b 및 b-c가 모두 n의 배수라면, (a-b) + (b-c) = a-c 도 n의 배수입니다. 여기서 [3]을 얻을 수 있습니다.

※ 법 n에 관한 잉여류

이제부터 정수 전체의 집합을 문자 z로 나타내기로 하자.

앞에서와 같이, n을 주어진 하나의 양의 정수라고 한다. a를 임의의 정수라고 할 때, a를 n으로 나누면,

a=nq+r, 0≤r〈n

을 충족시키는 정수, q, r이 각각 단 하나 결정된다. 이 q와 r이 a를 n으로 나누었을 때의 몫 및 나머지이다.

합동의 정의에 따라

(mod n)

이 성립된다. 즉 임의의 정수 a는 0≤r〈n을 충족시키는 단 하나의 정수 r과 n을 법으로 하여 합동이 된다.

두 개의 정수 a, b를 n으로 나누었을 때의 나머지가 동일하다면, 양자는 n을 법으로 하여 합동이다. 한편, 0, 1, 2,…, n-1 중의 다른 두 개는 명백하게 n을 법으로 하여 합동이 아니므로, a, b를 n으로 나누었을 때의 나머지가 같지 않으면 양자는 합동이 아니다.

따라서 n을 법으로 하여 서로 합동인 정수끼리를 한 덩어리로 정리하면, 정수 전체의 집합 z가 n개의 집합으로 분할된다. 즉 n으로 나누었을 때, 나머지가 0이 되는 것(나누어 떨어지는 것) 전체의 집합, 1이 되는 것 전체의 집합, 2가 되는 것 전체의 집합,…,n-1이 되는 것 전체의 집합이라는 n개의 집합으로 분할된다.

이를테면, n=2를 법으로서 생각한다면, 정수의 전체 Z는 2로 나누어 떨어지는 것, 즉 짝수와 2로 나누면 1이 남는 것, 즉 홀수로 분할된다.

n = 2

… -6 -4 -2 0 2 4 6 …

… -5 -3 -1 1 3 5 7 …

마찬가지로 n=3, n=5의 경우에는 z는 각각 다음과 같이 분할된다.

n = 3

… -9 -6 -3 0 3 6 9 …

… -8 -5 -2 1 4 7 10 …

… -7 -4 -1 2 5 8 11 …

n = 5

… -15 -10 -5 0 5 10 15 …

… -14 -9 -4 1 6 11 16 …

… -13 -8 -3 2 7 12 17 …

… -12 -7 -2 3 8 13 18 …

… -11 -6 -1 4 9 14 19 …

일반적으로 n을 법으로 했을 때, z는 서로 합동인 정수끼리로 된 n개의 집합으로 분할된다. 그 n개의 각 집

합을 법 n에 관한 잉여류(또는 법 n의 잉여류, mod n의 잉여류 등)라고 부른다.

또, n개의 잉여류에서 각각 하나식 대표를 취한 n개의 정수의 쌍을, 법 n에 관한 완전잉여계(또는 줄여서

그냥 잉여계)라고 부른다. 이를테면 n=5를 법으로 했을 경우 위의 표에서 0표를 한 5개의 수 0, 1, 2, 3, 4는

하나의 완전잉여계이다.