Saturday, January 4, 2014

Number Theory - 1

1. 나눗셈의 알고리즘(division algorithm)
정수 a와 양의 정수 b가 주어졌을 때, a=bq+r, 0≤r<b를 만족하는 유일한 정수 q, r이 존재한다.

(증명)
※ 정수의 정렬성 : 자연수의 집합 N의 공집합이 아닌 부분집합은 최소원을 가진다.
(1) 존재성 증명
S={a-mb|a-mb≥0, m은 정수}라 두자. 이 때, m=-|a|이면 b≥1이므로 |a| b≥|a|이고 a-(-|a|)b = a+|a|b≥a+|a|≥0 이므로 a-(-|a|)b∈S이다. 따라서 S는 공집합이 아니다.
i) 0이 S의 원소이면 0은 S의 최소원이다.
ii) 0이 S의 원소가 아니면 S⊂N이므로 정수의 정렬성에 의해 S는 최소원을 가진다.
i)와 ii)에 의해 S는 최소원을 가진다.
여기서 집합 S의 최소원을 r이라하면 적당한 정수 q에 대하여
r=a-bq, r≥0.
만약 r≥b이면, a-(q+1)b=(a-qb)-b=r-b≥0
→ a-(q+1)b∈S
→ r이 S의 최소원이라는 사실에 모순
따라서 r<b.
∴0<=r<b
∴a=bq+r, 0≤r<b인 정수 q, r이 존재

(2) 유일성 증명
a=bq+r =bq`+r`, 0≤r,r`<b
r-r`=b(q`-q) → |r-r`| = b|q-q`|
만약 q ≠q`이면 |q-q`|≥1이므로 |r-r`|≥b이 되어 0≤r<b에 모순
∴q와 r이 유일하게 존재.

2. 유클리드 알고리즘
두 양의 정수 a, b에 대하여 r(0) = a, r(1) = b라 하고
a(0), ... , a(n), r(2), ... , r(n) , r(n+1)을 다음을 만족하는 정수라 하자.
r(0) = a(0)r(1)+r(2) (0 < r(2) < r(1))
r(1) = a(1)r(2)+r(3) (0 < r(3) < r(2))
...
r(n-1) = a(n-1)r(n)+r(n+1) (0 < r(n+1) < r(n))
r(n) = a(n)r(n+1) 이때, (a,b) = r(n+1)이다.
그리고 s(0) = 1, s(1) = 0, s(i) = s(i-2)-a(i-2)s(i-1) (2≤ i ≤n+1)
t(0) = 0, t(1) = 1, t(i) = t(i-2)-a(i-2)t(i-1) (2≤ i ≤n+1)
이라 두면 r(i) = a*s(i) + b*t(i) (0≤ i ≤n+1) … ☆
특히 (a,b) = r(n+1) = a*s(n+1)+b*t(n+1)이 성립한다.

(증명)
나눗셈 알고리즘에 의해 a(i)와 r(i)는 존재하고
a=bq+r(0≤r<|b|)이면 (a, b) = (b, r)이라는 정리에 의해 (a, b) = (r(0), r(1)) = ... = (r(n), r(n+1))이다.
r(n+1)|r(n+1)이고 r(n+1)|r(n)이다. … ㉠
또 k|r(n)이고 k|r(n+1)이면 k≤r(n+1)이다. … ㉡
∴㉠과 ㉡에 의해 (a, b) = r(n+1)이다. (∵최대공약수의 정의)
그리고 i = 0 또는 i = 1이면 r(0) = a*s(0)+b*t(0), r(1) = a*s(1)+b*t(1)임은 명백하다.
만약 i ≤ k(0≤k≤n)인 모든 i에 대하여 ☆식이 성립한다면(수학적 귀납법)
r(k+1) = r(k-1)-a(k-1)r(k)
= a*s(k-1)+b*t(k-1) - a(k-1)( a*s(k) + b*t(k))
= a*(s(k-1)-a(k-1)s(k))+b(t(k-1)-a(k-1)t(k))
= a*s(k+1) + b*t(k+1)이므로 ☆식은 모든 i(0≤i≤n+1)에 대하여 성립한다.
따라서 (a, b) = r(n+1) = a*s(n+1)+b*t(n+1)이다.

3. 완전수(perfect number)
양의 정수 m에 대하여 σ (n) = 2n일 때 n을 완전수라 한다.

(Theorem)
메르센 소수 M(p) = (2^p)-1(p는 소수)에 대하여 N(p) = 2^(p-1) M(p)
즉, N(p) = 2^(p-1){(2^p)-1}는 완전수이다.
또, 짝수인 완전수는 모두 이와 같은 꼴이다.

(증명)
메르센 소수 M(p)와 2^(p-1)은 서로소이므로 σ (n)의 곱셈함수적 성질에 의해
σ (N(p)) = σ (2^(p-1))σ (M(p)) = (2^p) M(p) = 2 N(p)
따라서 N(p)는 완전수이다.
이제 짝수인 완전수 n을 n=(2^k)*m(k≥1, m은 홀수)라 하자.
이 때, (2^k, m) = 1이므로 (2^(k+1))m = 2n = σ (n) = σ (2^k) σ (m) = (2^(k+1)-1) σ (m)이고 (2^(k+1)-1, 2^(k+1)) = 1이므로 (2^(k+1)-1)|m이다.
따라서 m = (2^(k+1)-1)q, σ (m) = (2^(k+1))q인 양의 정수 q가 존재하고 q|m, q<m이다.
만약 q≠1이라고 가정하면 2≤q<m이므로 m은 적어도 3개의 양의 약수 1, q, m을 가지므로 σ (m) ≥ m+q+1 = (2^(k+1)-1)q+q+1 > (2^(k+1))q = σ (m)이 되어서 모순이다.
따라서 q=1, m=2^(k+1)-1, σ (m) = 2^(k+1) = m+1이고 이는 m의 약수가 1과 m뿐이라는 의미으로 m은 소수이다.
∴p=k+1로 두면 m=(2^p)-1이므로 p는 소수이고 m=M(p), n=(2^k)m=(2^(p-1))M(p) = N(p)

No comments:

Post a Comment