Тема Остатки и сравнения по модулю

Функция Эйлера и теорема Эйлера из ТЧ

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

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

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

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

Подтемы раздела остатки и сравнения по модулю

Решаем задачи

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

Задача 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

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 2#127166

Покажите, что при всех натуральных $a,n> 1$ число $φ(an − 1)$ делится на $n$ .

Показать доказательство

Рассмотрим модуль $m= an− 1.$ Заметим, что:

n НОД(a − 1,a)= НОД (1,a)= 1

Значит, применима теорема Эйлера $aφ(m) ≡ 1 (mod m).$

С другой стороны $ordm a= n,$ так как при $k <n$ имеем $ak < an− 1.$ Тогда получаем, что $n$ делит $φ(an− 1),$ что и требовалось.

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

Задача 3#76655

Сумма всех натуральных делителей числа $n$ более чем в 100 превосходит само число $n$ . Докажите, что есть сто идущих подряд чисел, каждое из которых имеет общий делитель с $n$ больший 1.

Источники: ЮМШ-2023, 11 класс, отборочный тур (см. yumsh.ru) | ЮМШ-23/24, 11 класс, 1 отборочный тур (см. yumsh.ru)

Показать доказательство

Сначала докажем лемму.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма.

Пусть $φ (n)$ - функция Эйлера числа $n.$ (Количество чисел от $1$ до $n$ взаимно простых с $n.$ ) Тогда для любого натурального числа $n >1$ справедливо неравенство

∑ n2 d < φ(n)- d|n

_________________________________________________________________________________________________________________________________________________________________________________

Доказательство леммы.

Запишем сумму делителей числа через произведение сумм степеней его простых делителей. Если $n =pα1pα2...pαk, 1 2 k$ то

∑ 2 α1 2 α2 2 αk d =(1+ p1+p1+ ...+ p1 )(1+ p2+ p2+ ...+ p2 )...(1+ pk +pk+ ...+ pk ) d|n

Используя формулу суммы геометрической прогрессии, получаем:

∑ d= (1+ p + p2 +...+ pα1)(1+ p +p2+ ...+ pα2)...(1+ p +p2+ ...+ pαk)= d|n 1 1 1 2 2 2 k k k

(pα11+1 − 1)(pα22+1− 1)...(pαk+1− 1) = ----(p1−-1)(p2-− 1)...(pkk− 1)--.

Функция Эйлера вычисляется по формуле $φ(n)=pα11−1(p1− 1)pα22−1(p2− 1)...pαkk− 1(pk− 1).$ Тогда чтобы получить $φ(n)$ в знаменателе, домножим числитель и знаменатель на $pα11−1pα22−1...pαkk−1$

(pα11+1−-1)(pα22+1−-1)...(pαkk+1−-1)= (p1− 1)(p2− 1)...(pk− 1)

α1−1 α2−1 αk−1 α1−1 α2−1 αk−1 = p1--p2α1−.1..pk--(pα12−1-− 1)(p2-α−k−11)...(pk---−-1)= p1 (p1− 1)p2 (p2− 1)...pk (pk− 1)

(p2α1 − pα1−1)(p2α2− pα2−1)...(p2αk− pαk−1) p2α1p2α2...p2αk n2 = --1----1-----2--φ(2n)------k----k----< -1--2φ(n)--k--= φ(n)

_________________________________________________________________________________________________________________________________________________________________________________

Решение задачи.

По условию и лемме

∑ -n2- 100n < d|nd< φ(n).

Тогда

100n< -n2-⇒ φ(n)< n-. φ(n) 100

То есть количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $-n- 100.$

Рассмотрим два случая: $n$ делится на $100$ и $n$ не делится на $100.$

1. Число $n$ делится на $100.$ Тогда можно разбить числа от $1$ до $n$ на $n-- 100$ групп по $100$ идущих подряд чисел. Если количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $n-- 100$ , то хотя бы в одной группе не будет числа взаимно простого с $n$

2. Число $n$ не делится на $100.$ Тогда среди чисел $2$ до $n$ можно выделить $-n- [100]$ групп по $100$ идущих подряд чисел. Если в каждой группе будет число взаимно простое с $n$ , то чисел взаимно простых с $n$ хотя бы $n [100]+ 1$ ( $1$ тоже взаимно проста с $n$ ). Это противоречит тому, что количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $n 100-$

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

Задача 4#102509

Среди натуральных чисел, не превосходящих $n= pα1pα2...pαm > 1, 1 2 m$ выбрали все такие $a,$ для которых $n$ взаимно просто с каждым из чисел $a,a+1.$ Докажите, что количество выбранных чисел равно

( 2 )( 2) ( 2) n 1− p1 1− p2 ... 1− pm-

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

Подсказка 1

Функция из условия похожа на функции Эйлера, так что можно применить похожие идеи. Для простых чисел нетрудно понять, что формула верна. Теперь нужно доказать мультипликативность функции.

Подсказка 2

Рассмотрим прямоугольник со взаимно простыми сторонами a и b. Отметим те столбцы, номера которых взаимно просты с а. Сколько тогда чисел, подходящих с точки зрения b, в таких столбцах?

Показать доказательство

