Question

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

Answer 1

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

Answer 2

Для доказательства данного утверждения воспользуемся методом от противного.

Предположим, что существует простое число p, которое при делении на 30 даёт в остатке число r, где r не является простым числом или 1. То есть p ≡ r (mod 30), где r ≠ 1 и r - не простое число.

Так как p - простое число, то оно не делится ни на одно из чисел 2, 3, 5, 6, 10, 15, которые являются делителями 30. Следовательно, p не может быть кратным ни одному из этих чисел.

Рассмотрим возможные значения r при делении на 30: 1. r = 0: это невозможно, так как простое число p не может быть кратным 30. 2. r = 2: это также невозможно, так как простое число p не может быть четным. 3. r = 3: это невозможно, так как простое число p не может быть кратным 3. 4. r = 4: это невозможно, так как простое число p не может быть кратным 2. 5. r = 5: это невозможно, так как простое число p не может быть кратным 5. 6. r = 6: это невозможно, так как простое число p не может быть кратным 2 или 3. 7. r = 8: это невозможно, так как простое число p не может быть кратным 2. 8. r = 9: это невозможно, так как простое число p не может быть кратным 3. 9. r = 10: это невозможно, так как простое число p не может быть кратным 2 или 5. 10. r = 12: это невозможно, так как простое число p не может быть кратным 2 или 3. 11. r = 14: это невозможно, так как простое число p не может быть кратным 2 или 7. 12. r = 15: это невозможно, так как простое число p не может быть кратным 3 или 5. 13. r = 16: это невозможно, так как простое число p не может быть кратным 2. 14. r = 18: это невозможно, так как простое число p не может быть кратным 2 или 3. 15. r = 20: это невозможно, так как простое число p не может быть кратным 2 или 5. 16. r = 21: это невозможно, так как простое число p не может быть кратным 3 или 7. 17. r = 22: это невозможно, так как простое число p не может быть кратным 2 или 11. 18. r = 24: это невозможно, так как простое число p не может быть кратным 2 или 3. 19. r = 25: это невозможно, так как простое число p не может быть кратным 5. 20. r = 26: это невозможно, так как простое число p не может быть кратным 2 или 13. 21. r = 27: это невозможно, так как простое число p не может быть кратным 3. 22. r = 28: это невозможно, так как простое число p не может быть кратным 2 или 7.

Таким образом, мы рассмотрели все возможные значения r и пришли к выводу, что нет простого числа p, которое при делении на 30 даёт в остатке число, отличное от простого числа или 1.

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