Euclid's lemma

Original article: w:Euclid's lemma

Not to be confused with Euclid's division lemma, Euclid's theorem, or Euclidean algorithm.

숫자 이론(number theory)에서, 유클리드의 보조정리(Euclid's lemma)는 소수(prime number)의 기본 속성을 포획하는 보조정리(lemma)입니다. 즉:

유클리드의 보조정리 — 만약 소수 p가 두 정수 a와 b의 곱 ab를 나누면, p는 그들 정수 a와 b 중 적어도 하나를 나누어야 합니다.

예를 들어, 만약 p = 19, a = 133, b = 143이면, ab = 133 × 143 = 19019이고, 이것은 19에 의해 나뉘므로, 보조정리는 133 또는 143의 하나 또는 둘 다가 마찬가지로 그래야 함을 의미합니다. 사실, 133 = 19 × 7입니다.

본질적으로, 만약 보조정리의 전제가 유지되지 않으면, 즉 p가 합성수(composite number)이면, 그 결과는 참 또는 거짓일 수 있습니다. 예를 들어, p = 10, a = 4, b = 15의 경우에서, 합성수 10은 ab = 4 × 15 = 60을 나누지만, 10은 4도 15도 나누지 않습니다.

이 속성은 산술의 기본 정리(fundamental theorem of arithmetic)의 증명에서 핵심입니다. 그것은 소수 원소(prime element), 소수를 임의의 교환 링(commutative ring)으로의 일반화를 정의하기 위해 사용됩니다. 유클리드의 보조정리는 정수에서 기약 원소(irreducible element)가 역시 소수 원소임을 보여줍니다. 그 증명은 귀납법(induction)을 사용하므로 그것은 모든 정수 도메인(integral domain)에 적용되지는 않습니다.

Formulations

$p$를 소수(prime number)로 놓고, $p$가 두 정수 $a$와 $b$의 곱을 나누는 것으로 가정합니다. (기호에서 이것은 $p\mid ab$으로 쓰입니다. 그것의 부정, $p$가 $ab$를 나누지 않는 것은 $p\nmid ab$로 쓰입니다.) 그런-다음 $p\mid a$ 또는 $p\mid b$ (또는 둘 다)입니다. 동등한(Equivalent) 명제는 다음입니다:

• 만약 $p\nmid a$ 및 $p\nmid b$이면, $p\nmid ab$입니다.
• 만약 $p\nmid a$ 및 $p\mid ab$이면, $p\mid b$입니다.

유클리드의 보조정리는 소수로부터 임의의 정수로 일반화될 수 있습니다:

Theorem — 만약 $n\mid ab$이고, $n$가 $a$와 상대적으로 소수(relatively prime)이면, $n\mid b$입니다.

이것은 일반화인데 왜냐하면 만약 $n$이 소수이면, 다음 둘 중 하나이기 때문입니다:

• $n\mid a$ 또는
• $n$이 $a$와 상대적으로 소수입니다. 이 두 번째 가능성에서, $n\nmid a$이므로 $n\mid b$입니다.

History

그 보조정리는 유클리드(Euclid)의 원론(Elements)의 책 VII에서 제안 30으로 처음 나타납니다. 그것은 초등 숫자 이론을 다루는 거의 모든 각 책에 포함되어 있습니다.

그 보조정리의 정수로의 일반화는 1681년 장 프리스테(Jean Prestet)의 책 New Elements of Mathematics에 나타났습니다.

카를 프리드리히 가우스(Carl Friedrich Gauss)의 논문 Disquisitiones Arithmeticae에서, 그 보조정리의 명제는 유클리드의 제안 14 (섹션 2)이며, 그는 이것을 정수의 소수 인수의 분해 곱 (정리 16)의 고유성을 증명하기 위해 사용하며, 그 존재를 "명백한" 것으로 인정합니다. 이 존재와 고유성으로부터 그는 그런-다음 소수를 정수로의 일반화를 추론합니다. 이러한 이유에 대해, 유클리드의 보조정리의 일반화는 때때로 가우스의 보조정리라고 참조되지만, 일부 사람들은 이 사용법이 올바르지 않다고 생각하는데, 왜냐하면 이차 잔여에 대한 가우스의 보조정리(Gauss's lemma on quadratic residues)와 혼동되어 때문입니다.

Proof

Proof using Bézout's lemma

보통의 증명은 베주의 항등식(Bézout's identity)이라고 불리는 또 다른 보조정리를 포함합니다. 이것은 만약 x와 y가 상대적으로 소수 정수(relatively prime integers)이면 (즉, 그것들이 1과 −1 이외의 공약 약수를 공유하지 않으면), 다음을 만족하는 정수 r과 s가 존재함을 말합니다:

$rx+sy=1.$

a와 n을 상대적으로 소수로 놓고, n|ab임을 가정합니다. 베주의 항등식에 의해, 다음을 만드는 r과 s가 있습니다:

$rn+sa=1.$

양쪽 변에 b를 곱하면:

$rnb+sab=b.$

왼쪽에서 첫 번째 항은 n으로 나뉘고, 두 번째 항은 ab로 나뉘며, 이것은 가설에 의해 n으로 나뉩니다. 그러므로, 그들의 합, b는 역시 n으로 나뉩니다. 이것은 위에서 언급된 유클리드의 보조정리의 일반화입니다.

Proof of Elements

유클리드의 보조정리는 유클리드의 원론(Euclid's Elements)의 책 VII에서 제안 30에서 입증됩니다. 원래 증명은 있는 그대로 이해하기 어려우므로, 우리는 Euclid (1956, pp. 319–332)로부터 주석을 인용합니다.

Proposition 19

만약 네 숫자가 비례하면, 첫 번째와 네 번째에서 생성된 숫자는 두 번째와 세 번째에서 생성된 숫자와 같습니다; 그리고, 만약 첫 번째와 네 번째에서 생성된 숫자가 두 번째와 세 번째에서 생성된 숫자와 같으면, 네 숫자는 비례합니다.

Proposition 20

그것들과 같은 비율을 갖는 그것들 중 가장 적은 숫자는 같은 비율을 갖는 그것들과 같은 횟수로 측정합니다–클수록 크고 적을수록 적습니다.

Proposition 21

서로 소수는 그것들과 같은 비율을 갖는 숫자 중 가장 작은 숫자입니다.

Proposition 29

임의의 소수는 그것이 측정하지 않는 임의의 숫자의 소수입니다.

Proposition 30

만약 두 숫자가, 서로 곱함으로써, 같은 숫자를 만들고, 임의의 소수가 그 곱을 측정하면, 역시 원래 숫자 중 하나를 측정합니다.

Proof of 30

만약 c, 하나의 소수가 ab를 측정하면, c는 a 또는 b 중 하나를 측정합니다.
c가 a를 측정하지 못함을 가정합니다.
그러므로, c, a는 서로 소수입니다.［VII. 29］
ab＝mc를 가정합니다.
그러므로 c : a ＝ b : m. ［VII. 19］
따라서 ［VII. 20, 21］ b＝nc이며, 여기서 n은 어떤 정수입니다.
그러므로 c는 b를 측정합니다.
비슷하게, 만약 c가 b를 측정하지 않으면, c는 a를 측정합니다.
그러므로 c는 두 숫자 a, b 중 하나 또는 나머지 다른 것을 측정합니다.
Q.E.D.

See also

• Bézout's identity
• Euclidean algorithm
• Fundamental theorem of arithmetic
• Irreducible element
• Prime element
• Prime number

References

• Bajnok, Béla (2013), An Invitation to Abstract Mathematics, Undergraduate Texts in Mathematics, Springer, ISBN 978-1-4614-6636-9.
• Euclid (1956), The Thirteen Books of the Elements, vol. Vol. 2 (Books III-IX), translated by Heath, Thomas Little, Dover Publications, ISBN 978-0-486-60089-5 {{citation}}: |volume= has extra text (help)- vol. 2
• Euclid (1994), Les Éléments, traduction, commentaires et notes (in French), vol. 2, translated by Vitrac, Bernard, pp. 338–339, ISBN 2-13-045568-9
• Gauss, Carl Friedrich (2001), Disquisitiones Arithmeticae, translated by Clarke, Arthur A. (Second, corrected ed.), New Haven, CT: Yale University Press, ISBN 978-0-300-09473-2
• Gauss, Carl Friedrich (1981), Untersuchungen uber hohere Arithmetik [Investigations on higher arithmetic], translated by Maser, = H. (Second ed.), New York: Chelsea, ISBN 978-0-8284-0191-3{{citation}}: CS1 maint: extra punctuation (link)
• Hardy, G. H.; Wright, E. M.; Wiles, A. J. (2008-09-15), An Introduction to the Theory of Numbers (6th ed.), Oxford: Oxford University Press, ISBN 978-0-19-921986-5
• Ireland, Kenneth; Rosen, Michael (2010), A Classical Introduction to Modern Number Theory (Second ed.), New York: Springer, ISBN 978-1-4419-3094-1
• Joyner, David; Kreminski, Richard; Turisco, Joann (2004), Applied Abstract Algebra, JHU Press, ISBN 978-0-8018-7822-0.
• Landau, Edmund; Goodman, J. E. (translator into English) (1999), Elementary Number Theory (2nd ed.), Providence, Rhode Island: American Mathematical Society, ISBN 978-0-821-82004-9 {{citation}}: |first2= has generic name (help)
• Martin, G. E. (2012), The Foundations of Geometry and the Non-Euclidean Plane, Undergraduate Texts in Mathematics, Springer, ISBN 978-1-4612-5725-7.
• Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (2nd ed.), Boston: Birkhäuser, ISBN 978-0-8176-3743-9.

External links

• Weisstein, Eric W. "Euclid's Lemma". MathWorld.