Будем обозначать эту функцию за $φ′.$ Посчитаем сначала её для степени простого числа $pα.$ У нас есть ровно $p− 2$ остатка таких, что $a$ и $a+ 1$ не делятся на $p,$ так что $′ α α−1 φ (p )= (p − 2)p .$ Теперь покажем, что $′ φ$ мультипликативна. Пусть $(a,b)=1,$ покажем, что $′ ′ ′ φ (ab)= φ(a)φ (b).$ Представим $ab$ в виде прямоугольной таблицы $a ×b$ $(a$ столбцов), отметим столбцы, для номеров которых $x, x+ 1$ взаимно просты с $a.$ Расположим числа слева-направо и сверху-вниз: в строке $x$ столбце $y$ стоит число $a(x− 1)+y.$ Тогда взаимно просты с $a$ будут клетки, которые стоят в отмеченных столбцах. Теперь рассмотрим, какие остатки по модулю $b$ встречаются в рамках одного столбца. Там стоят числа вида $a0 +ax.$ Из взаимной простоты $a$ и $b$ получаем, что все эти остатки различны. Значит, в одном столбцу нам подойдёт ровно $′ φ(b)$ чисел. Таким образом, всего подходящих чисел как раз $′ ′ φ (a)φ (b)$ (поскольку столбцов $′ φ (a)).$ Теперь остаётся сказать, что для простых $p$ верна формула из условия, значит, и для составных тоже.

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

Задача 5#102510

Докажите, что при $n >6$ выполнено неравенство $φ(n)≥ √n.$

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

Подсказка 1:

Попробуйте сначала решить задачу для простого случая, когда n имеет один простой делитель, то есть является степенью простого числа. Посчитайте для него функцию Эйлера и ручками докажите неравенство(всегда ли работает эта оценка..?).

Подсказка 2:

Чтобы обобщить до произвольного n, достаточно вспомнить, что функция Эйлера мультипликативна. И не забудьте про случай, когда в разложении есть двойка в точности в первой степени.

Показать доказательство

Докажем неравенство для каждого случая, когда $n= pα$ для некоторого простого $p$ и натурального $α.$ Действительно,

α α−1 √ -α φ (p )= p (p− 1)≥ p

верно при $α > 1,$ поскольку $α− 1≥ α. 2$ При $α= 1$ неравенство имеет вид

√ - p− 1 ≥ p

что верно при $p>2.$

Теперь докажем утверждение задачи для произвольного $n.$ Пусть

n= pα1pα2...pαm 1 2 m

Тогда, в силу мультипликативности функции Эйлера, имеем

φ(n)=φ (pα1pα2...pαm)= φ(pα1)⋅φ(pα2)⋅...⋅φ (pαm) 1 2 m 1 2 m

Наконец, по доказанному неравенству для степеней простых чисел, данное значение не меньше, чем

∘ ---∘ --- ∘---- pα11⋅ pα22... pαmm = √n

что доказывает исходное неравенство, если среди простых множителей нет двойки или она хотя бы во второй степени. Пусть теперь есть двойка в точности в первой степени. Тогда хотим улучшить оценку для какого-то простого на $φ (pα)≥ √2pα.$ Если $α≥ 2, p≥ 3,$ то $α − 1 ≥ α 2$ и $- p− 1> √2.$ Если же $α= 1$ и $p≥ 5,$ то $p− 1≥ √2p.$ Окончательно, заметим, что раз $n > 6,$ то в нём или двойка в степени не менее $2,$ или есть простое число, большее $3,$ или тройка в степени больше $1,$ так что оценка верна.

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

Задача 6#102511

Изначально в ряд написаны $2$ единицы. Раз в минуту между каждыми двумя соседними числами записывается их сумма. Докажите, что любое натуральное $n> 1$ встретится ровно $φ(n)$ раз через $n$ минут.

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

Подсказка 1

Когда может появиться число n? Только если подряд написаны 2 числа a и b такие, что b = n - a. Мы хотим, чтобы таких пар было ровно фи(n). Какое смелое предположение можно сейчас сделать?

Подсказка 2

Можно предположить, что если натуральные числа a и b взаимно просты, то пара (a, b) встречается в таблице ровно один раз; если же a и b имеют общий делитель (отличный от 1), то пара (a, b) не встретится в таблице ни разу. Как из этого предположения следует задача? Как это можно доказать?

Подсказка 3

Проведите доказательство сформулированного утверждения при помощи индукции по max(a, b).

Показать доказательство

Выпишем подряд строки чисел, образующиеся в результате очередного шага. Получим некоторую таблицу. Попробуем выяснить, сколько раз в $n$ -й строке этой таблицы встретится число $n.$ Будем говорить, что в нашей таблице встречается пара натуральных чисел $(a,b),$ если числа $a$ и $b$ стоят рядом в одной строке, причём $b$ справа от $a.$

______________________________________________________________________________________________________________________________________________________

Лемма. Если натуральные числа $a$ и $b$ взаимно просты, то пара $(a,b)$ встречается в таблице ровно один раз; если же $a$ и $b$ имеют общий делитель (отличный от $1),$ то пара $(a,b)$ не встретится в таблице ни разу.

Доказательство. Индукция по $m = max{a,b}.$ База $m =2$ очевидна. Шаг индукции. Пусть $a ≤b= m$ (случай $a >b$ аналогичен). Пара $(a,b)$ может встретиться в таблице в том и только том случае, когда в ней встречалась пара $(a,b− a).$ Числа $(a,b)$ и $(a,b− a)$ являются одновременно либо взаимно простыми, либо нет. Для пары $(a,b− a)$ утверждение справедливо по предположению индукции. Поэтому утверждение верно и для пары $(a,b).$

______________________________________________________________________________________________________________________________________________________

Каждый раз, когда $n$ пишется как сумма двух соседних чисел $a$ и $b= n− a$ , оно встречается в парах $(a,n)$ и $(n,n− a).$ Мы доказали, что это бывает ровно один раз для каждого $a,$ меньшего $n$ и взаимно простого с ним (тогда, конечно, и $n− a$ взаимно просто с $n).$ Итак, каждое число $n$ будет написано на отрезке столько раз, сколько существует натуральных чисел, меньших $n$ и взаимно простых с ним, что и требовалось доказать.

