Докажите, что: а) любое натуральное число либо взаимно просто с заданным простым числом р, либо делится на р;​

Наибольший общий делитель НОД чисел a и p делит p

p – простое число по условию

оно делится на 1 и p (по определению протого числа)

следовательно

НОД(a, p) равен либо 1, либо p.

1. НОД(a, p)=1,  числа a и p – взаимно простые.

2. НОД(a, p)=p, а так как a делится на НОД(a, p), то a делится на p.

доказано