Остаток от деления на число  произведения натуральных чисел  равен остатку от деления на число  произведения , где  и  – остатки от деления на  чисел  и  соответственно.
Таким образом, остаток от деления числа
на  равен остатку от деления  на , то есть равен .Остаток от деления числа
на  равен остатку от деления  на , то есть равен .Остаток от деления числа
на  равен .Так как любое натуральное число  всегда можно представить в одном из видов: , ,  (), то  при делении на  не может давать в остатке .

Ответ: Доказательство