Курсы

Всё необходимое для достижения цели

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

Задача 7#102513

Докажите, что существует такое натуральное число $n,$ что уравнение $φ(x)=n$ имеет не менее $2024$ решений.

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

Подсказка 1

Нам нужно найти много чисел, у которых одинаковая функция Эйлера, при этом мы знаем про её мультипликативность. Как это задействовать?

Подсказка 2

Если у двух чисел в паре совпадают функции Эйлера, то мы можем перемножать числа из разных пар такого вида как хотим при условии взаимной простоты.

Показать доказательство

Основная идея: пусть $φ(a)= φ(b)$ и $φ(c)=φ(d),$ причём $a,b$ взаимно просты с $c,d.$ Тогда $φ(ac)= φ(ad)=φ(bc)= φ(bd).$ Значит, нам достаточно придумать $11$ таких пар чисел и взять все их комбинации произведений, ведь $2048> 2024.$ Будем брать тройки простых чисел $p,q,r$ такие, что $p− 1= (q− 1)(r− 1).$ Нам подойдёт такое:

1.: $2⋅599$ и 599
2.: $3⋅157$ и 313
3.: $5⋅89$ и 353
4.: $7⋅73$ и 433
5.: $11⋅71$ и 701
6.: $13⋅79$ и 937
7.: $17⋅59$ и 929
8.: $19⋅43$ и 757
9.: $23⋅47$ и 1013
10.: $29⋅37$ и 1009
11.: $31⋅41$ и 1201

Вот мы предъявили нужные нам пары чисел, у которых одинаковая функция Эйлера. Тогда выбирая один из двух вариантов в паре и перемножая их, получим какие-то число. Они различны, их $2048$ и у них одинаковая функция Эйлера, что мы и хотели.

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

Задача 8#103205

Пусть $n$ — составное число такое, что существует взаимно простое с ним натуральное число $b,$ принадлежащее $[1;n],$ для которого не выполнено $n−1 b ≡ 1 (mod n).$ Докажите, что тогда среди чисел от $1$ до $n$ найдётся не более $φ(n) 2$ чисел $a:$ $n−1 a ≡ 1 (mod n).$

Показать доказательство

Рассмотрим число $c$ такое, что $(n,c)= 1$ и $c ∈[1;n].$ Тогда видно, что только одно из чисел $cn−1$ и $(bc)n−1$ может быть сравнимо с единицей по модулю $n.$ А любое число в промежутке $[1;n]$ не взаимно простое с $n$ точно не может в $n− 1$ степени давать единицу по модулю $n.$ Откуда сразу следует, что чисел $a$ не более $φ(n)∕2.$

______________________________________________________________________________________________________________________________________________________

Замечание. Эта задача связана с тестом простоты Ферма, в котором мы пытаемся определить простое ли число $n,$ выбрав случайно число в промежутке $[1;n],$ и проверить верно ли $n− 1 a ≡ 1 (mod n).$ Данная задача как раз говорит о том, что если существует число $b$ из условия, то с хорошей вероятностью нам выдаст нужное число $a,$ то есть $n−1 a ≡ 1$ неверно, а значит, $n$ составное. Оказывается число $b$ из условия задачи может не существовать и по составному модулю, такие числа называют числами Кармайкла. Предлагается подумать о том, как тогда проверять простое ли число. Для этого также есть именной вероятностный тест, а именно тест Соловея-Штрассена.

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

Задача 9#68523

Найдите все тройки взаимно простых в совокупности натуральных чисел $(a,b,c)$ таких, что для любого натурального $n$ число $n n n 2 (a + b +c )$ делится на $ab+bc+ ca$ .

Источники: 24 Кубок Колмогорова

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

Подсказка 1

Необходимо подобрать удобный показатель. Для какого n левая часть ведет себя понятным образом по модулю ab+bc+ca?

Подсказка 2

Существует показатель n, по которому каждое из n-степеней чисел a, b, c сравнимо с 1. Как он определяется?

Подсказка 3

Значением функции Эйлера в точке ab+bc+ca. Какой вывод можно сделать из рассмотрения данного показателя?

Подсказка 4

Несложно показать, что a и ab+bc+ca взаимно просты, аналогично для b, c. Тогда при данном показателе имеем 9 кратно ab+bc+ca. Осталось найти подходящие a, b, c.

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

Для начала покажем, что $(a,ab+ bc +ca)= 1.$ Пусть $a ..p .$ и $a(b+c)+ bc ..p. .$ Тогда или $b,$ или $c$ делится на $p.$ Но тогда так как $.. a+ b+ c.p,$ то все три переменные делятся на $p,$ что невозможно по условию. Значит, $(a,ab+ bc+ ca)=(b,ab+ bc+ca)= (c,ab+bc+ ca)= 1.$ Подставим $n= φ(ab+bc+ ca),$ получим

φ(ab+bc+ca) φ(ab+bc+ca) φ(ab+bc+ca)2 2 (a +b +c ) ≡ (1+1 +1) ≡ 9 (mod ab+ bc+ca)

Отсюда получаем, что $9..ab+bc+ ca. .$ Если $ab+bc+ ca =3,$ то все переменные равны $1.$ Если все переменные хотя бы $2,$ то $ab+bc+ ca≥12.$ Пусть $a =1,$ тогда $b+c +bc= (b+ 1)(c+ 1)− 1= 9,$ откуда получаем ещё одно решение $(1,1,4).$ Осталось убедиться, что эти решения подходят. Действительно, $(1n +1n +1n)2..3 .$ и $(1n+ 1n+ 4n)2..9, .$ так как $n n n 1 + 1 + 4 ≡ 0 (mod 3).$

