Teorema fonamental de l'aritmètica

A Disquisitiones Arithmeticae (1801) Gauss va demostrar el teorema de la factorització única i el va utilitzar per demostrar la llei de reciprocitat quadràtica.

El teorema fonamental de l'aritmètica afirma que

Sigui $a$ un nombre enter diferent de $0,1,-1$. Existeixen nombres primers positius $p_{1},...,p_{n}$ (amb $n\geq 1$) tals que $a=\pm p_{1}\cdot p_{2}\cdot ...\cdot p_{n}$ i són únics llevat de l'ordre.

Aquesta expressió d'un enter com a producte de nombres primers s'anomena factorització. Per exemple:

6936 = 2³ · 3 · 17²

1200 = 2⁴ · 3 · 5²

i cap altra factorització d'aquests nombres és possible. Aquest procés demostra que els primers es poden considerar els elements bàsics a partir dels quals es construeixen tots els enters; en concret, ens dona un coneixement complet de tots els factors d'un nombre. Per exemple, en el cas del 6936, de la factorització anterior, que és única, se sap que tots els possibles factors (no primers) de 6936 són:

2^a · 3^b · 17^c

amb 0 ≤ a ≤ 3, amb 0 ≤ b ≤ 1 i amb 0 ≤ c ≤ 2. Això dona un total de 4 · 2 · 3 = 24 factors.

Demostració

La primera demostració es deu a Euclides, i consisteix en dues parts: primer cal demostrar que tot nombre es pot escriure com a producte de nombres primers i, en segon lloc, demostrar que aquest producte és únic, excepte per l'ordre dels productes.

Suposem que hi hagués enters que no es poden escriure com a producte de primers i suposem també que n sigui el més petit d'aquests enters. Com n no pot ser igual a 1 (pel que hem dit abans) ni pot ser un primer, ja que qualsevol primer és producte d'ell mateix, ha de ser un nombre compost i, per tant, el podem escriure com

n = ab

on a, b són enters positius més petits que n. Com que n era l'enter més petit que no es podia escriure com a producte de primers, resulta que a, b sí que es poden escriure com a producte de primers:

a = p₁p₂p₃...

b = q₁q₂q₃...

i, per tant:

n = ab = p₁p₂p₃...q₁q₂q₃...

És a dir, que n sí que es pot escriure com a producte de primers, contradient la suposició i demostrant que, efectivament, tot enter es pot escriure com a producte de primers.

Ara falta demostrar la unicitat del producte en primers. Se sap que si un nombre primer p divideix un producte ab, llavors divideix a o divideix b (lema d'Euclides). Ara suposem que existeixen dos productes de nombres primers que donen el mateix nombre enter i suposem que p és un primer del primer producte; aquest p divideix el primer producte i, per tant, també el segon. Llavors també ha de dividir almenys un factor del segon producte. Però tots els factors són primers, no divisibles per ningú més que ells mateixos. Això només deixa la possibilitat que p també sigui un dels factors del segon producte. Continuant amb tots els factors veuríem que tots són iguals.

Generalització

Els anells on es compleix aquesta propietat que tot element es pot factoritzar de manera única en producte d'elements primers s'anomenen anells factorials o anells de factorització única. El teorema fonamental de l'aritmètica demostra que l'anell dels nombres enters és un anell factorial, però n'hi ha d'altres com els anells de polinomis, els anells principals, etc.

Història

El teorema fonamental es pot derivar del llibre VII, proposicions 30, 31 i 32, i del llibre IX, proposició 14 dels Elements d’Euclides.

«	Si dos nombres multiplicant-se entre si formen algun nombre, i qualsevol nombre primer mesura el producte, també mesurarà un dels nombres originals.	»
— Euclides, Teorema fonamental de l'aritmètica, Elements Llibre VII, Proposició 30

(En terminologia moderna: si un nombre primer p divideix el producte ab, aleshores p divideix a o b o tots dos.) La Proposició 30 es coneix com el lema d'Euclides, i és la clau en la demostració del teorema fonamental de l'aritmètica.)

«	Qualsevol nombre compost es mesura per algun nombre primer.	»
— Euclides, Teorema fonamental de l'aritmètica, Elements Llibre VII, Proposició 31

