정수론(Number theory)

소인수분해(Prime factorization)

1보다 큰 모든 자연수⁠(natural number)⁠는 소수⁠(prime number)⁠들의 곱으로 쓸 수 있고, 그 방법은 순서를 빼면 오직 하나뿐이다.

n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}

먼저 보면 좋은 개념소수와 에라토스테네스의 체

합성수⁠(composite number)⁠는 더 작은 두 수의 곱으로 쪼갤 수 있고, 쪼갠 조각이 또 합성수면 다시 쪼갭니다. 더 쪼갤 수 없는 조각이 소수입니다. $n =$ 을 쪼개 봅시다: .

왼쪽으로 떨어지는 초록 잎⁠(leaf)⁠이 소수, 오른쪽으로 내려가는 흰검은 마디가 아직 더 쪼갤 몫입니다. 마지막 몫은 소수라서 초록입니다.

어떤 순서로 쪼개든 같은 소수들이 같은 개수만큼 나온다는 것이 산술의 기본정리입니다. 당연해 보이지만 증명이 필요한 사실입니다. 열쇠는 "소수 $p$ 가 곱 $ab$ 를 나누면 $a$ 나 $b$ 중 하나를 나눈다"는 성질(유클리드의 보조정리⁠(lemma)⁠)입니다. 두 분해가 있다면 한쪽의 소수가 다른 쪽의 어떤 소수를 나누어야 하니 그 둘은 같고, 양쪽에서 지우며 반복하면 두 분해가 똑같아집니다.

그래서 자연수는 "소수마다 몇 개씩"이라는 지수 목록과 같습니다. 약수⁠(divisor)⁠도 이 목록으로 보입니다. $n = 2^a 3^b$ 의 약수는 $2^i 3^j$ ( $0 \le i \le a,\ 0 \le j \le b$ )로, 격자 위의 직사각형 하나를 채웁니다. 그래서 약수는 $(a+1)(b+1)$ 개입니다. $n = 2^{a} 3^{b}$ 에서 $a =$ , $b =$ , $m = 2^{c} 3^{d}$ 에서 $c =$ , $d =$ 로 두면 $n =$ , $m =$ 입니다.

파란 상자는 n의 약수, 분홍 상자는 m의 약수입니다. 겹친 초록 칸이 공약수이고, 그 오른쪽 위 끝이 최대공약수입니다.

두 직사각형이 겹친 부분이 공약수이고, 겹친 부분의 오른쪽 위 모서리가 최대공약수(지수마다 작은 쪽, 지금 ), 두 상자를 모두 덮는 가장 작은 상자의 모서리가 최소공배수(지수마다 큰 쪽, )입니다. 큰 수에서는 이 분해가 어렵기 때문에 최대공약수⁠(greatest common divisor)⁠는 분해 없이 유클리드 호제법⁠(Euclidean algorithm)⁠으로 구합니다.

