Задача 4. p – простое число. Сколько существует натуральных чисел а) мень- ших р и взаимно простых с ним; б) меньших р^2 и взаимно простых с ним?

Взаимно простые числа - не имеющие общих делителей, кроме 1.

a) Так как p - простое, то это все натуральные числа, меньшие p, то есть их p - 1.

б) p^2 не взаимно простое с p*k, где k - натуральное число, меньшее или равное p, значит меньших p^2 - p.

а) p - 1

б) p^2 - p

Объяснение:

а) Метод решето Эратосфена

б) среди чисел p^2 получится p чисел кратных p. их надо исключить, так как они не будут взаимно простыми с p, в отличии от остальных цифр