Ответ:

$(1,1,1)$ , $(1,1,4)$ , $(1,4,1)$ , $(4,1,1)$

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

Задача 10#74248

Докажите, что при $m > 2$ число $φ(m)$ четно.

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

Подсказка 1

Посмотрим на разложение m в произведение простых. Пусть в нем есть какое-то нечетное число. Что получается из формулы функции Эйлера?

Подсказка 2

Верно! В ней есть слагаемое, равное разности степеней этого нечетного числа, которая обязательно четна. А что, если нечетного числа в разложении нет?

Подсказка 3

Верно! Тогда наше число является степенью двойки, причем не ниже второй. Какой вывод можно сделать по формуле функции Эйлера?

Показать доказательство

Первый способ. Если в разложение $m$ входит какое-то нечётное простое число $p$ в некоторой натуральной степени $α,$ то $m > 2$ и $φ(m)$ кратно $α α−1 p − p ,$ что, в свою очередь, кратно $2$ как разность двух нечётных чисел. В противном случае либо $m =1,$ тогда $m < 2,$ либо $x m =2 ,$ откуда $x x−1 φ(m )= 2 − 2 .$ Если $x >1,$ то $φ(m)$ чётно и $m > 2.$ В ином случае $m =2.$ Что и требовалось.

Второй способ. Разобьём числа $1,2,...,m − 1$ на пары следующим образом: $(k,m− k).$ Заметим, что при чётном $m$ число $m- 2$ останется без пары. В этом случае $m- 2$ делит $m,$ то есть оно точно не учтётся в $φ(m).$ Ясно, что НОД $(k,m )=$ НОД $(m − k,m).$ Отсюда следует, что для каждой пары либо оба числа учитываются в $φ(m),$ либо нет. Значит, $φ (m )$ является суммой нескольких двоек, то есть делится на $2.$ Осталось заметить, что при $m > 2$ хотя бы одна пара вида $(k,m − k)$ найдётся.

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

Задача 11#74249

Докажите, что для любого натурального числа $n$ найдется число с суммой цифр, равной $n,$ делящееся на $n.$

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

Подсказка 1

Заметим, что, приписывая нули к числу, мы не меняем его сумму цифр. Тогда, если n = abk, где a — степень двойки, b — степень пятерки, а k — число, взаимно простое с 10, то делимость на a и b можно заработать, приписав достаточное число нулей. А как хорошим способом заработать делимость на k?

Подсказка 2

Попробуем найти много чисел с суммой цифр 1, которые будут иметь остаток 1 по модулю k. Поскольку k взаимно просто с 10, то по теореме Эйлера одно такое число легко получится. А как получить большее количество чисел?

Подсказка 3

Верно! Возводя неравенство в разные степени, мы сможем доказать, что любая степень десятки с показателем, кратным функции Эйлера от k, имеет остаток 1 при делении на k. Как теперь сконструировать число с нужной суммой цифр, делящееся на k?

Показать доказательство

Для начала заметим, что к числу с суммой цифр равной $n$ мы можем дописать сколько угодно нулей справа и при этом сумма цифр не изменится. Поэтому если $α β n = 25 k$ , где НОД( $k$ , 10) = 1, то чтобы найти нужное число делящееся на $n$ , достаточно найти число делящееся на $k$ .

Вторая идея этого решения заключается в том, чтобы найти МНОГО чисел с суммой цифр 1 и остатком 1 по mod $k$ . Если мы найдем $n$ таких чисел и сложим их, то сумма цифр сложится (мы на это надеемся), и получившееся число будет сравнимо с $n$ по модулю $k$ , а $.. n .k$ .

В качестве одного из таких чисел можно взять $φ(k) 10$ (по теореме Эйлера $φ(k) 10 ≡ 1$ (mod $k$ )) и тут время вспомнить о том, что сравнения можно возводить в степень, то есть $10a⋅φ(k) ≡ 1$ (mod $k$ ), поэтому нам подойдет любое число вида $10a⋅φ(k)$ . При сложении $n$ таких чисел в столбик из-за того, что единички у этих чисел будет в разных разрядах, получится число с суммой цифр $n$ и делящееся на $k$ . Осталось лишь дописать к этому число много (max( $α$ , $β$ )) нулей справа и получить число с суммой цифр $n$ и делящееся на $n$ .

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

Задача 12#74251

Дано натуральное $n ≥3.$ Докажите, что число

nnn nn n − n

делится на $1989.$

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

Подсказка 1

Сначала разложим на множители 1989 = 9 × 13 × 17. Тогда достаточно доказать делимость указанного числа на все числа 9, 13 и 17. Попробуем вынести за скобки общий множитель. Тогда у нас получится произведение степени числа n на разность степени числа n и единицы. Как можно доказать делимость на 9?

Подсказка 2

Верно! Если n делится на 3, то вынесенный множитель делится на 9. Если же не делится, то достаточно доказать, что показатель степени числа n из скобки делится на функцию Эйлера числа от числа 9 (она равна 6). Как это сделать?

Подсказка 3

Верно! Это выражение делится на 2, поскольку числа в разности имеют одну и ту же четность. Для делимости на 3 снова выносим общий множитель. Если n кратно 3, то все получилось, а если же не делится, то в скобке показатель степени числа n делится на 2, и по малой теореме Ферма мы получаем делимость. Можно ли аналогично доказать, что исходное выражение в задаче делится на 13 и 17?

Показать доказательство

Заметим, что $1989= 9⋅13⋅17.$ Отдельно покажем делимость на каждый множитель. Запишем выражение в виде

