Докажем существование разложения числа n на простые множители, предполагая, что оно уже доказано для любого другого числа, меньшего n. Если n — простое, то существование доказано. Если n — составное, то оно может быть представлено в виде произведения двух чисел aи b, каждое из которых больше 1, но меньше n. Числа a и b либо являются простыми, либо могут быть разложены в произведение простых (уже доказано ранее). Подставив их разложение в n, получим разложение исходного числа n на простые. Существование доказано.
Докажем существование разложения числа n на простые множители, предполагая, что оно уже доказано для любого другого числа, меньшего n. Если n — простое, то существование доказано. Если n — составное, то оно может быть представлено в виде произведения двух чисел aи b, каждое из которых больше 1, но меньше n. Числа a и b либо являются простыми, либо могут быть разложены в произведение простых (уже доказано ранее). Подставив их разложение в n, получим разложение исходного числа n на простые. Существование доказано.