소수는 양의 약수가 1과 자기 자신뿐인 1보다 큰 정수이다. 모든 양의 정수는 소수들의 곱으로 분해되며, 이 분해가 본질적으로 유일하다는 사실이 정수론의 기본 구조를 만든다.
Prime과 Composite Number
의 양의 약수가 뿐이면 를 prime number라고 한다. 1보다 큰 정수 중 소수가 아닌 수는 composite number이다. 1은 소수도 합성수도 아니다. 1을 소수로 포함하면 소인수분해에 1을 임의로 반복해서 넣을 수 있어 유일성이 깨지기 때문이다.
Euclid’s Lemma for Primes
가 소수이고 이면 또는 이다.
증명
이면 끝이다. 그렇지 않다면 가 소수이므로 이다. Bézout’s Identity에 의해
인 정수 가 존재한다. 양변에 를 곱하면
이다. 왼쪽의 두 항은 모두 의 배수이므로 이다.
이 정리는 귀납적으로 확장된다.
특히 소수 에 대해 이면 인 가 존재한다.
Fundamental Theorem of Arithmetic
모든 은 소수들의 곱으로 표현되며, 소수의 순서를 제외하면 그 표현은 유일하다.
존재성
Strong Induction을 사용한다. 는 소수이므로 성립한다. 인 모든 정수에 대해 명제가 참이라고 가정하자.
이 소수이면 이미 소수 하나의 곱이다. 합성수이면 인 정수 이 존재한다. 귀납가정에 의해 는 각각 소수들의 곱으로 표현되므로 도 소수들의 곱으로 표현된다.
유일성
두 소인수분해가 있다고 하자.
이므로 Euclid’s Lemma에 의해 어떤 에 대해 이다. 두 수가 모두 소수이므로 이다. 순서를 바꾸어 로 둘 수 있고, 양변에서 같은 소수를 약분한다. 이 과정을 반복하면 두 분해에 등장하는 소수의 개수와 지수가 모두 같아진다.
따라서 모든 은
로 유일하게 표현된다. 여기서 는 서로 다른 소수이고 이다.
소인수분해로 GCD와 LCM 계산하기
처럼 두 수에 등장하는 소수를 모두 포함해 지수가 0일 수도 있게 쓰면
이다. 각 소수의 지수에 대해 최소값과 최대값을 더하면 가 되므로 GCD와 LCM의 곱이 라는 사실도 다시 확인할 수 있다.
소수 판별과 Sieve of Eratosthenes
합성수 에서 라 하면 , 즉 이다. 따라서 이 합성수라면 반드시 이하의 소인수를 가진다. 소수 여부를 확인할 때 부터 까지만 나누어 보면 충분한 이유이다.
Sieve of Eratosthenes는 일정 범위의 모든 소수를 한꺼번에 구한다.
- 2부터 원하는 상한까지 정수를 나열한다.
- 지워지지 않은 가장 작은 수 를 소수로 선택한다.
- 부터 시작해 의 배수를 지운다.
- 인 동안 반복한다.
는 더 작은 소수 단계에서 이미 지워졌기 때문에 부터 시작해도 된다.
소수가 무한히 많다는 증명
소수가 유한하게 뿐이라고 가정하자. 다음 수를 만든다.
어떤 로 나누어도 나머지가 1이므로 기존 소수 중 어느 것도 을 나누지 못한다. 그러나 은 소수이거나 어떤 소인수를 가져야 한다. 어느 경우든 목록에 없는 새로운 소수가 존재하므로 모순이다. 따라서 소수는 무한히 많다.
주의할 점은 자체가 항상 소수라는 주장이 아니라는 것이다. 핵심은 의 소인수가 기존 목록에 없다는 사실이다.
꼴 소수의 무한성
꼴 소수가 유한하게 뿐이라고 가정하고
을 생각한다. 이다. 의 모든 소인수가 라면 그 곱도 가 되어야 하므로, 적어도 하나의 소인수 는 이다.
그런데 각 에 대해 이므로 이다. 따라서 는 목록에 없는 새로운 꼴 소수이고 모순이다.
의 무리성
인 서로소 양의 정수 가 존재한다고 가정하자. 그러면
이므로 이다. Euclid’s Lemma에 의해 이고 라 둘 수 있다. 대입하면 이므로 이다. 가 모두 짝수라는 결론은 서로소라는 가정에 모순이다.
이 증명은 소수가 제곱을 나누면 원래 수도 나눈다는 성질에 의존한다.
Euclidean Numbers와 열린 문제
다음과 같이 정의한 수를 흔히 Euclid–Mullin 형태의 수열 또는 Euclidean construction과 관련해 살펴볼 수 있다.
서로 다른 단계에서 얻은 수들이 항상 소수일 필요는 없지만, 앞에서 선택된 모든 소수와는 서로소이다.
소수에는 아직 해결되지 않은 문제가 많다.
- Twin Prime Conjecture: 가 모두 소수인 쌍이 무한히 많은가?
- Goldbach Conjecture: 2보다 큰 모든 짝수는 두 소수의 합으로 표현되는가?
이들은 널리 계산으로 확인되었지만 일반적인 증명은 알려지지 않았다.
정리
Euclid’s Lemma는 소수가 곱을 나누는 방식을 통제하고, 이를 이용하면 소인수분해의 유일성을 증명할 수 있다. Fundamental Theorem of Arithmetic은 모든 정수가 소수의 지수 정보로 완전히 기술됨을 뜻한다. 소수는 무한히 많으며, 특정 합동류에 속하는 소수의 무한성도 비슷한 구성으로 증명할 수 있다.
연습 문제
- 을 소인수분해하고 약수 가 실제로 나누는지 지수 비교로 확인한다.
- 가 소수이고 이면 임을 증명한다.
- 꼴 소수가 무한히 많음을 Euclid 방식으로 증명한다.
풀이
1번
이고
이다. 에 나타난 각 소수의 지수가 의 대응 지수보다 작거나 같으므로 이다.
2번
이다. Euclid’s Lemma를 반복 적용하면 가 곱을 나눌 때 어느 한 인수 를 나누어야 한다.
3번
꼴 소수가 유한하게 뿐이라고 하자. 다음 수를 생각한다.
이고 2나 3으로 나누어지지 않는다. 의 소인수는 modulo 6에서 1 또는 5와 합동이다. 모든 소인수가 1과 합동이면 곱도 1과 합동이므로, 적어도 하나는 5와 합동이다. 또한 기존 로 나누면 나머지가 이므로 새로운 꼴 소수가 존재해 모순이다.