nn nnn−nn n (n − 1)

Докажем делимость на $9.$ Если $n$ кратно $3,$ то выражение поделится на $9.$ В противном случае надо доказать, что $9$ делит $nnnn−nn − 1.$ Для этого достаточно, чтобы $nnn − nn$ делилось по теореме Эйлера на $φ(9)=6.$ Делимость на $2$ очевидна, так как $nnn$ и $nn$ имеют одну чётность. Если $n$ кратно $3,$ то доказали. В противном случае запишем $nnn − nn$ в виде $nn(nnn− n− 1)$ и заметим, что $nn − n$ делится на $φ (3)= 2.$

Докажем делимость на $13.$ Если $n$ кратно $13,$ то доказали. В противном случае достаточно, чтобы $nnn − nn$ делилось на $φ(13)=12.$ Делимость на $3$ мы доказали в предыдущем абзаце. Докажем делимость на $4.$ Если $n$ чётно, то она очевидна. В противном случае запишем $nn n n − n$ в виде $n nn−n n (n − 1)$ и поймём, что нам достаточно делимости $n n − n$ на $φ(4)=2.$ что является правдой.

Докажем делимость на $17.$ Если $n$ кратно $17,$ то доказали. В противном случае достаточно, чтобы $nn n n − n$ делилось на $φ(17)=16.$ Если $n$ чётно, то делимость очевидна. В противном случае достаточно доказать, что $n n − n$ делится на $φ(16)= 8.$ Для этого переберём нечётные остатки при делении на $8.$ Если $n≡ 1 (mod 8),$ то всё очевидно. Если $n≡ 3 (mod 8),$ то $n n n − n ≡ 3 − 3 (mod 8).$ Если посмотреть на цикл остатков степеней троек при делении на $8,$ то можно видеть, что в $x 3 ≡ 3 (mod 8)$ при нечётных $t,$ отсюда следует делимость. Если $n ≡5 (mod 8),$ то

nn − n ≡5n− 5≡ (−3)n +3 ≡− (3n− 3)≡ 0 (mod 8)

Если $n≡ 7 (mod 8),$ то

n n n − n≡ (− 1)+ 1≡ −1+ 1≡ 0 (mod 8)

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

Задача 13#74253

Докажите, что при любом четном $n$ число $2n!− 1$ делится на $n2− 1.$

Показать доказательство

Запишем $n2 − 1$ в виде $(n − 1)(n +1).$ Заметим, что НОД чисел $n − 1$ и $n+ 1$ делит $2,$ поскольку $(n− 1,n +1)= (n − 1,2).$ Но по условию $n$ чётно, а значит числа $n − 1$ и $n+ 1$ нечётны, то есть они взаимно просты. Пусть некоторое простое число $p$ входит в одно из чисел $n− 1$ или $n +1$ в степени $k.$ Поскольку скобочки взаимно просты, степень вхождения $p$ в $2 n − 1$ также равна $k.$ Заметим, что справедливо неравенство $k φ (p )≤ n,$ потому что $k k k−1 φ(p )= p − p ≤ n− 1.$ Следовательно, $n!$ делится на $k φ(p ).$ В таком случае по теореме Эйлера $n! k 2 ≡ 1 (mod p ).$ Простой делитель $2 n − 1$ был выбран произвольно, поэтому делимость доказана.

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

Задача 14#82080

Для скольких значений числа $i,$ где $1≤ i≤1000,$ существует число $j,1≤j ≤1000,$ такое, что $2j − 1$ делится на $i?$

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

Подсказка 1

По теореме Эйлера мы можем легко указать степень двойки, которая при вычитании единицы будет делиться на i. Однако i может быть четным. В этом случае теорема Эйлера не работает. Как решить эту проблему?

Подсказка 2

Верно! Если i четно, то степень двойки при вычитании единицы нечетна, и не может делиться на i. Положим теперь j — количество чисел, меньших i, взаимно простых с i. Почему для каждого нечетного i существует подходящее j?

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

Очевидно, что для четных $i$ число $2j − 1$ точно не делится на $i$ . Поэтому число $i$ точно нечетное, НОД( $i$ , 2) = 1, а значит можно применить теорему Эйлера.

$φ(i) 2 ≡ 1$ (mod $i$ ), значит если $1 ≤φ(i)≤1000$ , то тогда $j =φ(i)$ нам подходит.

Понятно, что $φ(i)$ всегда хотя бы 1, так как для любого числа $i$ есть 1, которая не превосходит $i$ и взаимно проста с $i$ и $φ (i)$ всегда не больше $i$ , так как по определению $φ(i)$ равно количеству натуральных чисел от 1 до $i$ и взаимно простых с $i$ . Поэтому для всех нечетных $i$ существует требуемое в задаче $j$

Ответ:

$500$

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

Задача 15#102512

Для натурального числа $m$ обозначим через $φ(m)$ количество натуральных чисел, не превосходящих $m$ и взаимно простых с $m,$ а через $σ(m )$ сумму натуральных делителей числа $m.$ Найдите все чётные натуральные $n,$ для которых $5 n σ(n)− 2 делится на φ(n).$

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

Подсказка 1

Предположим, что у подходящего числа есть простой делитель, входящий хотя бы во второй степени. Тогда он делит функцию Эйлера от числа n.

Подсказка 2

Так можно получить, что только 2 может входить в степени ≥2. Нетрудно разобрать случай степени двойки. В противном случае, по модулю 4 можно получить, что 2 тоже входит в 1 степени.

Подсказка 3

Модуль 4 также даёт нам, что нечётных простых тогда не более одного. То есть нужно разобрать случай n=2p. Тогда мы знаем значения функции Эйлера и сумму делителей.

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