(En terminologia moderna: tot enter més gran que la unitat es divideix per algun nombre primer.) La proposició 31 es demostra directament per descens infinit.)

«	Qualsevol nombre és primer o es mesura per algun nombre primer.	»
— Euclides, Teorema fonamental de l'aritmètica, Elements Llibre VII, Proposició 32

La proposició 32 yyyderiva de la proposició 31 i demostra que la descomposició és possible.

«	Si un nombre és el més petit que es mesura per nombres primers, no es mesurarà per cap altre nombre primer excepte els que el van mesurar originalment.	»
— Euclides, Teorema fonamental de l'aritmètica, Llibre dels Elements IX, Proposició 14

(En terminologia moderna: un mínim comú múltiple de diversos nombres primers no és un múltiple de cap altre nombre primer.) El llibre IX, proposició 14, es deriva del llibre VII, proposició 30, i demostra parcialment que la descomposició és única, un punt assenyalat críticament per André Weil. Weil (2007, p. 5) Fins i tot a Euclides, no trobem una afirmació general sobre la singularitat de la factorització d'un enter en nombres primers; segurament ell potser n'era conscient, però tot el que té és una afirmació (Eucl.IX.I4) sobre el mínim comú de nombres primers de qualsevol nombre de nombres primers donats. De fet, en aquesta proposició els exponents són tots iguals a un, de manera que no es diu res per al cas general.)

Mentre Euclides va fer el primer pas en el camí cap a l'existència de la factorització prima, Kamal al-Din al-Farisí va fer el pas final i va enunciar per primera vegada el teorema fonamental de l'aritmètica.

L'article 16 de les Disquisitiones Arithmeticae de Gauss sembla ser la primera prova de la part d'unicitat del teorema.

Aplicacions

Representació canònica d'un enter positiu

Tot enter positiu n > 1 es pot representar exactament d'una manera com a producte de potències primeres

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

on p₁ < p₂ <... < p_k són nombres primers i els n_i són nombres enters positius. Aquesta representació s'estén habitualment a tots els nombres enters positius, inclòs 1, mitjançant la convenció que el producte buit és igual a 1 (el producte buit correspon a k = 0).

Aquesta representació s'anomena representació canònica de n, o la forma estàndard de n. Per exemple,

999 = 3 ³ × 37,

1000 = ^2/3 × ^5/3,

1001 = 7 × 11 × 13.

Els factors p⁰ = 1 es poden inserir sense canviar el valor de n (per exemple, 1000 = 2³×3⁰×5³). De fet, qualsevol enter positiu es pot representar de manera única com un producte infinit pres sobre tots els nombres primers positius, com

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

on un nombre finit dels n_i són enters positius, i els altres són zero.

Permetre exponents negatius proporciona una forma canònica per als nombres racionals positius.

Operacions aritmètiques

La demostració d'unicitat utilitza el lema d'Euclides (Elements VII, 30): si un nombre primer divideix el producte de dos nombres enters, aleshores ha de dividir almenys un d'aquests nombres enters.

Existència

Cal demostrar que tot enter més gran que 1 és primer o un producte de nombres primers. Sigui n un enter més gran que 1 i fem la suposició inductiva que tot enter més gran que 1 i més petit que n és primer o un producte de nombres primers. Si n és primer, no hi ha res més a demostrar. Altrament, hi ha enters a i b, on n = a b, i 1 < a ≤ b < n. Per la hipòtesi inductiva, a = p₁ p₂ ⋅⋅⋅ p_j i b = q₁ q₂ ⋅⋅⋅ q_k són productes de nombres primers. Però aleshores n = a b = p₁ p₂ ⋅⋅⋅ p_j q₁ q₂ ⋅⋅⋅ q_k és un producte de nombres primers.

Singularitat

