정수론 Kuldeep Singh 간단 정리 I

출처: Freepik

※ 이 글은 정수론 첫걸음 교재를 바탕으로 작성되었습니다.

#1.나눗셈 탐구
자연수의 정렬성(WOP)
공집합이 아닌 양의 정수의 부분집합에는 가장 작은 원소가 있다.

일반성을 잃지 않는다(WLOG)
모든 사례를 고려하는 대신, 특정 사례를 고려하고 나머지 사례에도 유사하게 적용한다.

- 나눗셈 알고리즘
임의의 정수 a, b ( b≥1 )에 대하여 다음을 만족하는 유일한 정수 q와 r이 존재한다. q는 몫, r은 나머지라 부른다.

a=bq+r, ( b>r≥0 )

다음의 증명은 WOP를 이용하여 한다.
이것은 집합 S를 정의하는 것부터 시작된다.

S={ a-mb: m은 정수이고 a-mb≥0 }

STEP1) S≠∅ 증명
m=∣a∣를 a-mb에 대입 시, b≥1이라 a-∣a∣b는 0 이상이 된다.
따라서 S≠∅이다.

STEP2) r<b가 성립하는 원소 r이 존재함을 보이기
WOP를 사용 시, S에 가장 작은 원소 r이 존재한다.
r<b가 성립함을 보여야 한다. ( 그 후, 유일성을 증명한다. )
r≥b일 경우, r>r-b≥0이 되어 S에 r보다 작은 원소 r-b가 포함되게 되어 모순, 즉 r<b가 성립한다.

STEP3) q, r이 유일함을 증명하자.
a=bq'+r'=bq+r이라 하자.

(r'-r)/b = q-q'이 성립 (*)
r'>r이라고 가정, 0≤r'-r<b가 성립
b≥1이므로 0≤r'-r<b를 (*)에 대입하여 0≤r'-r/b<b/b=1임을 알 수 있다.
0≤q-q'<1을 만족하는 유일한 정수는 0이므로 q=q', 이를 (*)에 대입 시, r=r'이 되어 유일성이 증명된다.

이런 류의 증명은 꽤 자주 사용되기에 정리해보았다. 집합을 정의하고 논리를 펼쳐나가는 방식 말이다.

- 베주 항등식 (Be'zout's identity)
0이 아닌 a, b에 대하여 ax+by=gcd(a, b)를 만족하는 정수 x, y가 존재한다.

이것 또한 WOP를 이용하여 증명한다. 역시 S={ ax+by: ax+by>0 }을 정의하는 것에서부터 시작한다.

마지막으로 디오판토스 방정식에 대해 간략하게 설명 후 #1.나눗셈 탐구를 마무리하겠다.
- 디오판토스 방정식
변수가 2개인 일차 디오판토스 방정식은 ax+by=c의 형태로, 변수 x, y는 정수이며 a, b는 0이 아니다.
( x₀와 y₀가 위의 디오판토스 방정식의 해일 경우, x=x₀+bt, y=y₀-at 또한 위의 방정식의 해이다. gcd(a, b)=g, g∣c를 만족하는 경우에 x와 y의 해가 어떤 식의 형태를 띌지는 각자 알아보자. )


#2. 소수와 인수분해
산술의 기본 정리:
1보다 큰 모든 정수는 소수이거나 소수들의 곱으로 나타낼 수 있다. 곱하는 순서를 무시할 시, 소수들의 곱 형태는 유일하다.

이 단원은 인수분해, 최소공배수와 최대공약수 등에 대해 다루는데 고등과정을 공부했다면 딱히 주의해서 볼 개념은 없어보인다. 간단한 명제에 대해 소개하고자 한다.

임의의 양의 정수 n에 대하여, 합성수이면서 연속인 정수가 n개 존재한다.
- 실례: (n+1)!+2, (n+1)!+3 ... , (n+1)!+(n+1)


#3. 합동 산술 이론

≡에 대해 논할 차례다. 우선 여러 개념에 대해 정의하자.

- 합동

n은 주어진 양의 정수, a, b는 정수. 다음을 만족하면 'a와 b는 법 n에 대해 합동'이라고 한다.

a ≡ b (mod n) ↔ a-b가 n의 배수 or 정수 k가 존재하여 a-b=kn 만족
이해를 돕자면 a ≡ 0 (mod n)은 n∣a와 동치다.

- 완전 잉여 집합 & 완전 잉여계
모든 정수가 집합 {r₁, r₂, ... , r_n-1, r_n}에서 단 하나의 r_k와 합동인 경우, 이 집합을 n의 완전 잉여 집합 또는 법 n의 완전 잉여계라 한다.

몇개만 정리하고 넘어가고자 한다.
1. ac ≡ bc (mod n)이고 gcd(c, n)=g이면 a ≡ b (mod n/g)이다. (소거법칙)
2. 선형합동식 ax ≡ b (mod n)의 해가 존재하는 것은 g=gcd(a, n)에 대해 g∣b인 것과 필요충분관계다. (선형합동식의 해)
3. 2번의 상황에서 gcd(a, n)=1이면 선형합동식 ax ≡ b (mod n)은 법 n에 대하여 유일한 해를 가진다. (유일성)

4. ax ≡ 1 (mod n)일 때, 이 합동식의 유일한 해 x는 법 n에 대하여 a의 곱셈에 대한 역원이라고 하며 a^-1 (mod n)으로 표기한다. (곱셈에 대한 역원)

- 중국인의 나머지 정리
n₁, n₂, ... n_r은 양의 정수이고 쌍마다 서로소다. 다음 연립방정식을 만족하는 해가 존재하고 법 n₁ × n₂ × ... × n_r 에 대해 유일하다.

여기까지가 3단원까지의 개념이다. 총 8단원까지 있으니 II, III 까지 적어서 마무리해보겠다.