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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 2#68523

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

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

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

Для начала покажем, что $(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)$

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

Задача 3#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)$ найдётся.

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

Задача 4#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$ .

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

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

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

Задача 6#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$ был выбран произвольно, поэтому делимость доказана.

Курсы

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

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

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

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

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

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

Задача 9#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)$

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

Задача 10#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$ .

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

Задача 11#97388

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

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

Подсказка 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$ есть некоторые простые делители. Производя аналогичную процедуру, за $2013$ шагов мы получим число $An,$ у которого не менее $2014$ различных простых делителей.

Интенсивы

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

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

Задача 12#83139

Теорема Эйлера. Для любого числа $m$ и взаимно простого с $m$ числа $a$ верно, что $aφ(m) ≡ 1$ (mod $m$ )

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

Давайте возьмем две разные ПрСВ по одному модулю $m$ и перемножим в каждой все числа. Так как наборы остатков одинаковые, то получившиеся произведения будут сравнимы по модулю $m$ .

Тогда рассмотрим две такие ПрСВ: [ $x1$ , $x2$ , ..., $xφ(m )$ ] (это любая ПрСВ по модулю $m$ ) и [ $ax1$ , $ax2$ , ..., $axφ(m)$ ] (То, что написано справа - это $a⋅$ ПрСВ) и перемножим в каждой все числа. Получаем, что:
$x1⋅x2⋅....⋅xφ(m ) ≡ax1⋅ax2⋅....⋅axφ(m)$ (mod $m$ ) или
$φ(m) x1x2...xϕ(m ) ≡x1x2...xφ(m)a$ (mod $m$ ).
Теперь перепишем это сравнение через разность, то есть
$φ(m) φ(m) a x1x2...xφ(m)− x1x2...xφ(m) = (a − 1)x1x2...xφ(m)$ делится на $m$ .
Из-за того, что НОД( $xi$ , $m$ ) = 1, то отсюда следует, что $aφ(m)− 1$ делится на $m$ или $aφ(m) ≡ 1$ (mod $m$ )

Предыдущий раздел

Следующий раздел