Demostración: Sea n cualquier entero mayor que 1. Consideremos el conjunto S de todos los enteros positivos, diferentes que 1, que dividen a n. Com...

Demostración: Sea n cualquier entero mayor que 1. Consideremos el conjunto S de todos los enteros positivos, diferentes que 1, que dividen a n. Como n n y n 1, entonces existe al menos un elemento en S. Por tanto, por el principio del buen orden para los enteros, S tiene un elemento que es el más pequeño; llamado p. Afirmamos que p es primo. Supongamos que p no es primo. Entonces existen enteros a y b con 1 a p, 1 b p y p ab. Por definición de división, a p. También p n porque p está en S y cada elemento de S divide a n. Por tanto, a p y p n y así, por transitividad de divisibilidad, a n. Consecuentemente, a S. Pero esto contradice el hecho de que a p y que p sea el elemento más pequeño de S. [Esta contradicción muestra que la suposición de que p no es primo, es falsa.] Entonces p es primo y hemos demostrado la existencia de un número primo que divide a n.