Question

Скільки існує натуральних чисел менших від квадрата простого числа p і взаємно простих з ним

Answer 1

Ответ:

Кількість натуральних чисел, менших від квадрата простого числа p і взаємно простих з ним, можна знайти за допомогою функції Ейлера (фі-функція).

Функція Ейлера (фі(n)) визначається як кількість натуральних чисел, менших або рівних n і взаємно простих з n.

В даному випадку, нам потрібно знайти фі(p^2), де p - просте число. Оскільки p - просте число, то всі числа, менші за p, є взаємно простими з ним. Тому фі(p) = p - 1.

Тепер ми можемо знайти фі(p^2):

фі(p^2) = p^2 * (1 - 1/p) = p^2 * (p - 1)/p = p * (p - 1)

Отже, кількість натуральних чисел, менших від квадрата простого числа p і взаємно простих з ним, дорівнює p * (p - 1).