Остатки и сравнения по модулю
Ошибка.
Попробуйте повторить позже
Пусть — нечётное, большее единицы число и
— его разложение на простые множители (среди
могут быть
равные). Тогда для произвольного целого числа
символ Якоби определяется равенством:
где — символы Лежандра. По определению считаем
для всех
Докажите, обобщённый квадратичный закон взаимности:
если
— взаимно простые нечётные числа, то
Сначала проверим случай, когда одно из чисел Пусть
Тогда
То есть действительно всё
сходится.
Теперь пусть и
Из взаимной простоты следует, что
Мультипликативность символа Якоби
следует из определения и мультипликативности символа Лежандра:
Тогда
По квадратичному закону взаимности для простых чисел получаем, что
Значениие степени зависит от чётности показателя, то есть нам нужно доказать, что
Для нечётных заметим, что
(можно явно проверить, рассмотрев остатки по модулю
при равных
остатках с обеих сторон получится
при различных остатках —
Тогда заметим, что в сумме можно вынести
за второй индекс
суммирования:
из нашего тождества. Теперь общий множитель можно тоже вынести:
снова по тождеству. То есть у нас получилось в точности то, что и требовалось доказать:
Ошибка.
Попробуйте повторить позже
Пусть — простое число, а
— натуральные числа. Оказалось, что
Докажите, что
Подсказка 1
Для начала попробуйте разобрать случай, когда у чисел x и y есть общий простой нечетный делитель.
Подсказка 2
Если у x и y есть общий простой нечётный делительно, то достаточно посмотреть на его степень вхождения в обоих частях нашего равенства. Теперь пусть у x + y есть нечетный простой делитель q. Что тогда можно сказать про степени вхождения q в нашем равенстве (давайте пока считать, что p > 2)?
Подсказка 3
Для этого достаточно выяснить, как вычислить степень вхождения q в x^p + y^p. Что же может нам помочь в этом?
Подсказка 4
Правильно, лемма об уточнении показателя! Применив ее, легко получить, что m может быть только 1. Теперь можно считать, что x + y вообще не имеет нечётных простых делителей. То есть x + y является степенью двойки. Из нашего равенства также будет следовать, что x^p + y^p тоже степень двойки. Попробуйте осознать, что это бывает довольно редко.
Подсказка 5
Не забудьте рассмотреть случай p = 2. Чтоб разобрать этот случай достаточно на самом деле понять, что при m > 2 правая часть точно больше левой.
Пока будем считать, что Пусть
— простой общий делитель чисел
и
Тогда
и
(
Теперь
посмотрим на степень вхождения
в нашем равенстве. Мы получаем, что
а значит,
Следовательно, достаточно доказать задачу для где
Предположим, что
имеет простой множитель
Тогда
и
по отдельности на
не делятся. Тогда по лемме об уточнении показателя получаем
поэтому что неверно. Пусть
а значит,
и
(
Мы разобрали случай, когда у
есть нечётный простой делитель, поэтому можно считать, что
и
Следовательно, из нашего
равенства мы получаем, что
где
— какое-то число. Тогда мы знаем, что
После
раскрытия скобок получаем, что степень вхождения двойки справа равна
а слева равна
Значит,
Так как
то
а значит,
и аналогично
то есть
Тогда из условия сразу следует, что
Если же то мы получаем
Заметим, что
в силу того, что
и
А значит,
левая часть нашего равенства при
точно больше правой. То есть
тоже равно двум.
Ошибка.
Попробуйте повторить позже
Найдите все натуральные и простые
такие, что
Подсказка 1
В случае нечетного c правая часть делится на p+3, а тогда оно является степенью двойки или произведением степени двойки и числа p. Предположим, что это степень двойки. Какие числа тогда заведомо являются вычетами или невычетами по модулю p?
Подсказка 2
Верно! -1 является вычетом, а 2 — невычетом. Тогда -2 — невычет. Возможно ли такое?
Подсказка 3
Конечно же, нет! Пусть теперь p+3 - это произведение степени двойки и p. Легко видеть, что p = 3. Можно ли найти теперь степень вхождения 3 в правую часть?
Подсказка 4
Верно! По лемме об уточнении показателя степень вхождения 3 в правую часть равна степени вхождения 3 в c, увеличенной на 1. Следовательно, с не меньше, чем (b-1)-я степень числа 3. При каких a, b, c это возможно?
Подсказка 5
Остается случай четного c. Обозначим степень вхождения 2 в c через n. Заметим, что если в правой части заменить c на n-ю степень 2, то получится делитель правой части. Тогда мы знаем разложение этой правой части с заменой c на n-ю степень 2 на простые множители. Какие выводы напрашиваются?
Подсказка 6
Верно! Мы видим, что при p > 2 можно применять LTE-лемму по модулю 2! Тогда можно получить уравнение на степени вхождения 2, а что из него следует?
Подсказка 7
Точно! Из этого уравнения легко получается, что степень вхождения 2 в показатель 2 по модулю p равна n+1. Тогда p-1 делится на (n+1)-ю степень 2. Кроме того, можно заметить, что степень вхождения p в левую часть с заменой c на n-ю степень двойки четна. Как тогда можно оценить степень вхождения 2 в b из имеющихся условий?
Подсказка 8
Конечно! Степень вхождения 2 в b, увеличенная на 2, не меньше 3 и не больше степени вхождения 2 в p+3. Отсюда получаем, что p-1 не делится на 8. Какое тогда получается уравнение из исходного?
Подсказка 9
Верно! Мы получаем n = 2 и после подстановки легко видеть, что при p > 5 решений нет (одна из частей уравнения точно больше другой). Остается разобраться со случаями p = 3 и p = 5!
Предположим, что нечетное. Тогда правая часть делится на
откуда
или
В первом случае получаем, что Тогда
является квадратичным вычетом по модулю
а
— не является, откуда
является квадратичным невычетом по модулю
но
откуда получаем противоречие.
Во втором случае получаем, что делится на
откуда
Тогда имеем уравнение
Заметим, что
откуда
По лемме об уточнении показателя получаем, что
откуда То есть
что возможно только при
и
Разберем случай четного Пусть
то есть
Заметим, что
делит
откуда
Заметим, что при
откуда
Тогда
Тогда
С другой стороны
откуда
Заметим, что а
откуда следует, что
то есть
делится на
Тогда
Посмотрим на наше равенство по модулю
Имеем
откуда
— четное. Тогда из только что полученного
равенства на степени вхождения следует, что
То есть число не может делиться на
Значит,
откуда
Тогда имеем уравнение
Заметим, что при
Если то
— нет решений.
Если то
откуда
Вернемся к исходному уравнению
Посмотрев по модулю получаем
Далее
Но по лемме об уточнении показателя
откуда что не может быть правдой. Значит,
Ошибка.
Попробуйте повторить позже
Дано простое число Для каждого натурального
рассмотрим выражение
Оказалось, что ровно
из
них делится на
Найдите все возможные значения
Пусть рассмотрим обратный вычет
(он существует, так как
и
) и выражение
но по условию такое число одно, получаем, что
Пусть тогда
проведем проверку, что для
неверно
Пусть тогда
что невозможно при любом
Ошибка.
Попробуйте повторить позже
Даны натуральные числа
и
такие, что
и
делятся на
Докажите, что тогда и
тоже
делится на
Так как это простое число, то у всех ненулевых вычетов есть обратный. Тогда
поэтому перейдём к
обратному остатку
Аналогично взаимно просто с
откуда
Тогда то, что нам нужно доказать, действительно, верно
Ошибка.
Попробуйте повторить позже
Докажите, что для любого простого существует бесконечно много натуральных
таких, что
делится на
По малой теореме Ферма: если Тогда
то есть
значит, надо найти одно такое, что
Рассмотрим пусть оно и ненатуральное, последующие будут натуральными:
Ошибка.
Попробуйте повторить позже
Пусть — простое число, большее
Докажите, что существует такая перестановка
чисел
что
Пусть Условие перепишется следующим образом:
Заметим, что
тогда
Ошибка.
Попробуйте повторить позже
Для каждого натурального определим число
равное количеству целых чисел
взаимно простых с
Найти
Источники:
Подсказка 1
Заметим, что у 1947 в разложении на простые ровно 3 простых делителя. Давайте попробуем решить задачу в общем виде для чисел с 3 простыми делителями в некоторых степенях.
Подсказка 2
В данном случае будет проще посчитать, сколько всего чисел, не взаимно простых с n, и потом вычесть.
Подсказка 3
Как насчёт того, чтобы сначала отдельно посчитать количество чисел, делящихся на первый простой делитель, затем — на второй, третий, после — на первый и второй и так дальше.
Подсказка 4
А как теперь найти количество не взаимно простых, зная результаты вычислений из предыдущей подсказки? Нужно немного манипуляций с формулой включения-исключения.
Пусть где
— различные простые числа,
— их (натуральные) кратности. Количество чисел, не
больших
делящихся на
Количество чисел, не больших делящихся на
Количество чисел, не больших делящихся на
Количество чисел, не больших делящихся на
Количество чисел, не больших делящихся на
Количество чисел, не больших делящихся на
И наконец, количество чисел, делящихся на
Общее количество чисел, не взаимно простых с по формуле включений-исключений равно
Тогда
Таким образом, при имеем
1160
Ошибка.
Попробуйте повторить позже
Пусть — все квадратичные вычеты по модулю
Для
…,
найдите
Квадратичными вычетами по модулю являются те и только те числа, которые удовлетворяют сравнению
Давайте рассмотрим многочлен
Его корни
Если вспомнить теорему Виета, становится ясно, что
— модуль коэффициента при
у рассмотренного многочлена, умноженный на
Все
коэффициенты, кроме свободного члена, равны
значит, соответствующие сигмы сравнимы с
а
при
и
Ошибка.
Попробуйте повторить позже
Найдите все пары числел где
простое, а
целое и при этом
В ответе укажите значения
Если их
несколько, перечислите их в любом порядке через запятую.
Источники:
Подсказка 1
Хотим использовать малую теорему Ферма (МТФ). Посмотрим на левую часть: по какому модулю удобно рассматривать остаток?
Подсказка 2
Рассматриваем остаток по модулю 5 (тогда возникает требование, что p не равно 5), так как по МТФ p⁴ дает остаток 1 по модулю 5. Вся левая часть, получается, дает остаток 2 по модулю 5. Теперь посмотрим на правую часть. Сразу видно, что второе слагаемое дает остаток 0 по модулю 5 (так как имеет вид 5*q). Что тогда можно сказать о n²?
Подсказка 3
Получается, n² должно давать остаток 2 по модулю 5. Рассмотрим различные случаи остатков. Какой вывод можем сделать?
Подсказка 4
Да, n² не может давать остаток 2 по модулю 5. Тогда у нас остается единственное возможное значение p: p = 5. Тогда наше уравнение превращается в квадратное, которое легко решается!
Согласно малой теореме Ферма, если число
даёт остаток 1 при делении на 5. Число 211 также даёт остаток 1 при
делении на 5. И
делится на
Значит, если
мы получаем, что
даёт остаток 2 при делении на 5, что
невозможно.
Осталось разобрать случай В этом случае нам надо решить квадратное уравнение
Откуда получаем два решения: и
Ошибка.
Попробуйте повторить позже
Три простые числа и
больше трех и удовлетворяют условию
Для какого наибольшего
число
всегда будет
делиться на
Источники:
Подсказка 1
Чтобы угадать ответ, попробуйте записать число p + q + r, используя равенство из условия.
Подсказка 2
Скорее всего, вы поняли, что работать надо с делимостью на 3. Быть может, повезёт и даже с девяткой получится.
Подсказка 3
Рассмотрите варианты остатков p и q при делении на 3. Чтобы доказать, что больше 9 нельзя, подберите два примера, чтобы НОД значений p + q + r был 9.
Покажем, что всегда делится на
Действительно, по условию
поэтому
Заметим, что
поэтому если и
дают остатки
и
от деления на три, то
делится на три и больше трех, поэтому
не может быть
простым числом. Значит,
и
дают одинаковые остатки от деления на три. Тогда
делится на три, а, значит,
делится
на
Подберем две различных тройки простых: если и
то
— простое число и
Если
и
то
— простое число и
Поэтому для чисел из условия задачи
гарантированно может
делиться только на
Ошибка.
Попробуйте повторить позже
Найдите все такие пары целых чисел и
, что
Подсказка 1:
Давай заметим, что в правой части равенства почти полный квадрат. Не хватает 1. Давайте добавим её слева и справа.
Подсказка 2:
Также хотелось бы разложить на скобочки левую часть, притом желательно на взаимно простые. Если не получается угадать разложение, рассмотрите выражение слева как квадратный трёхчлен относительно (n-2)!.
Подсказка 3:
Итак, вы получили равенство ((n - 1)! - 1)((n - 2)! - 1) = (m - 1)². Являются ли скобки в левой части взаимно простыми?
Подсказка 4:
Для дальнейших продвижения необходимо вспомнить, что если произведение взаимно простых чисел равно квадрату, то каждое из них является квадратом. Кстати, почему это так?
Подсказка 5:
Теперь осталось показать, что при больших n какая-то из скобок не сможет быть большим квадратом. Учитывая особенности факториалов, стоит подумать про остатки. Например, при делении на 4 квадраты могут иметь далеко не все остатки.
Заметим, что
Пусть Заметим, что числа
и
взаимно просты. Предположим, что это не так, и оба этих числа делятся
на простое число
Тогда число
тоже делится на Тогда
делится на
а
не кратно
противоречие. Таким образом, произведение взаимно
простых чисел
и
—– точный квадрат, тогда и каждое из них точный квадрат. Однако, число
при
даёт остаток 3 при делении на 4, поэтому оно точным квадратом быть не может. Остаётся разобрать случаи
При
получается
решений нет. При
мы получаем:
что даёт единственное решение
,
Ошибка.
Попробуйте повторить позже
Найти все натуральные числа такие, что для любого целого числа
существуют
целых чисел
таких, что
и
Среди чисел
могут быть совпадающие.
Источники:
Подсказка 1
Давайте попробуем пойти снизу-вверх. Что, если n = 3?
Подсказка 2
Попробуйте обозначить x₁, x₂ и x₃. Какими должны быть это обозначения, чтобы x₁ + x₂ + x₃ = 0?
Подсказка 3
Например, x₃ = - x₁ - x₂.
Подсказка 4
Попробуйте посмотреть на остатки от деления.
Подсказка 5
Быть может, с n = 4 нам подойдут аналогичные иксы?
Подсказка 6
Попробуйте увидеть полный квадрат.
Подсказка 7
Кажется, что с n = 5 противоречий не находится. Может, стоит попробовать придумать пример в общем виде?
Подсказка 8
Нам бы хотелось, чтобы сумма попарных произведений по циклу равнялась -m... То есть, вероятно, m должно быть среди иксов.
Подсказка 9
А давайте вспомним пример для n = 3.
Подсказка 10
Чтобы он работал и для n = 4, можно, например, докинуть 0.
Подсказка 11
А можем ли мы при помощи 0 доказать, что и для n ≥ 5 условия выполняются?
Пусть
Положим тогда
Из последнего равенства следует, что остаток от деления числа на 3 совпадает с остатком от деления
на 3, а он может быть
равен только 0 и 1. Следовательно, числа
для всех
дающих при делении на 3 остаток 2, не могут быть представлены требуемым в
условии образом, поэтому
не подходит.
Пусть
Положим Тогда
Следовательно, в требуемом в условии виде представляются только те числа для которых
является точным квадратом,
поэтому случай
тоже нам не подходит.
Пусть
Для произвольного рассмотрим
целых чисел:
Их сумма равна 0, а сумма попарных проиведений по циклу равна следовательно, любое
удовлетворяет условию
задачи.
Ошибка.
Попробуйте повторить позже
Коля выписал каждый натуральный делитель числа по одному разу, после чего покрасил некоторые из них в красный цвет, а
остальные — в синий. При этом он действовал так, чтобы разность между суммой всех красных делителей и суммой всех синих делителей
оказалась минимально возможным (при данном
) положительным числом. Какими могут оказаться две последние цифры этой разности?
(Найдите все варианты и докажите, что других нет.)
Источники:
Подсказка 1
Разложите 2025 на простые множители. Как выглядит сумма всех его делителей? Почему максимальный делитель 2025ⁿ больше суммы остальных? Сумма делителей растёт медленнее, чем само число, из-за степеней в разложении.
Подсказка 2
Чтобы разность сумм красных и синих делителей была минимальной положительной, как нужно раскрасить делители? Что произойдёт, если покрасить только 2025 в красный, а остальные — в синий? Разность будет 2 × 2025ⁿ.
Подсказка 3
Докажите, что искомая разность = 70n + 81 (mod 100). Какие остатки при делении на 100 могут быть у 70n + 81 при разных n? Переберите n от 1 до 20. Остатки будут циклически повторяться!
Если разность равна
Пусть
Сумма всех делителей числа 2025 равна
По формуле суммы геометрической прогрессии, сумма делителей меньше, чем
Значит, максимальный делитель (само число превосходит сумму остальных, поэтому для получения минимального
положительного результата перед ним должен стоять плюс, а перед остальными делителями — минус. Получается, что ответ имеет вид
Заметим, что разность больше
то есть по крайней мере
двузначная.
1, 09, 19, 29, 39, 49, 59, 69, 79, 89, 99
Ошибка.
Попробуйте повторить позже
Докажите, что для каждого натурального существует простое
такое, что число
— составное.
Заметим, что для подойдет
действительно:
Далее
Выберем в качестве простой делитель числа
Тогда:
Значит, наше число кратно осталось лишь показать, что это число больше
Это действительно так, поскольку
уже больше
Ошибка.
Попробуйте повторить позже
Покажите, что при всех натуральных число
делится на
.
Рассмотрим модуль Заметим, что:
Значит, применима теорема Эйлера
С другой стороны так как при
имеем
Тогда получаем, что
делит
что и
требовалось.
Ошибка.
Попробуйте повторить позже
Найдите все натуральные для которых числа
и
имеют один и тот же набор простых делителей.
Подсказка 1.
Рассмотрите простой делитель p у числа n. Как можно использовать, что 2ⁿ−1 делится на p?
Подсказка 2.
Правильно! Ввести показатель и получить условия на него.
Подсказка 3.
Получаем, что n и p−1 делятся на этот показатель, а дальше непонятно, что делать... Было бы отлично, если бы n и p−1 были взаимно просты.
Подсказка 4.
Воспользуйтесь принципом крайнего на стадии выбора p.
Очевидно, что подходит. Пусть теперь
рассмотрим минимальный простой делитель
числа
Пусть
Тогда
делится на
то есть
делится на
По условию
делится на
значит,
делится на
Заметим, что
так как
— минимальный простой делитель
Отсюда получаем, что
значит,
делится на
Получаем
противоречие, значит, таких
не существует.
Ошибка.
Попробуйте повторить позже
Докажите, что для простого уравнение
не имеет решений в натуральных числах при
,
,
Подсказка 1
Иногда полезно рассмотреть крайние случаи. Может ли равенство достигаться, если одно из чисел равно p?
Подсказка 2
Если ни одно из чисел не равно p, то они точно меньше. Может тогда посмотреть на делимость, ведь у нас есть малая теорема Ферма.
Подсказка 3
Из малой теоремы Ферма легко получается, что a + b ≡ c (mod p). Но все числа меньше p, какие есть варианты?
Подсказка 4
Полезно бы сравнить aᵖ + bᵖ и cᵖ при полученных условиях, кажется одна из частей будет намного больше другой.
Предположим противное: пусть существуют натуральные числа удовлетворяющие уравнению
Рассмотрим случаи, когда одно из чисел
равно
Пусть Тогда
Так как
то
Следовательно,
что невозможно. Аналогично для
Пусть Тогда
так как
Теперь и
– простое, значит,
не делятся на
По малой теореме Ферма:
Подставляя в исходное уравнение, получаем:
Так как то
Возможны два случая:
а) Пусть
Тогда По биному Ньютона:
так как все дополнительные слагаемые положительны при и
б) Пусть
Обозначим тогда
Уравнение принимает вид:
При фиксированном минимум
достигается при
и тогда
Рассмотрим убывающую при функцию
Так как функция убывает, то
что завершает доказательство.
Ошибка.
Попробуйте повторить позже
Как изменятся частное и остаток, если делимое и делитель увеличить в раз?
Пусть число даёт остаток
при делении на
то есть
Увеличим делимое в пять раз, тогда получим
Так
как по условию делитель стал равен
видим, что частное осталось неизменным, а остаток увеличился в пять раз. Важно отметить, что
так как
то есть
действительно является остатком при делении на
В силу однозначности определения
остатка полученный нами результат — единственно возможный.
Остаток увеличиться в пять раз
Ошибка.
Попробуйте повторить позже
Число даёт остаток
при делении на
Какой остаток оно может давать при делении на
По условию пусть частное при делении
на 15 равно
а остаток равен
то есть
Приравняем правые части
имеющихся равенств:
Заметим, что кратно пяти, а, значит,
тоже нацело делится на 5. Учитывая, что
— остаток при делении на 15, то есть
получаем три возможных варианта:
В самом деле, число имеет остаток 3 при делении на 5 и 15, число
имеет остаток 3 при делении на 5 и
остаток 8 при делении на 15, и наконец, число
имеет остаток 3 при делении на 5 и остаток 13 при делении на
15.
3; 8; 13