Предположим, что у $n$ есть простой нечётный делитель $p,$ причём $n ..pk .$ при $k≥ 2.$ Тогда

( k) 5 p|φ p |φ(n)=⇒ p|n σ(n)− 2=⇒ p |2

что невозможно. Допустим, что $n$ не является степенью двойки. Если $k 2 |n$ при $k≥ 2,$ то $k n= 2 p1...pm$ для различных простых $p1,...,pm,$ причём $m≥ 1.$ Функция Эйлера вычисляется как $k−1∏m φ(n)= 2 i=1(pi− 1).$ Обозначим через $v2(t)$ степень вхождения $2$ в число $t.$ Тогда

v2(φ(n))≥ k− 1+m ≥ 1+ 1= 2

так как все $pi$ нечётны. Это значит, что $5 4|n σ(n)− 2,$ что невозможно.

Таким образом, если $n$ — не степень двойки, то $n= 2p1...pm.$ Если $m ≥ 2,$ опять же в силу нечётности всех $pi$ имеем

v2(φ(n))≥m ≥ 2

что опять ведёт к противоречию.

Итак, если $n$ — не степень двойки, то $n= 2p$ для некоторого нечётного простого $p,$ и тогда $σ(n)= 1+ 2+ p+2p= 3p+ 3.$ Тогда условие можно переписать как

5 p− 1|32p(3p+ 3)− 2

и пользуясь $p≡ 1 (mod p− 1)$ получаем, что $p− 1 |190.$ При этом $190= 2⋅5⋅19,$ и $p− 1$ — чётное, значит могут подойти $p =3,11,191.$ Они действительно все подходят, что даёт ответы $n = 6,$ $n = 22,$ $n =382.$

Наконец, разберём случай, когда $k n= 2 ,$ $k≥ 1.$ Для такого $n$ сумма делителей $k k+1 σ(n)=1 +2+ ...+ 2 = 2 − 1.$ Подставляя в условие, получаем $k−1 5k(k+1 ) 2 |2 2 − 1 − 2.$ Если $k≥ 3,$ то

k−1 2 ≡0 (mod 4)

5k( k+1 ) 2 2 − 1 − 2 ≡2 (mod 4)

противоречие. Однако, $k= 1,2$ подходит, что также даёт ответы $n= 2$ и $n= 4.$

Ответ:

$2,4,6,22,382$

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

Задача 16#99641

Найдите сумму натуральных чисел от $1$ до $3000$ включительно, имеющих с числом $3000$ общие делители, большие $1.$

Источники: ИТМО - 2021, 11.2 (см. olymp.itmo.ru)

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

Подсказка 1

В условии задачи сказано, что надо просуммировать числа от 1 до 3000, которые не взаимнопросты с 3000. Какие нам тогда числа не подходят, если 3000 = 2³ * 3¹ * 5³?

Подсказка 2

Это значит, что нам подходят числа, которые делятся на 2, или на 3, или 5. Давайте поймём, что если нам подходит число x, то подходит и число 3000-x. При том, все числа, которые подходят под условие выше, разбиваются на пары. Или почти все? А когда тогда посчитать их сумму?

Подсказка 3

Числа 3000 и 1500 не составляют те самые пары, а вот все остальные числа, подходящие под условия все таки разбиваются на пары. Это значит, что нам теперь достаточно найти количество таких чисел и домножить их на 3000 (учтя особую роль в этой сумме исключений выше). Как найти количество таких чисел? Мы ведь не можем просто сложить количество чисел кратных 2, 3 и 5 и получить ответ. У нас есть числа которые кратны сразу двум каким-то, а также числа, кратные сразу всем. Подумайте, как тогда считать их количество?

Подсказка 4

Мы можем посчитать с помощью формулы включений и исключений количество таких чисел, а именно сначала количество просто кратных какому-то, минус сумма кратных сразу двум и плюс сумма кратных всем трём. Получится 2200. Чему тогда равна наша сумма?

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

$3000= 23 ⋅3 ⋅53$ , то есть нас интересуют числа, деляющиеся на $2,3$ или $5.$ Найдём сначала количество таких чисел. Для этого воспользуемся принципом включений и исключений. Чётных чисел от $1$ до $3000$ ровно $3000 2 = 1500$ , кратных трём — $3000 3 =1000$ , кратных пяти — $3000 5 =600$ . Однако, если просто сложить числа 1500,1000 и 600 , мы посчитаем некоторые числа 2 раза, а именно, числа, делящиеся на $2⋅3= 6,2⋅5= 10$ и $3⋅5= 15$ , поэтому из полученной суммы надо вычесть $3000 6 =$ $3000 500,10 = 300$ и $3000 15 = 200$ . Однако, $1500+1000+ 600− 500− 300− 200=2100$ всё ещё неправильный ответ, Поскольку в этом выражение числа, имеющие все три простых множителя, сначала считаются три раза, а потом их количество вычитается опять же три раза, поэтому надо снова добавить эти числа. Количество таких чисел $3000 − 2⋅3⋅5 =100$ , значит, количество чисел, имеющих с $3000$ общие делители и не превосходящих его, это $2200.$

Заметим теперь, что если какое-то число $x$ имеет с числом $N$ общие делители, то число $N − x$ тоже имеет с $N$ те же самые общие делители. Значит, все интересующие нас числа, кроме чисел $1500$ и $3000,$ разбиваются на пары с суммой $3000$ (числу 3000 в пару пришлось бы сопоставить $0,$ а числу $1500−$ само себя). Таких пар получаается $1099,$ поэтому итоговый ответ $1099⋅3000+ 3000+ 1500 =$ $1100⋅3000+ 1500 =3301500.$

