Докажите, что простое число при делении на 30 может давать в остатке только простое число или 1.

P=30k+r, 0lt;rlt;30. 30=2*3*5. Так как p - простое, r не может делиться ни на 2, ни на 3, ни на 5. Если бы r было составное, оно раскладывалось бы на простые множители, которые больше 5. Самое маленькое из них - это 7. Следовательно, r будет больше или равно 7^2=49, что противоречит rlt;30