De eerste die de stelling bewees was Euclides. Het eerste gedetailleerde en correcte bewijs stond in de Disquisitiones Arithmeticae van Carl Friedrich Gauß.
Sommige mensen denken misschien dat de stelling overal waar is. De stelling is echter niet waar in meer algemene getallenstelsels, zoals algebraïsche gehele getallen. Dit werd voor het eerst vermeld door Ernst Kummer in 1843, in zijn werk over de laatste stelling van Fermat. Voor meer informatie daarover: lees algebraïsche getaltheorie.
Het bewijs bestaat uit twee delen: eerst tonen we aan dat elk getal kan worden geschreven als een product van priemgetallen; ten tweede tonen we aan dat als we een getal voor een tweede keer schrijven als een product van priemgetallen, de twee lijsten van priemgetallen hetzelfde moeten zijn.
Eerste deel van het bewijs
Wij tonen aan dat als niet elk getal groter dan 1 kan worden geschreven als een product van priemgetallen, wij in een soort onmogelijkheid terechtkomen. Daarna concluderen we dus dat het waar moet zijn dat elk getal kan worden geschreven als een product van priemgetallen.
Kijk nu wat er gebeurt als iemand zegt dat hij/zij een positief geheel getal groter dan 1 kent dat niet kan worden geschreven als een product van priemgetallen. In dat geval vragen we hem/haar om alle getallen groter dan 1 te noemen die niet kunnen worden geschreven als een product van priemgetallen. Een van deze getallen moet het kleinste zijn: laten we het n noemen. Natuurlijk kan dit getal n niet 1 zijn. Verder kan het geen priemgetal zijn, want een priemgetal is een 'product' van één priemgetal: zichzelf. Het moet dus een product van getallen zijn. Dus-
n = ab
waarbij zowel a als b positieve gehele getallen zijn die natuurlijk kleiner zijn dan n. Maar: n was het kleinste getal dat niet kan worden geschreven als een product van priemgetallen. Het moet dus mogelijk zijn a en b te schrijven als producten van priemgetallen, omdat ze allebei kleiner zijn dan n. Maar dan is het product
n = ab
kan ook worden geschreven als een product van priemgetallen. Dit is een onmogelijkheid omdat wij hebben gezegd dat n niet kan worden geschreven als een product van priemgetallen.
Wij hebben nu de onmogelijkheid aangetoond die bestaat als het eerste deel van de stelling niet waar zou zijn. Zo hebben wij nu het eerste deel van de stelling bewezen.
Tweede deel van het bewijs
Nu moeten we bewijzen dat er maar één manier is om een positief getal groter dan 1 te schrijven als een product van priemgetallen.
Hiervoor gebruiken wij het volgende lemma: als een priemgetal p een product ab deelt, dan deelt het a of het deelt b (lemma van Euclides). We bewijzen nu eerst dit lemma. Stel nu dat p niet deelt in a. Dan zijn p en a coprime en hebben we de identiteit van Bezout die zegt dat er gehele getallen x en y moeten zijn zodat
px + ay = 1.
Alles vermenigvuldigen met b geeft
pbx + aby = b,
Vergeet niet dat ab gedeeld kan worden door p. Dus nu hebben we aan de linkerkant twee termen die deelbaar zijn door p. Dus de term aan de rechterkant is ook deelbaar door p. We hebben nu bewezen dat als p a niet deelt, hij b moet delen.
Nu zullen we bewijzen dat we een geheel getal groter dan 1 slechts op één manier kunnen schrijven als een product van priemgetallen. Neem twee producten van priemgetallen A en B die dezelfde uitkomst hebben. We weten dus voor de uitkomst van de producten dat A = B. Neem een willekeurige priem p uit het eerste product A. Die deelt A, dus die deelt ook B. Door verschillende keren het lemma te gebruiken dat we net bewezen hebben, kunnen we zien dat p dan minstens één factor b van B moet delen. Maar de factoren zijn zelf allemaal priemgetallen, dus ook b is priem. Maar we weten dat p ook priem is, dus p moet gelijk zijn aan b. Dus nu delen we A door p en delen we ook B door p. En we krijgen een resultaat als A* = B*. Opnieuw kunnen we een priem p nemen uit het eerste product A* en vaststellen dat die gelijk is aan een getal in het product B*. Als we zo doorgaan, zien we aan het eind dat de priemfactoren van de twee producten precies gelijk moeten zijn. Dit bewijst dat we een positief geheel getal slechts op één unieke manier kunnen schrijven als een product van priemgetallen.