Замечание.

Числа, меньшие $3000$ и взаимно простые с ним разбиваются на пары таким же образом, поэтому участники, знакомые с функцией Эйлера, могли получить формулу для ответа в виде

N(N +-1)−-N ⋅φ(N). 2

Ответ:

$3301500$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 17#83141

Докажите, что к числу $22018$ можно приписать слева несколько цифр так, чтобы снова получилась степень двойки.

Показать доказательство

Мы хотим дописать какое-то число цифр слева и получить $2k$ . Нужно каким-то образом перевести это на язык остатков и сравнений. Пусть в числе $2018 2$ $n$ цифр. Тогда для того, чтобы у $2018 2$ и у $k 2$ совпадали последние $n$ цифр, нужно, чтобы у числа $k 2018 2 − 2$ последние $n$ цифр были нулями или, что то же самое, чтобы $k 2018 2 − 2$ делилось на $n 10$ . Таким образом, наша задача превратилась в следующую задачу: Пусть у числа $2018 2$ в десятичной записи $n$ цифр. Докажите, что найдется такое $k$ , что $k 2018 2 ≡2$ (mod $n 10$ ).

$. 2k − 22018 = 22018(2k−2018− 1)..2n5n$ . Давайте для начала докажем, что выражение слева всегда делится на $2n$ .

Поймем, что первое число, в котором 2019 цифр, это $102018$ , но $22018 < 102018$ , поэтому $n ≤2018$ , что и дает нам то, что $22018$ делится на $2n$ .

Теперь осталось найти такое $k$ , что $2k− 2018− 1 ...5n$ или $2k−2018 ≡ 1$ (mod $5n$ ). Так как НОД(2, $5n$ ) = 1, то здесь можно вспомнить, что по теореме Эйлера $2φ(5n) ≡ 1$ (mod $5n$ ). Значит в качестве $k$ можно взять $2018 +φ(5n)$ и тогда $2k−2018 ≡ 2φ(5n) ≡ 1 (mod p)$

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

Задача 18#83142

Докажите, что $2..22 2..2 2 − 2$ (в первом слагаемом $n$ двоек, во втором — $n − 1$ ) делится на все числа от 1 до $n$ .

Замечание. Делится на все числа от 1 до $n$ и делится на $n!$ — это совсем не одно и то же. Например, возьмем $n =6$ : число 60 делится на все числа от 1 до 6, но не делится на $6!=720$

Замечание. Возведение в степень всегда идет сверху вниз, то есть $222 24 16 2 = 2 =2$

Показать доказательство

Будем доказывать по индукции. Давайте сначала проверим для n = 2. Очевидно, что $22− 2$ делится и на 1, и на 2, а дальше мы будем делать следующее: рассматривать выражение, где в обеих степенях на одну двойку больше и в доказательстве предполагать, что для меньшего количества двоек мы уже все доказали.

(Идея индукции заключается в том, что мы доказываем два факта: если для какого-то числа $n$ наше условие верно, то и для $n+ 1$ оно тоже будет верно (эта часть решения называется "переход") и что наше условие верно для некоторого минимального числа $n$ , в нашем случае для 2 (эта часть решения называется "база"). Зная эти два факта, мы можем сказать, что раз для $n =2$ это верно, то и для $n +1= 3$ (по 1 факту), а раз для 3, то и для 4 и т. д.)

Базу мы уже доказали, осталось доказать переход.

$..22 ..2 ..2 ..22 ..2 22 − 22 = 22 (22 −2 − 1)$ , степень 2 в скобочках (назовем ее $t$ ) — это число из предыдущего шага индукции, то есть $t$ делится на числа от 1 до $n − 1$ и нам нужно теперь доказать, что $2 22.. (2t− 1)$ делится на все числа от 1 до $n$ . Возьмем какое-то число $k$ из ряда от 1 до $n$ и представим $k$ , как $2xm$ , где $m$ нечетное. Теперь нам нужно доказать, что $22..2$ делилось на $2x$ (это очевидно, так как степень $22..2 > n≥ x$ ) и $2t− 1$ делилось на $m$ .

Вторая часть верна, так как $φ(m)< m$ , если $m ⁄= 1$ (в случае $m =1$ утверждение о том, что $2t− 1$ делится на $m$ очевидно), потому что мы в $φ (m )$ рассматриваем числа не превосходящие $m$ и взаимно простые и так как $m⁄= 1$ , то $m$ не взаимно просто с $m$ , а значит $φ(m )$ меньше $m$ хотя бы на 1. Значит $φ(m)< n$ и $t$ делиться на $φ(m )$ , поэтому $2t− 1$ делилось на $m$ .

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

Задача 19#102514

Найдите все бесконечные последовательности натуральных чисел $a, 0$ $a , 1$ $a , 2$ …такие, что $a = 1, 0$ $a >1 1$ и $a =φ(a ) n n+1$ при всех $n ≥0.$

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

Подсказка 1

Для начала хочется понять ответ. Попробуйте построить какие-нибудь длинные последовательности с условием как в задаче. Что вы можете сказать про простые числа в разложении чисел последовательности?

Подсказка 2

Докажите следующее утверждение. Если фи(n) делится на некоторое простое число большее трех, то и n делится на простое число большее 3. Этого утверждения для задачи будет маловато, вам предстоит его как-нибудь усилить. Подумайте в сторону вхождения двойки в числа последовательности. Какой вывод мы хотим получить?

Подсказка 3

Из предыдущей подсказки докажите, что ни один член последовательности не может иметь простой делитель больший 3. Тогда n делится только на 2 и 3, осталось лишь понять, какие именно последовательности нам подойдут.

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

