Тема . Росатом

Теория чисел на Росатоме

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела росатом

Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#119614

Для каждого натурального $n$ определим число $φ(n),$ равное количеству целых чисел $m,1 ≤m ≤ n$ взаимно простых с $n.$ Найти $φ(1947).$

Источники: Росатом - 2025, 11.3 (см. olymp.mephi.ru)

Подсказки к задаче

Подсказка 1

Заметим, что у 1947 в разложении на простые ровно 3 простых делителя. Давайте попробуем решить задачу в общем виде для чисел с 3 простыми делителями в некоторых степенях.

Подсказка 2

В данном случае будет проще посчитать, сколько всего чисел, не взаимно простых с n, и потом вычесть.

Подсказка 3

Как насчёт того, чтобы сначала отдельно посчитать количество чисел, делящихся на первый простой делитель, затем — на второй, третий, после — на первый и второй и так дальше.

Подсказка 4

А как теперь найти количество не взаимно простых, зная результаты вычислений из предыдущей подсказки? Нужно немного манипуляций с формулой включения-исключения.

Показать ответ и решение

Пусть $n =pr1⋅pr2 ⋅pr3, 1 2 3$ где $p,p ,p 1 2 3$ — различные простые числа, $r ,r ,r 1 2 3$ — их (натуральные) кратности. Количество чисел, не больших $n,$ делящихся на $p1 :$

r1−1 r2 r3 n1 = p1 ⋅p2 ⋅p3

Количество чисел, не больших $n,$ делящихся на $p : 2$

r1 r2−1 r3 n2 = p1 ⋅p2 ⋅p3

Количество чисел, не больших $n,$ делящихся на $p3 :$

r1 r2 r3−1 n3 = p1 ⋅p2 ⋅p3

Количество чисел, не больших $n,$ делящихся на $p1⋅p2 :$

n = pr1−1⋅pr2−1⋅pr3 4 1 2 3

Количество чисел, не больших $n,$ делящихся на $p1⋅p3 :$

n5 = pr11−1⋅pr22⋅pr33−1

Количество чисел, не больших $n,$ делящихся на $p2⋅p3$

n6 = pr11 ⋅pr22−1⋅pr33−1

И наконец, количество чисел, делящихся на $p1⋅p2⋅p3 :$

n7 = pr11−1 ⋅pr22−1⋅pr33−1

Общее количество чисел, не взаимно простых с $n,$ по формуле включений-исключений равно

n1+ n2+n3 − n4− n5− n6+n7 =pr11−1⋅pr22−1⋅pr33−1(p1⋅p2+ p1⋅p3+p2⋅p3− p1− p2− p3+ 1)

Тогда

φ(n)= n− n1− n2 − n3+ n4+ n5+n6 − n7 =

= pr1−1⋅pr2−1⋅pr3−1(p ⋅p ⋅p − p ⋅p − p ⋅p − p ⋅p +p + p +p − 1)= 1 2 3 1 2 3 1 2 1 3 2 3 1 2 3

= pr1−1⋅pr2−1⋅pr3−1(p1− 1)(p2− 1)(p3− 1) 1 2 3

Таким образом, при $n =1947= 3⋅11 ⋅59$ имеем

φ(1947)= (3− 1)(11− 1)(59− 1)= 1160

Ответ:

1160

Нужна консультация? Задайте нам вопрос в чате.

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

Теория чисел на Росатоме

Специальные программы

Программалояльности v2.0

Крути рулеткуи выигрывай призы!

Бесплатное онлайн-обучение

Налоговые вычеты

Специальное предложениедля учителей

Вернём деньги за курсза твою сотку на ЕГЭ

Программалояльности v2.0

Крути рулеткуи выигрывай призы!

Бесплатное онлайн-обучение

Налоговые вычеты

Специальное предложениедля учителей

Вернём деньги за курсза твою сотку на ЕГЭ

Программа
лояльности v2.0

Крути рулетку
и выигрывай призы!

Специальное предложение
для учителей

Вернём деньги за курс
за твою сотку на ЕГЭ

Программа
лояльности v2.0

Крути рулетку
и выигрывай призы!

Специальное предложение
для учителей

Вернём деньги за курс
за твою сотку на ЕГЭ