Question

4. Сколько натуральных чисел N, 1 ≤ N ≤ 100, обладают свойством, что количество
натуральных чисел n ≤ N где НОД(n, N) = 1 является делителем числа N?

Answer 1

Ответ:

16.

Пошаговое объяснение:

Обозначим через f(N) количество натуральных чисел n≤N, взаимно простых с N. Требуется выяснить, сколько натуральных чисел N≤100 удовлетворяют условию f(N)|N  (f(N) делит N, то есть N  делится на f(N)).  

Ясно, что f(1)=1|1, то есть одно натуральное число с нужными свойствами найдено. Пусть N>1.

Выведем формулу для f(N). Пусть

                                       $N=p_1^{k_1}\cdot p_2^{k_2}\cdot\ldots\cdot p_m^{k_m},$

где $p_1 < p_2 < \ldots < p_m -$ простые числа,  $k_1,\ k_2,\ \ldots , \ k_m -$ натуральные числа. Существование (и единственность) такого разложения даёт основная теорема арифметики. Докажем, что

         $f(N)=(p_1-1)\cdot (p_2-1)\cdot\ldots(p_m-1)\cdot p_1^{k_1-1}\cdot p_2^{k_2-1}\cdot \ldots \cdot p_m^{k_m-1}.$    

Собственно, нам потребуется эта формула для m≤3: если m=4 или больше 4, то даже при минимальных $k_1=k_2=\ldots=k_m=1$ и минимальных $p_1=2,\ p_2=3,\ p_3=5,\ p_4=7,\ \ldots,$ имеем

                                     $N\ge 2\cdot 3\cdot 5\cdot 7 > 100.$

Поэтому в общем случае формулу доказывать не будем.

Пусть m=1, то есть N является степенью простого числа:  $N=p^k.$ Не взаимно простыми с N, но не большими N, будут числа

                                                 $p,\ 2p,\ 3p,\ \ldots,\ p^k=p\cdot p^{k-1}$

в количестве $p^{k-1}=\dfrac{N}{p}$ штук, поэтому взаимно простых с N чисел будет

                           $N-p^{k-1}=p^k-p^{k-1}=(p-1)p^{k-1}.$

Пусть m=2, то есть $N=p^k\cdot q^t.$ Не взаимно простыми с N будут числа, кратные p (в количестве $\dfrac{N}{p}$штук), и числа, кратные q (в количестве $\dfrac{N}{q}$ штук). При этом числа, кратные p·q (в количестве $\dfrac{N}{pq}$ штук), посчитаны дважды. Поэтому всего не взаимно простых с N чисел будет

 $\dfrac{N}{p}+\dfrac{N}{q}-\dfrac{N }{pq}$ штук, а тогда взаимно простых с N чисел будет

  $f(N)=N-\left(\dfrac{N}{p}+\dfrac{N}{q}-\dfrac{N}{pq}\right)=N\cdot\dfrac{pq-p-q+1}{pq}=(p-1)(q-1)p^{k-1}\cdot q^{t-1}.$

Пусть m=3, то есть $N=p^k\cdot q^t\cdot r^ u.$ Рассуждая как в предыдущем пункте, мы из $\dfrac{N}{p}+\dfrac{N}{q}+\dfrac{N}{r}$ должны вычесть $\dfrac{N}{pq}+\dfrac{N}{qr}+\dfrac{N}{rp},$ но при этом числа, кратные p·q·r, (в количестве $\dfrac{N}{pqr}$ штук) мы сначала посчитали трижды, затем трижды  вычли, поэтому это количество нужно еще раз добавить. А тогда взаимно простых с N чисел будет

             $f(N)=N-\left(\dfrac{N}{p}+\dfrac{N}{q}+\dfrac{N}{r}-\dfrac{N}{pq}-\dfrac{N}{qr}-\dfrac{N}{rp}+\dfrac{N}{pqr}\right)=$

 $=N\cdot \dfrac{pqr-qr-pr-pq+r+p+q-1}{pqr}=(p-1)(q-1)(r-1)p^{k-1}q^{t-1}r^{u-1}.$

Переходим к нашей задаче.

Если $N=p^k\Rightarrow f(N)=(p-1)\cdot p^{k-1}.$ Мы ищем числа N такие, что

                $f(N)=(p-1)p^{k-1}|N=p^k\Leftrightarrow (p-1)|p\Leftrightarrow p=2.$

Итак, к ранее найденной единице мы добавляем числа

  $2^1=2,\ 2^2=4,\ 2^3=8,\ 2^4=16,\ 2^5=32,\ 2^6=64.$

Всего найдено 1+6=7 чисел.

Если $N=p^k\cdot q^t\Rightarrow f(N)=(p-1)(q-1)p^{k-1}q^{t-1}|N=p^k\cdot q^t\Leftrightarrow (p-1)(q-1)|pq.$

Единственное четное простое число - это 2. Поэтому q>p является нечетным числом, а тогда q-1 - четное число. Поэтому pq должно быть четным числом, откуда p=2, и условие $(p-1)(q-1)|pq$ превращается в $(q-1)|2q.$ А поскольку соседние натуральные числа взаимно просты, делаем вывод, что q=3.

Поэтому добавляются числа

$2^1\cdot 3^1=6,\ 2^1\cdot 3^2=18,\ 2^1\cdot 3^3=54,\ 2^2\cdot 3^1=12,\ 2^2\cdot 3^2=36,\ 2^3\cdot 3^1=24,$

 $2^3\cdot 3^2=72,\ 2^4\cdot 3^1=48,\ 2^5\cdot 3^1=96.$

Здесь 9 чисел, плюс найденные раньше 7 чисел - суммарно 16 чисел.

Пусть $N=p^k\cdot q^t\cdot r^u\Rightarrow f(N)=(p-1)(q-1)(r-1)p^{k-1}q^{t-1}r^{u-1}.$

Надо выяснить, когда $(p-1)(q-1)(r-1)|pqr.$ Как и в предыдущем случае получаем p=2, поэтому $(q-1)(r-1)|2qr.$ Число, стоящее слева, кратно 4, а число, стоящее справа, хотя на 2 делится, но на 4 не делится. Поэтому нужных нам чисел N среди исследуемых чисел нет. Поэтому окончательный ответ - 16.