Обозначим через $v(n)$ степень вхождения двойки в разложение числа $n.$

Лемма. Пусть $n$ — натуральное число. Если $φ(n)$ делится на некоторое простое $p≥ 5,$ то и $n$ делится на некоторое простое $q ≥ 5.$ Более того, если $φ(n)$ делится на простое $p≥ 5,$ то $v(φ(n))≥ v(n),$ при этом равенство достигается тогда и только тогда, когда $s t n =2 ⋅p$ и $p≡ 3 (mod 4).$

Доказательство. Если в разложении числа $n$ нет простых, больше или равных $5,$ то их нет и в разложении $φ(n).$ Пусть $α β1 β2 βk n =2 ⋅p1 p2 ...pk .$ Тогда

k v(φ(n))≥ α− 1+ ∑ v(pi− 1) i=1

Каждое из чисел $v(pi− 1)$ больше нуля, поэтому если таких чисел хотя бы два, или одно из них хотя бы $2,$ то $v(φ(n))> v(n).$ Иначе $s t n =2 ⋅p ,$ где $p≡ 3 (mod 4).$ Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Докажем, что ни один из членов последовательности не делится ни на одно простое число, большее или равное $5.$ Предположим противное, и пусть $aN$ делится на простое $p ≥5.$ Тогда, согласно лемме, для каждого $k≥ N$ число $ak$ делится на некоторое простое $pk ≥ 5.$ Согласно лемме, последовательность $v(ak),$ начиная с $N,$ будет не возрастать. Поскольку убывать бесконечно она не может, то, начиная с некоторого момента, она стабилизируется, и опять же из леммы, $s t ak =2 ⋅pkk$ при всех достаточно больших $k.$ Тогда

2s⋅ptkk= ak = φ(ak+1)= 2s−1⋅(pk+1 − 1)⋅ptkk++11−1

то есть

ptkk= pk+12−-1⋅ptkk++11−1

Поскольку $pk+1 > 3,$ то $pk+1− 1⁄= 1$ делится на $pk.$ Значит, $pk+1 ⁄=pk,$ а $tk+1 = 1.$ Следовательно, начиная с некоторого момента $n,$ $ak = 2s⋅pk$ и $pk+1 =2pk+ 1.$ Но тогда последовательность $pn+k$ по модулю $pn$ зацикливается, а поскольку $(2,pn) =1,$ зацикливается без предпериода. Значит, найдётся $k> 0,$ что $pn+k$ делится на $pn,$ что невозможно.

Значит, среди простых делителей членов последовательности могут быть только $2$ и $3.$ Поскольку $3n >1$ — нечётное число, оно не может являться значением функции Эйлера, поэтому в последовательности не встречается. Заметим, что

φ(2s)= 2s−1

φ(2s⋅3t)= 2s⋅3t−1

откуда, если $s an =2 ,$ то $s+1 an+1 = 2$ или $s an+1 = 2 ⋅3,$ а если $s t an =2 ⋅3$ при $t≥ 1,$ то $s t+1 an+1 = 2 ⋅3 .$ Таким образом, если ни один член последовательности не делится на $3,$ получаем первый ответ, иначе — второй.

Ответ:

$a =2n n$ для любого $n;$ $a = 2n n$ при $n ≤k,$ $a =2k⋅3n−k n$ при $n> k,$ где $k$ —– натуральное число

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

Задача 20#97388

Дано нечетное натуральное число $m.$ Докажите, что при некотором натуральном $n$ у числа $mn + nm$ не меньше $2025$ различных простых делителей.

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

Подсказка 1

Для данного m можно определить последовательность чисел, задаваемую выражением из условия для n-го члена. Тогда наша задача - найти в этой последовательности подходящее число. Попробуем зафиксировать какое-нибудь n. Как по нему построить такое k, чтобы k-ый член последовательности был больше n-го, и простых делителей у этого члена было не меньше, чем у n-го?

Подсказка 2

Точно! Возьмем n, взаимно простое с m, а после этого положим k равным сумме n и произведения m на функцию Эйлера от квадрата n-го члена. На что делится разность k-го члена и n-го члена?

Подсказка 3

Верно, на квадрат n-го члена! Что можно сказать о простых числах, входящих в n-ый и k-ый члены?

Подсказка 4

Конечно! Все простые делители n-го члена входят в k-ый член в тех же степенях. А можно ли сравнить k-ый и n-ый члены?

Подсказка 5

Правильно! k-ый член больше! Следовательно, у него больше простых делителей, чем у n-го. А как заработать число с еще большим числом делителей?

Показать доказательство

Пусть $A = mn+ nm. n$ Пусть $n$ взаимно просто с $m,$ тогда $n$ взаимно просто с $A . n$ Рассмотрим число $k =n +m φ(A2 )⋅A2 . n n$ Тогда $k$ взаимно просто с $m.$ Заметим, что $k n m − m$ кратно $2 An$ по теореме Эйлера, а $m m k − n$ кратно $2 An$ , поскольку $k − n$ делится на $2 A n$ . Следовательно, $Ak − An$ делится на $2 An$ . Значит, все простые делители числа $An$ входят в $Ak$ в тех же степенях, что и в само $An,$ при этом число $Ak$ больше; следовательно, у него есть другой простой делитель. Итого, по числу $An$ мы получили $Ak,$ у которого количество различных простых делителей больше. Теперь рассмотрим $n= 1;$ тогда $n$ взаимно просто с $m,$ и у числа $An$ есть некоторые простые делители. Производя аналогичную процедуру, за $2024$ шагa мы получим число $An,$ у которого не менее $2025$ различных простых делителей.