Существуют ли составные числа, которые нельзя разложить на простые множители?

Короткий ответ: нет, среди натуральных чисел таких не бывает. Любое составное натуральное число обязательно разлагается на простые множители. Это утверждение — классическая «Основная теорема арифметики»: каждое число $n>1$ либо само простое, либо представимо в виде произведения простых, причём такое представление единственно с точностью до порядка множителей.

Почему это так (эскиз доказательства «от противного»). Предположим, что есть наименьшее составное число $n$, которое нельзя разложить на простые. Так как $n$ составное, $n=ab$ с $1$. Если $a$ простое — мы уже начали разложение; остаётся разложить $b$, но $b$, значит по минимальности $n$ у $b$ разложение существует — противоречие. Если $a$ составное, у него по той же причине есть разложение на простые, а значит есть и у $n=ab$ — снова противоречие. Следовательно, такого $n$ не существует.

Уникальность («те же самые простые, только в другом порядке») вытекает из леммы Евклида: если простое $p$ делит произведение $ab$, то оно делит хотя бы один из множителей. С её помощью два разных разложения одного и того же числа согласуются по простым множителям.

Пара оговорок:

• Число 1 — ни простое, ни составное, поэтому вопросы про «разложение» его не касаются.

• Для отрицательных целых добавляется только знак: $-n=(-1)\cdot n$, а дальше разложение $n$ на простые.

• На практике факторизацию очень больших чисел бывает трудно найти алгоритмически (это основа некоторых криптосхем), но это вопрос вычислительной сложности, а не существования разложения.

Итого: всякое составное натуральное число раскладывается на простые множители, и делает это единственным образом с точностью до порядка.