Fundamental theorem of arithmetic

Original article: w:Fundamental theorem of arithmetic

Not to be confused with Fundamental theorem of algebra.

The unique factorization theorem was proved by Gauss with his 1801 book Disquisitiones Arithmeticae. In this book, Gauss used the fundamental theorem for proving the law of quadratic reciprocity.

숫자 이론(number theory)에서, 산술의 기본 정리(fundamental theorem of arithemetic)는, 역시 고유한 인수분해 정리(unique factorization theorem) 또는 고유한-소수-인수분해 정리(unique-prime-factorization theorem)라고 불리며, 1보다 큰 모든 각 정수(integer)는 소수(prime number) 그 자체 또는 소수의 곱으로 표현될 수 있고, 게다가, 이 표현은 인수의 순서까지(up to) (제외하고) 고유하다고 말합니다. 예를 들어,

$1200=2^{4}\cdot 3\cdot 5^{2}=(2\cdot 2\cdot 2\cdot 2)\cdot 3\cdot (5\cdot 5)=5\cdot 2\cdot 5\cdot 2\cdot 3\cdot 2\cdot 2=\ldots$

그 정리는 이 예제에 대해 두 가지를 말합니다: 첫째, 1200은 소수의 곱으로써 표현될 수 있고, 둘째, 이것이 어떻게 행해지는 것과 상관없이, 항상 정확히 넷의 2, 하나의 3, 둘의 5가 있고, 곱에서 다른 소수는 없습니다.

인수가 소수라는 요구-사항은 필요합니다: 합성수(composite number)를 포함하는 인수분해는 고유하지 않을 수 있습니다 (예를 들어, $12=2\cdot 6=3\cdot 4$).

이 정리는 1이 소수로 여겨지지 않는 주된 이유 중 하나입니다: 만약 1이 소수라면, 소수로의 인수분해는 고유하지 않을 것입니다; 예를 들어, $2=2\cdot 1=2\cdot 1\cdot 1=\ldots$

Euclid's original version

유클리드(Euclid)의 원론(Elements)의 책 VII, 제안 30, 31과 32, 및 책 IX, 제안 14는 본질적으로 기본 정리의 명제이고 증명입니다.

만약 두 숫자를 서로 곱해서 어떤 숫자를 만들고, 임의의 소수가 그 곱을 측정하면, 그것은 역시 원래 숫자의 하나를 측정할 것입니다.

— 유클리드, 원론 책 VII, 제안 30