Suposem, al contrari, que hi ha un nombre enter que té dues factoritzacions primeres diferents. Sigui n el menor d'aquests nombres enters i escrivim n = p₁ p₂... p_j = q₁ q₂... q_k n = p₁ p₂... p_j = q₁ q₂... q_k n = p₁ p₂... p_j = q₁ q₂... q_k, on cada p_i i q_i és primer. Veiem que p₁ divideix q₁ q₂... q_k q₁ q₂... q_k, de manera que p₁ divideix algun q_i pel lema d'Euclides. Sense pèrdua de generalitat, diguem que p₁ divideix q₁ Com que p₁ i q₁ són tots dos primers, es dedueix que p₁ = q₁ Tornant a les nostres factoritzacions de n, podem cancel·lar aquests dos factors per concloure que p₂... p_j = q₂... q_k p₂... p_j = q₂... q_k p₂... p_j = q₂... q_k. Ara tenim dues factoritzacions primeres diferents d'un enter estrictament més petit que n, cosa que contradiu la minimalitat de n.

Unicitat sense el lema d'Euclides

El teorema fonamental de l'aritmètica també es pot demostrar sense utilitzar el lema d'Euclides. La demostració que segueix està inspirada en la versió original de l’algoritme euclidià d'Euclides.

Suposem que $s$ és el nombre enter positiu més petit que és el producte de nombres primers de dues maneres diferents. A més, això implica que $s$, si existeix, ha de ser un nombre compost més gran que $1$ Ara, si

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

Cada $p_{i}$ ha de ser diferent de cada $q_{j}.$ Altrament, si dius $p_{i}=q_{j},$ aleshores existiria algun nombre enter positiu $t=s/p_{i}=s/q_{j}$ que és més petit que s i té dues factoritzacions primeres diferents. També es pot suposar que $p_{1}<q_{1},$ intercanviant les dues factoritzacions, si cal.

Configuració $P=p_{2}\cdots p_{m}$ i $Q=q_{2}\cdots q_{n},$ un té $s=p_{1}P=q_{1}Q.$ També, des que $p_{1}<q_{1},$ un té $Q<P.$ Aleshores es dedueix que

$s-p_{1}Q=(q_{1}-p_{1})Q=p_{1}(P-Q)<s.$

Com que s'ha suposat que els enters positius menors que s tenen una factorització prima única, $p_{1}$ ha de produir-se en la factorització de qualsevol de les dues $q_{1}-p_{1}$ o Q Aquest darrer cas és impossible, ja que Q, en ser més petit que s, ha de tenir una factorització prima única, i $p_{1}$ difereix de cada $q_{j}.$ El primer cas també és impossible, ja que, si $p_{1}$ és un divisor de $q_{1}-p_{1},$ també ha de ser un divisor de $q_{1},$ cosa que és impossible com $p_{1}$ i $q_{1}$ són nombres primers diferents.

Per tant, no pot existir un nombre enter més petit amb més d'una factorització prima diferent. Cada nombre enter positiu ha de ser o bé un nombre primer en si mateix, que es factoritzaria de manera única, o bé un compost que també es factoritzaria de manera única en nombres primers, o en el cas de l'enter $1$, no factoritza en cap nombre primer.

Bibliografia

• Gauss, Carl Friedrich. Disquisitiones Arithemeticae (Second, corrected edition). Traducció: Arthur A. Clarke. New York: Springer, 1986. ISBN 978-0-387-96254-2. 
• Hardy, G. H.; Wright, E. M.. An Introduction to the Theory of Numbers. 6a. Oxford: Oxford University Press, 2008 [1a. ed. 1938]. ISBN 978-0-19-921986-5. 
• Long, Calvin T.. Elementary Introduction to Number Theory. 2a. Lexington: D. C. Heath and Company, 1972. LCCN 77-171950. .
• Pettofrezzo, Anthony J.; Byrkit, Donald R. Elements of Number Theory. Englewood Cliffs: Prentice Hall, 1970. LCCN 77-81766. .
• Riesel, Hans. Prime Numbers and Computer Methods for Factorization (second edition) (en anglès). Boston: Birkhäuser, 1994. ISBN 0-8176-3743-5. 
• Weil, André. Number Theory: An Approach through History from Hammurapi to Legendre. Boston, MA: Birkhäuser, 2007 [1a. ed. 1984] (Modern Birkhäuser Classics). ISBN 978-0-817-64565-6. 
• Euclides Dover. The thirteen books of the Elements. 2 (Llibres III-IX). 2a, 1956. ISBN 978-0-486-60089-5.