Ответ:

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). Пусть

                                       [tex]N=p_1^{k_1}\cdot p_2^{k_2}\cdot\ldots\cdot p_m^{k_m},[/tex]

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

         [tex]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}.[/tex]    

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

                                     [tex]N\ge 2\cdot 3\cdot 5\cdot 7 > 100.[/tex]

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

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

                                                 [tex]p,\ 2p,\ 3p,\ \ldots,\ p^k=p\cdot p^{k-1}[/tex]

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

                           [tex]N-p^{k-1}=p^k-p^{k-1}=(p-1)p^{k-1}.[/tex]

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

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

  [tex]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}.[/tex]

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

             [tex]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)=[/tex]

 [tex]=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}.[/tex]

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

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

                [tex]f(N)=(p-1)p^{k-1}|N=p^k\Leftrightarrow (p-1)|p\Leftrightarrow p=2.[/tex]

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

  [tex]2^1=2,\ 2^2=4,\ 2^3=8,\ 2^4=16,\ 2^5=32,\ 2^6=64.[/tex]

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

Если [tex]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.[/tex]

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

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

[tex]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,[/tex]

 [tex]2^3\cdot 3^2=72,\ 2^4\cdot 3^1=48,\ 2^5\cdot 3^1=96.[/tex]

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

Пусть [tex]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}.[/tex]

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