(현대 용어에서: 만약 소수 p가 곱 ab를 나누면, p는 a 또는 b 또는 둘 다를 나눕니다.) 제안 30은 유클리드의 보조정리(Euclid's lemma)로 참조되고, 그것은 산술의 기본 정리의 증명에서 핵심입니다.

임의의 합성수는 어떤 소수에 의해 측정됩니다.

— 유클리드, 원론 책 VII, 제안 31

(현대 용어에서: 일보다 큰 모든 각 정수는 어떤 소수에 의해 균등하게 나뉩니다.) 제안 31은 무한 하강(infinite descent)에 의해 직접 입증됩니다.

임의의 숫자는 소수이거나 어떤 소수에 의해 측정됩니다.

— 유클리드, 원론 책 VII, 제안 32

제안 32는 제안 31로부터 유도되고, 분해가 가능함을 입증합니다.

만약 하나의 소수가 소수에 의해 측정되는 것 중에 가장 작으면, 그것은 원래 그것을 측정하는 소수를 제외하고 임의의 다른 소수에 의해 측정되지 않을 것입니다.

— 유클리드, 원론 책 IX, 제안 14

(현대 용어에서: 여러 소수의 최소 공통 배수(least common multiple)는 임의의 다른 소수의 배수가 아닙니다.) 책 IX, 제안 14는 책 VII, 제안 30에서 유도되고, 부분적으로 분해는 고유하다는 것을 입증합니다 – 이것은 앙드레 베유(André Weil)에 의해 비판적으로 지적됩니다. 사실, 이 제안에서 지수는 모두 일과 같으므로, 어떤 것도 일반적인 경우에 대해 말해지지 않습니다.

가우스(Gauss)의 Disquisitiones Arithmeticae의 기사 16은 초기의 현대 명제이고 모듈러 산술(modular arithmetic)을 사용하여 증명입니다.

Applications

Canonical representation of a positive integer

모든 각 양의 정수 n > 1은 소수 거듭제곱의 곱으로 정확하게 하나의 방법에서 표현될 수 있습니다:

$n=p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{k}^{n_{k}}=\prod _{i=1}^{k}p_{i}^{n_{i}}$

여기서 p₁ < p₂ < ... < p_k는 소수이고 n_i는 양의 정수입니다. 이 표현은 공통적으로 빈 곱(empty product)이 1과 같다는 관례에 의해, 1을 포함하여, 모든 양의 정수로 확장됩니다 (빈 곱은 k = 0에 해당합니다).

이 표현을 n의 정식의 표현(canonical representation) 또는 n의 표준 형식(standard form)이라고 불립니다. 예를 들어,

999 = 3³×37,

1000 = 2³×5³,

1001 = 7×11×13.

인수 p⁰ = 1는 n의 값을 변경하는 것없이 삽입될 수 있습니다 (예를 들어, 1000 = 2³×3⁰×5³). 사실, 임의의 양의 정수는 모든 양의 소수에 걸쳐 무한 곱(infinite product)으로 고유하게 표현될 수 있습니다:

$n=2^{n_{1}}3^{n_{2}}5^{n_{3}}7^{n_{4}}\cdots =\prod _{i=1}^{\infty }p_{i}^{n_{i}},$

여기서 n_i의 유한 숫자는 양의 정수이고, 나머지는 영입니다. 음의 지수를 허용하는 것은 양의 유리수(rational number)에 대해 정식의 형식이 제공합니다.

Arithmetic operations

두 숫자 a와 b의 곱의 정식의 표현, 최대 공통 약수(greatest common divisor) (GCD), and 최소 공통 배수(least common multiple) (LCM)는 a와 b 자체의 정식의 표현의 관점에서 간단히 표현될 수 있습니다:

${\begin{alignedat}{2}a\cdot b&{}={}2^{a_{1}+b_{1}}3^{a_{2}+b_{2}}5^{a_{3}+b_{3}}7^{a_{4}+b_{4}}\cdots &&{}={}\prod p_{i}^{a_{i}+b_{i}},\\\gcd(a,b)&{}={}2^{\min(a_{1},b_{1})}3^{\min(a_{2},b_{2})}5^{\min(a_{3},b_{3})}7^{\min(a_{4},b_{4})}\cdots &&{}={}\prod p_{i}^{\min(a_{i},b_{i})},\\\operatorname {lcm} (a,b)&{}={}2^{\max(a_{1},b_{1})}3^{\max(a_{2},b_{2})}5^{\max(a_{3},b_{3})}7^{\max(a_{4},b_{4})}\cdots &&{}={}\prod p_{i}^{\max(a_{i},b_{i})}.\end{alignedat}}$

어쨌든, 특히 큰 숫자의, 정수 인수분해(integer factorization)는 곱, GCD, 또는 LCM을 계산하는 것보다 훨씬 더 어렵습니다. 따라서 이들 공식은 실제에서 제한적인 사용을 가집니다.

Arithmetic functions

Main article: Arithmetic function

많은 산술 함수는 정식의 표현을 사용하여 정의됩니다. 특히, 덧셈(additive) 및 곱셈(multiplicative) 함수의 값은 소수의 거듭제곱에 대한 그들의 값에 의해 결정됩니다.

Proof

증명은 유클리드의 보조정리(Euclid's lemma)를 사용합니다 (원론 VII, 30): 만약 소수 p가 두 정수 a와 b의 곱 ab를 나누면(divides), p는 그들 정수 a와 b 중 적어도 하나를 나누어야 합니다.

Existence

1보다 큰 모든 각 정수는 소수 또는 소수의 곱임을 보여야 합니다. 먼저, 2는 소수입니다. 그런-다음, 강한 귀납법(strong induction)에 의해, 이것이 1보다 크고 n보다 작은 모든 숫자에 대해 참이라고 가정합니다. 만약 n이 소수이면, 더 이상 입증할 것이 없습니다. 그렇지 않으면, 정수 a와 b가 있으며, 여기서 n = ab이고, 1 < a ≤ b < n입니다. 귀납법 가설에 의해, a = p₁p₂...p_j 및 b = q₁q₂...q_k는 소수의 곱입니다. 그러나 그때에 n = ab = p₁p₂...p_jq₁q₂...q_k는 소수의 곱입니다.

Uniqueness

반대로, 두 구별되는 소수 인수분해를 가진 정수가 있다고 가정합니다. n을 가장 작은 그러한 정수라고 놓고 n = p₁ p₂ ... p_j = q₁ q₂ ... q_k라고 쓰며, 여기서 각 p_i와 q_i는 소수입니다. (주목 j와 k는 둘 다 적어도 2입니다.) 우리는 p₁이 q₁ q₂ ... q_k를 나눔을 알고 있으므로, p₁은 일부 q_i를 유클리드의 보조정리에 의해 나눕니다. 일반성의 손실 없이, p₁이 q₁을 나눈다고 말합니다. p₁과 q₁이 둘 다 소수이므로, p₁ = q₁임을 따릅니다. 우리의 n의 인수분해로 돌아가서, 우리는 이들 두 항을 p₂ ... p_j = q₂ ... q_k를 결론짓기 위해 취소합니다. 우리는 이제 n보다 엄격하게 작은 일부 정수의 두 구별되는 소수 인수분해를 가지며, 이것은 n의 최소성과 모순됩니다.

Elementary proof of uniqueness

산술의 기본 정리는 다음과 같이 유클리드의 보조정리를 사용하는 것없이 입증될 수 있습니다:

s > 1이 두 가지 다른 방법으로 소수의 곱인 가장 작은 양의 정수라고 가정합니다. 만약 s가 소수였으면 자체적으로 고유하게 인수분해할 수 있으므로, s는 소수가 아니고 s의 각 인수분해에서 적어도 두 소수가 있어야 합니다:

${\begin{aligned}s&=p_{1}p_{2}\cdots p_{m}\\&=q_{1}q_{2}\cdots q_{n}.\end{aligned}}$

만약 임의의 p_i = q_j이면, 취소에 의해, s/p_i = s/q_j는 s와 다른 또 다른 양의 정수일 수 있으며, 이것은 1보다 크고 역시 두 구별되는 인수분해를 가집니다. 그러나 s/p_i는 s보다 작으며, s는 실제로 가장 작은 그러한 정수가 아닐 수 있음을 의미합니다. 그러므로 모든 각 p_i는 모든 각 q_j로부터 구별될 수 있어야 합니다.

일반성의 손실 없이, p₁ < q₁를 취합니다 (만약 이것이 아직 그 경우가 아니면, p와 q 지정을 전환하십시오.) 다음을 생각해 보십시오:

$t=(q_{1}-p_{1})(q_{2}\cdots q_{n}),$

그리고 1 < q₂ ≤ t < s임을 주목하십시오. 그러므로 t는 고유한 소수 인수분해를 가져야 합니다. 재배열에 의해, 우리는 다음임을 압니다:

${\begin{aligned}t&=q_{1}(q_{2}\cdots q_{n})-p_{1}(q_{2}\cdots q_{n})\\&=s-p_{1}(q_{2}\cdots q_{n})\\&=p_{1}((p_{2}\cdots p_{m})-(q_{2}\cdots q_{n})).\end{aligned}}$

여기서 u = ((p₂ ... p_m) - (q₂ ... q_n))는 양수인데, 왜냐하면 만약 그것이 음수 또는 영이면 p₁과의 그것의 곱일 것이기 때문이지만, 그 곱은 양수인 t와 같습니다. 따라서 u는 1 또는 소수로 인수화됩니다. 두 경우에서, t = p₁u는 t의 소수 인수분해를 산출하며, 우리는 이것이 고유할 것임을 알고 있으므로, p₁은 t의 소수 인수분해에서 나타납니다.

만약 (q₁ - p₁)이 1과 같았다면 t의 소수 인수분해는 모두 q일 것이며, 이것은 나타나는 것에서 p₁을 제외할 것입니다. 따라서 (q₁ - p₁)는 1이 아니지만, 양수이므로, 그것은 소수로 인수화됩니다: (q₁ - p₁) = (r₁ ... r_h). 이것은 다음의 소수 인수분해를 산출합니다:

$t=(r_{1}\cdots r_{h})(q_{2}\cdots q_{n}),$

우리는 이것이 고유함을 알고 있습니다. 이제, p₁이 t의 소수 인수분해에서 나타나고, 그것은 임의의 q와 같지 않으므로, 그것은 r' 중 하나이어야 합니다. 그것은 p₁가 (q₁ - p₁)의 인수임을 의미하므로, p₁k = (q₁ - p₁)를 만족하는 양의 정수 k가 존재하고, 따라서 다음입니다:

$p_{1}(k+1)=q_{1}.$

그러나 그것은 q₁이 적절한 인수분해를 가짐을 의미하므로, 그것은 소수가 아닙니다. 이 모순은 s가 실제로 두 다른 소수 인수분해를 가지지 않음을 보여줍니다. 결과로써, 여러 소수 인수분해를 갖는 가장 작은 양의 정수가 없으므로, 1보다 큰 모든 양의 정수는 고유하게 소수로 인수화됩니다.

Generalizations

그 정리의 첫 번째 일반화는 복이차 상호관계(biquadratic reciprocity)에 대한 가우스의 이차 연구논문 (1832)에서 발견됩니다. 이 논문은 지금 가우스 정수(Gaussian integer)의 링(ring), 모든 복소수(complex number) a + bi의 집합이라고 불리는 것을 도입했으며, 여기서 a와 b는 정수입니다. 그것은 지금 $\mathbb {Z} [i]$로 표시됩니다. 그는 이 링이 네 단위 ±1 및 ±i를 가진다는 것, 비-영, 비-단위 숫자가 두 클래스, 소수와 함성수로 떨어진다는 것, 및 (순서를 제외하고), 합성수는 소수의 곱으로 고유한 인수분해를 가진다는 것을 보였습니다.

비슷하게, 1944년에 삼차 상호관계(cubic reciprocity)를 연구하는 동안, 아이젠슈타인(Eisenstein)은 링 $\mathbb {Z} [\omega ]$을 도입했으며, 여기서 $\omega ={\frac {-1+{\sqrt {-3}}}{2}},$   $\omega ^{3}=1$는 단위의 세제곱 근(cube root of unity)입니다. 이것은 아이젠슈타인 정수(Eisenstein integer)의 링이고, 그는 그것이 여섯 개의 단위 $\pm 1,\pm \omega ,\pm \omega ^{2}$를 가지는 것과 그것이 고유한 인수분해를 가지는 것을 입증했습니다.

어쨌든, 그것은 역시 고유한 인수분해가 항상 유지되는 것은 아님을 발견했습니다. 하나의 예제는 $\mathbb {Z} [{\sqrt {-5}}]$에 의해 주어집니다. 이 링에서 우리는 다음을 가집니다:

$6=2\cdot 3=(1+{\sqrt {-5}})(1-{\sqrt {-5}}).$

이것과 같은 예제는 "소수"의 개념을 수정하게 되는 원인이 되었습니다. $\mathbb {Z} [{\sqrt {-5}}]$에서, 만약 위의 인수의 임의의 것이 곱, 예를 들어, 2 = ab로 표현될 수 있으면, a 또는 b 중의 하나는 단위여야 함을 입증할 수 있습니다. 이것이 전통적인 "소수"의 정의입니다. 역시 이들 인수 중 어떤 것도 유클리드의 보조정리를 따르지 않음을 입증할 수 있습니다; 예를 들어, 2는 (1 + √−5)도 (1 − √−5)도 나누지 않지만 그것은 그들의 곱 6을 나눕니다. 대수적 숫자 이론(algebraic number theory)에서, 2는 $\mathbb {Z} [{\sqrt {-5}}]$에서 기약(irreducible) (오직 자체 또는 단위로 나뉨)이라고 불리지만 $\mathbb {Z} [{\sqrt {-5}}]$에서 소수(prime)가 아닙니다 (만약 그것이 곱을 나누면 그것은 인수 중 하나를 나누어야 합니다). $\mathbb {Z} [{\sqrt {-5}}]$의 언급이 요구되는데 왜냐하면 2는 $\mathbb {Z}$에서 소수이고 기약이기 때문입니다. 이들 정의를 사용하여, 임의의 정수 도메인(integral domain)에서 소수는 기약이어야 함을 입증할 수 있습니다. 유클리드의 고전적 보조정리는 "정수 $\mathbb {Z}$의 링에서 모든 각 기약은 소수입니다"로 다시 표현될 수 있습니다. 이것은 역시 $\mathbb {Z} [i]$ 및 $\mathbb {Z} [\omega ]$에서 참이지만, $\mathbb {Z} [{\sqrt {-5}}]$에서 참이 아닙니다.

기약으로 인수분해가 본질적으로 고유한 링은 고유한 인수분해 도메인(unique factorization domain)이라고 불립니다. 중요한 예제는 정수에 걸쳐 또는 필드에 걸쳐 다항식 링(polynomial ring), 유클리드 도메인(Euclidean domain) 및 주요 아이디얼 도메인(principal ideal domain)입니다.

1843년에 쿠머(Kummer)는 아이디얼 숫자(ideal number)의 개념을 도입했으며, 이것은 데데킨트(Dedekind) (1876)에 의해 아이디얼(ideals)의 현대 이론, 링의 특별한 부분집합으로 더 나아가서 개발되었습니다. 곱셈은 아이디얼에 대해 정의되고, 그것들이 고유한 인수분해를 가지는 링은 데데킨트 도메인(Dedekind domain)이라고 불립니다.

비록 고유성을 보장하기 위해 몇 가지 추가적이 조건이 요구될지라도, 서수에 대해 고유한 인수분해(unique factorization for ordinals)의 버전이 있습니다.

See also

• Integer factorization – Decomposition of a number into a product – Decomposition of a number into a product
• Prime signature

References

The Disquisitiones Arithmeticae has been translated from Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.

• Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, ISBN 978-0-387-96254-2 {{citation}}: |first2= has generic name (help)
• Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8 {{citation}}: |first2= has generic name (help)

The two monographs Gauss published on biquadratic reciprocity have consecutively numbered sections: the first contains §§ 1–23 and the second §§ 24–76. Footnotes referencing these are of the form "Gauss, BQ, § n". Footnotes referencing the Disquisitiones Arithmeticae are of the form "Gauss, DA, Art. n".

• Gauss, Carl Friedrich (1828), Theoria residuorum biquadraticorum, Commentatio prima, Göttingen: Comment. Soc. regiae sci, Göttingen 6
• Gauss, Carl Friedrich (1832), Theoria residuorum biquadraticorum, Commentatio secunda, Göttingen: Comment. Soc. regiae sci, Göttingen 7

These are in Gauss's Werke, Vol II, pp. 65–92 and 93–148; German translations are pp. 511–533 and 534–586 of the German edition of the Disquisitiones.

• Baker, Alan (1984), A Concise Introduction to the Theory of Numbers, Cambridge, UK: Cambridge University Press, ISBN 978-0-521-28654-1
• Euclid (1956), The thirteen books of the Elements, vol. 2 (Books III-IX), Translated by Thomas Little Heath (Second Edition Unabridged ed.), New York: Dover, ISBN 978-0-486-60089-5
• Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001.
• A. Kornilowicz; P. Rudnicki (2004), "Fundamental theorem of arithmetic", Formalized Mathematics, 12 (2): 179–185
• Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77-171950.
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766.
• Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, ISBN 0-8176-3743-5
• Weil, André (2007) [1984]. Number Theory: An Approach through History from Hammurapi to Legendre. Modern Birkhäuser Classics. Boston, MA: Birkhäuser. ISBN 978-0-817-64565-6.
• Weisstein, Eric W. "Abnormal number". MathWorld.
• Weisstein, Eric W. "Fundamental Theorem of Arithmetic". MathWorld.

External links

• Why isn’t the fundamental theorem of arithmetic obvious?
• GCD and the Fundamental Theorem of Arithmetic at cut-the-knot.
• PlanetMath: Proof of fundamental theorem of arithmetic
• Fermat's Last Theorem Blog: Unique Factorization, a blog that covers the history of Fermat's Last Theorem from Diophantus of Alexandria to the proof by Andrew Wiles.
• "Fundamental Theorem of Arithmetic" by Hector Zenil, Wolfram Demonstrations Project, 2007.
• Grime, James. "1 and Prime Numbers". Numberphile. Brady Haran.