서로 다른 소수 $k$ 개를 한 번씩 곱한 수(30 = 2·3·5처럼 제곱 인수가 없는 수)라면 약수 하나는 "어떤 소수를 고를까"라는 선택, 곧 소인수 집합⁠(set)⁠의 부분집합⁠(subset)⁠ 하나입니다. 그래서 약수의 개수는 멱집합⁠(power set)⁠의 크기 $2^k$ 이 됩니다. 30의 약수는 $2^3 = 8$ 개입니다. 소인수를 알면 오일러 피 함수⁠(Euler's totient function)⁠도 곧바로 계산됩니다.

소인수분해가 한 가지뿐이라는 사실 덕분에 괴델은 수식 하나를 자연수 하나로 바꿔 적을 수 있었습니다. 기호마다 번호를 정해 두고, 수식의 첫째 기호 번호를 2의 지수로, 둘째를 3의 지수로, 셋째를 5의 지수로 올려 모두 곱합니다. 기호 번호가 1, 3, 2인 수식이라면 $2^1 \cdot 3^3 \cdot 5^2 = 1350$ 이 됩니다. 분해가 한 가지뿐이니 이 수를 소인수분해하면 원래 수식을 정확히 되찾을 수 있습니다. 이렇게 수식에 붙인 번호를 괴델 수라 합니다. 수식에 관한 말을 자연수에 관한 말로 바꾸는 이 장치가 불완전성 정리⁠(incompleteness theorem)⁠의 출발점입니다.

관련된 시대와 장소바그다드 지혜의 집 20세기 초 케임브리지 벨 연구소

이 개념이 나오는 큰 생각자기 참조와 대각선 표현 바꾸기

이 개념이 나오는 긴 글

소수 소수를 세는 사람들 소수는 제멋대로 흩어져 있는 것 같다. 그런데 멀리서 세어 보면 로그가 보인다. 정수론과 암호 나머지로 지키는 비밀 한 번도 만난 적 없는 두 사람이 모두가 엿듣는 통신망에서 비밀 열쇠를 맞출 수 있을까? 답은 시계의 산수와 1640년 페르마의 정리에 있다. 집합론 무한에도 크기가 있다 자연수와 짝수는 어느 쪽이 많을까? 칸토어는 무한을 세는 법을 찾았고, 무한이 하나가 아님을 보였다. 그래프 이론 일곱 다리의 도시 쾨니히스베르크의 일곱 다리를 한 번씩만 건너 산책할 수 있을까? 오일러는 지도를 지우고 점과 선만 남겼다. 계산 이론 기계가 풀 수 없는 문제 모든 수학 문제를 기계적으로 풀 수 있을까? 러셀의 역설에서 괴델과 튜링까지, 그 질문에 대한 답은 '아니오'였고, 그 증명이 컴퓨터를 낳았다. 수학의 오류 틀린 증명이 만든 수학 틀린 증명은 흔하다. 드물게, "정확히 어디가 틀렸는가"라는 물음이 새 분야를 낳는다. 코시의 합 정리와 균등 수렴, 라메의 증명과 아이디얼, 켐프의 사슬, 푸앵카레의 회수된 논문과 혼돈, 프레게의 법칙과 러셀의 편지, 보예보츠키와 증명 보조기까지. 오류는 대개 서로 다른 두 가지를 하나로 여긴 자리에 있었다. 범주론 화살표만으로 본 수학 최대공약수와 교집합과 '그리고'는 같은 것이고, 화살표를 뒤집으면 최소공배수와 합집합과 '또는'이 된다. 무엇으로 만들었는지 묻지 않고 어떻게 이어지는지만 보는 언어로, '자연스럽다'는 말의 뜻, 관계만으로 대상을 알아보는 요네다의 생각, 함자로 본 연쇄법칙, 어디에나 있는 수반까지 사이트의 여러 분야를 가로지른다.

이 개념 위에 세워진 것

최대공약수와 유클리드 호제법 리만 제타 함수 괴델의 불완전성 정리 유일 인수분해와 아이디얼

이 개념을 언급하는 페이지

소수와 에라토스테네스의 체
1보다 큰 모든 자연수는 소수들의 곱으로 쪼개집니다(소인수분해). 그래서 소수는 곱셈의 원자이고, 정수의 성질을 연구하는 정수론의 한가운데에 있습니다. 소수를 찾는 …
최대공약수와 유클리드 호제법
… 입니다. 문제를 같은 모양의 더 작은 문제로 줄이는 재귀의 전형입니다. 흔히 최대공약수를 구하려면소인수분해가 필요하다고 생각합니다. 학교에서 12 = 2² × 3, 18 = 2 × 3²으로 나누어 공통인 2 × …
오일러 피 함수와 페르마 소정리
… p^k , 그 두 배 2p^k 뿐이라는 것을 가우스가 보였습니다. \varphi(n) 의 공식은소인수분해한 뒤 각 소인수의 배수를 포함배제 원리로 빼면 나옵니다. 이 정리 하나 위에 RSA 암호가 서 …
RSA 암호
… p, q 가 곧바로 나옵니다. 공개된 것은 n 과 e 뿐입니다. 이것만으로 d 를 알아내는 일은 n 을소인수분해하는 일만큼 어렵다는 것이 증명되어 있습니다. 다만 d 없이 암호문을 푸는 다른 지름길이 없다는 증명은 …
원시근
… 한 바퀴에 모두 도는 수가 원시근 입니다(오른쪽 노란 막대). 더 나아가 위수는 늘 \varphi(n) 의약수입니다. 오일러 정리에 따라 a^{\varphi(n)} \equiv 1 이고, 1로 돌아오는 지수는 모두 …
중국인의 나머지 정리
… 법이 몇 개든 쌍마다 서로소이기만 하면 됩니다. 이어지는 곳. 이 정리 덕분에 합성수를 법으로 하는 계산은소인수분해의 각 소수 거듭제곱에 대한 계산으로 쪼개집니다. 서로소인 m, n 에 대해, mn 과 서로소인 …
디피–헬먼 키 교환
… p 번이 아니라 약 \sqrt p 번의 계산으로 로그를 찾을 수 있습니다. 또 p-1 이 작은 소수들로만소인수분해되면 중국인의 나머지 정리로 문제를 작은 소수마다의 쉬운 문제로 쪼갤 수 있습니다. 그래서 실제로는 …
소수 판정
… 표기법⟧). 그래도 실제로는 더 빠른 밀러–라빈이 쓰입니다. 합성수라는 것을 알아도 인수를 찾는소인수분해는 여전히 어렵습니다. 밑을 거듭제곱할 때 값이 도는 고리 구조는 원시근에서, 판정에 쓰는 나머지 …
리만 제타 함수
… n^{-s} 이 정확히 한 번씩 나옵니다. 모든 자연수가 소수의 곱으로 단 한 가지로 쓰이기 때문입니다(소인수분해). N = 까지 자른 합은 , 곱은 입니다. 곱을 전개하면 N 이하의 모든 항에 더 많은 항까지 들어 …
괴델의 불완전성 정리
… 기호표(아래 숫자가 기호의 번호), 가운데는 지금 식입니다. 기호의 번호가 그 자리 소수의 지수가 됩니다.소인수분해가 오직 한 가지뿐이므로 수에서 기호열을 되찾을 수 있습니다. 수를 끌어 바꿔 보세요: . 증명도 식들을 …
처치–튜링 논제
… 않습니다. 하지만 미국 수학자 피터 쇼어가 1994년에 내놓은 알고리즘을 쓰면, 충분히 큰 양자 컴퓨터는소인수분해를 다항식 걸음에 해낼 수 있어 RSA를 위협합니다. 보통 컴퓨터로는 소인수분해의 다항 시간 방법이 …
P 대 NP 문제
… 1959)으로 빠르게 풉니다. 모양이 비슷해 보이는 문제가 쉬움과 어려움으로 갈립니다. 큰 수를소인수분해하는 문제도 'N에 k보다 작은 인수가 있는가'라는 예/아니오 꼴로 바꾸면 NP에 속합니다. 인수를 …
수학적 귀납법
… 단계에서 바로 앞 하나가 아니라 1부터 k까지 전부가 참이라고 가정해도 됩니다. 2 이상의 자연수는 모두소인수분해된다는 증명이 그렇습니다. n이 소수이면 n 자신이 소인수분해입니다. 소수가 아니면 n = ab\ (1 …
정수론
… 360 = 2^3 \cdot 3^2 \cdot 5 이고, 순서를 바꾸는 것 말고 다른 분해는 없습니다(소인수분해, 산술의 기본정리). 기원전 300년 무렵 유클리드의 『원론』 7–9권에 이미 두 수의 …
보편 성질: 곱, 쌍대곱, 극한
… AND·OR이자 집합의 연산의 교집합·합집합이고, 나누어떨어짐에서는 최대공약수와 최소공배수이며,소인수분해로 보면 소수마다 지수의 최솟값과 최댓값을 고르는 일입니다. 곱과 쌍대곱이 방향만 뒤집은 짝이라는 것은 …
유일 인수분해와 아이디얼
… 역원이 있는 수(단원)는 \pm 1 뿐이니, 두 분해는 순서나 단원의 차이가 아니라 정말로 다릅니다.산술의 기본정리, 곧 소인수분해가 한 가지뿐이라는 성질이 여기서는 성립하지 않습니다. 무엇이 달라졌을까요? 정수에서 …
페르마의 마지막 정리
… y^p 를 1의 거듭제곱근을 써서 일차식들의 곱으로 쪼갰는데, 그 논증은 이렇게 넓힌 수의 세계에서도소인수분해가 한 가지뿐이라는 가정에 기대고 있었습니다. 독일의 에른스트 쿰머는 그 가정이 p = 23에서 처음 …

이 페이지가 가리키는 개념

유클리드 최대공약수와 유클리드 호제법 집합 멱집합 오일러 피 함수와 페르마 소정리 쿠르트 괴델 괴델의 불완전성 정리