Ошибка.
Попробуйте повторить позже
Найдите сумму максимальных нечётных делителей всех чисел от 601 до 1200 включительно.
Подсказка 1
Зададимся вопросом, что означает тот факт, что у двух чисел из отрезка [601; 1200] одинаковый наибольший нечетный делитель. Если это так, как могут отличаться эти два числа?
Подсказка 2
Если у двух чисел одинаковый наибольший нечётный делитель, то состав нечётных простых, в них входящих, идентичен у двух чисел, и отличаться эти числа могут только степенью вхождения двойки. Может ли такое случиться для двух чисел из данного отрезка?
Подсказка 3
Такая ситуация невозможна, ведь на отрезке нет чисел, которые отличаются друг от друга хотя-бы в два раза. Какой вывод можно сделать из этого рассуждения?
Подсказка 4
Тогда мы получили, что искомые делители у всех наших чисел различны. Делитель не может быть больше самого числа, поэтому мы не получим делители, превосходящие 1200. Тогда не остаётся выбора, какие нечётные числа брать :)
Пусть — сумма максимальных нечётных делителей чисел на отрезке , причём является максимальным нечётным делителем числа для всех
Пусть — натуральное нечётное число на отрезке . Докажем, что совпадает с для некоторого . Предположим противное. Рассмотрим ряд
Поскольку , то существует натуральное число такое, что , а , что невозможно.
Таким образом, каждое нечётное число на отрезке совпадает с для некоторого . Осталось заметить, что на отрезке каждое второе число является нечётным, следовательно, количество нечётных чисел равно 600, ровно из стольких слагаемых состоит , то есть никаких других чисел там нет. Наконец, по формуле суммы членов арифметической прогрессии
Ошибка.
Попробуйте повторить позже
В тюрьме находятся 100 камер, пронумерованных числами от 1 до 100. Тюремщик Джон Фридом, осуществляя частичную амнистию, поступил следующим образом. Сначала он открыл все камеры. Затем запер каждую вторую камеру. На третьем этапе он повернул ключ в замке каждой третьей камеры (открыл запертые и запер открытые). Продолжая действовать таким образом, на сотом этапе он повернул ключ только в замке последней сотой камеры, а затем выпустил всех заключенных, которые оказались в открытых камерах. Укажите номера камер, в которых сидели счастливчики.
Подсказка 1
Подумаем, что с точки зрения теории чисел значит, что в момент k-го прохода (когда тюремщик проходится по камерам k-й раз и поворачивает замок в каждой k-й) повернулся замок в камере с номером n? Например, в третий раз он меняет состояние 3, 6,… 99 двери, что нам это напоминает?
Подсказка 2
Верно, такое действие означает, что n является кратным числа k, или же k — делитель n. Если в конце дверь отказалась открыта, значит замок поворачивали нечетное количество раз. Что мы получим, сопоставив эти две мысли?
Подсказка 3
Таким образом, отрыты в конце те двери, у номеров которых нечетное число делителей. У любого числа все (или почти все) делители можно поделить на пары. Подумаем, когда же реализуется это “почти”, которое нас и приведет к решению задачи!
Назовем проходом с номером изменение состояний каждой -той камеры. Рассмотрим камеру с номером . Найдем сколько раз она меня свое состояние с открытой на закрытую или наоборот. Пусть камера поменяла свое состояние на проходе с номером , тогда номер камеры делится на . Таким образом, камера с номером меняла свое состояние столько раз, сколько различных делителей она имеет.
Заметим, что после каждой нечетной смены состояний камеры она является открытой, а после каждой четной — закрытой. Таким образом, в конце камера будет открыта тогда и только тогда, когда количество смен ее состояний, то есть количество делителей ее номера является нечетным числом. Докажем, что число имеет нечетное количество делитей тогда и только тогда, когда является полным квадратом. Как известно, число делителей числа равно — нечетное число, но тогда число нечетно при всех , следовательно, каждое из чисел при всех делится на 2, то есть степень вхождения любого простого числа в четна, а значит является квадратом. Аналогично, если суть полный квадрат, то числа при всех делятся на 2, следовательно, — нечетно.
Наконец, открытыми будут те и только те камеры, номера которых есть полный квадарт, то есть 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.
Ошибка.
Попробуйте повторить позже
На какое самое большое натуральное число будет гарантированно делиться произведение любых шести подряд идущих натуральных чисел?
Ответ обоснуйте.
Поскольку произведение первых 6 натуральных чисел равно то искомое число не больше
Осталось доказать, что произведение любых подряд идущих 6 натуральных чисел делится на . Поделим:
и получим натуральное число способов выбрать шестёрку из элементов. Действительно, делится.
Ошибка.
Попробуйте повторить позже
Докажите, что уравнение
имеет бесконечно много решений в целых числах.
Источники:
Решим сначала уравнение
______________________________________________________________________________________________________________________________________________________
Умножим на 4 и прибавим 1 к обеим частям, чтобы выделить полный квадрат справа:
Теперь домножим обе части на 5 и выделим полный квадрат слева:
Сделаем замену . У получившегося уравнения
имеются решения
где — числа Фибоначчи (мы пользуемся нумерацией при всех целых ). На самом деле
равно для всех , что легко проверить по индукции: при это выполняется, а если , то и
(Можно доказать с помощью теории уравнений Пелля, что не имеет других решений.)
Теперь нужно найти бесконечно много и таких, для которых соответствующие и целые. Заметим, что последовательность остатков чисел Фибоначчи по модулю 10 периодична (так как пара ( ) может принимать конечное количество вариантов по модулю 10, а остаток следующего и предыдущего чисел Фибоначчи однозначно определяются по остаткам этой пары). Кроме того, и подходят, они соответствуют тривиальному решению . Значит, уравнение имеет бесконечно много решений.
_________________________________________________________________________________________________________________________________________________________________________________
Осталось понять, что они все не могут обнулять знаменатель. Действительно, если — решение уравнения , при котором , то и . Следовательно, . Так как целое, то обязательно (иначе ), а значит, и . Остальные пары нам подходят.
Ошибка.
Попробуйте повторить позже
Для любых натуральных и докажите неравенство
(Как обычно, обозначает наибольший общий делитель чисел и )
Источники:
Заметим, что
Но эта разность делится на произведение НОДов. Действительно, делится на делится на и делится на следовательно делится на произведение НОДов. Аналогично делится на произведение НОДов, а тогда и разность делится. Но тогда эта разность не меньше, а больше произведения НОДов.
Ошибка.
Попробуйте повторить позже
На доске в ряд написаны простых чисел. Известно, что среди них менее различных. Докажите, что можно выбрать несколько подряд идущих написанных чисел, произведение которых является точным квадратом.
Источники:
Рассмотрим произведения первых чисел в ряду. Всего таких произведений (также учитваем произведение, в котором простых чисел, будем считать, что оно равно ).
Ясно, что произведение чисел любой подпоследовательности этого ряда — частное каких-то двух произведений первых чисел.
Пусть ряд состоит из чисел Тогда любое произведение первых чисел имеет вид Если мы найдём два произведения первых чисел, у которых чётности соответствующих совпадают, то мы найдём подпоследовательность ряда, произведение чисел которой равно квадрату.
Всего существует наборов чётностей (каждое либо чётное, либо нет). Осталось заметить, что Значит, найдутся два произведения с одинаковым набором чётностей у получили требуемое.
Ошибка.
Попробуйте повторить позже
Найти сумму максимальных нечётных делителей всех чисел от 61 до 120 включительно.
Подсказка 1
Интересно, что чисел от 61 до 120 ровно столько же, сколько нечётных от 1 до 120.
Подсказка 2
Чем нечётные отличаются от чётных? Наличием степени двойки. Тогда как удобно представить все числа?
Подсказка 3
Из первого замечания про количество нечётных хочется посмотреть, а сколько чисел вида n * 2ᴷ для каждого нечётного n (меньшего 120) лежит в промежутке от 61 до 120.
Подсказка 4
Оказывается, для каждого такого n одно своё n * 2ᴷ в промежутке от 61 до 120. Попробуйте понять, почему это так, и досчитать искомую сумму нечётных n!
Для каждого нечетного числа в промежутке 1 до 119 рассмотрим числа вида , где Докажем, что для каждого найдётся ровно одно число вида на промежутке от 61 до 120.
Пусть на нашем промежутке не нашлось нужного числа. Тогда должна найтись такая пара чисел , что
что невозможно, поскольку из первого следует, что
Тогда из нашего утверждения следует, что для любого нечётного числа , меньшего 120, найдётся число от 61 до 120, что его наибольшим нечетным делителем будет . Причём для каждого такое число уникально. При этом нечётных чисел от 1 до 120 ровно 60, как и чисел от 61 до 120. Получается, что искомая сумма равна сумме всех нечётных чисел от 1 до 120.
Ошибка.
Попробуйте повторить позже
Про натуральные числа известно, что делится на делится на , а делится на . Найдите наименьшее возможное значение их произведения .
Подсказка 1
Обратите внимание, что если w является делителем x и y является делителем z, то xz кратно wy. Как это можно применить относительно нашего условия?
Подсказка 2
Правильно, перемножив попарно все три условия кратности и сократив лишнее, получим, что a² ⫶ 10, b² ⫶ 6 и c² ⫶ 15. Все эти числа не включают в себя полные квадраты. Что это говорит о числах a, b и c?
Подсказка 3
Правильно, сами числа тогда тоже делятся на 10, 6 и 15 соответственно, а значит, не могут быть меньше них. Тогда и abc тоже будет не меньше произведения этих чисел.
Но раз квадрат делится на 2 и на 3, то и само делится на 2 и на 3. Тогда , значит,
Но раз квадрат делится на 2 и на 5, то и само делится на 2 и на 5. Тогда , значит,
Но раз квадрат делится на 3 и на 5, то и само делится на 3 и на 5. Тогда , значит,
В итоге причём при , , достигается равенство.
Ошибка.
Попробуйте повторить позже
В вершинах куба записали восемь различных натуральных чисел, а на каждом его ребре — наибольший общий делитель двух чисел, записанных на концах этого ребра. Могла ли сумма всех чисел, записанных в вершинах, оказаться равной сумме всех чисел, записанных на ребрах?
Давайте докажем, что если числа и различны, то НОД. Пусть , тогда НОД, а 2НОД (так как делится на НОД, но равно быть не может, так как числа не равны и большее число, значит, 2НОД). Получили, что 3НОД. Давайте для каждого ребра запишем полученную оценку и сложим все неравенства, каждая вершина используется в трех неравенствах, поэтому сумма всех НОДов меньше либо равна суммы всех чисел. Предположим, что эти суммы равны, тогда равенство достигается в каждом неравенстве, выше. То есть равенство возможно только при или (для каждого ребра).
Не теряя общности пусть , но тогда: либо , тогда нашлись два равных числа, либо , но также или , то
есть в любом случае найдутся хотя бы два равных числа, противоречие, значит, равенства быть не могло. Таким образом, сумма всех НОДов
меньше суммы всех чисел.
Нет
Ошибка.
Попробуйте повторить позже
Даны натуральные числа и такие, что число является целым. Докажите, что наибольший общий делитель чисел и не превосходит числа
Имеем:
Пусть — наибольший общий делитель чисел и Так как делится на то делится на Число также делится на Поэтому делится на и
Ошибка.
Попробуйте повторить позже
Докажите, что если делится на то сумма всех делителей натурального числа тоже делится на
Так как делится на и то при делении на даёт остаток а при делении на — остаток
Разобьём делители на пары вида так как число не может быть полным квадратом ввиду противоречия с делимостью на Заметим, что если даёт остаток при делении на то даёт остаток и наоборот. Поэтому сумма делителей в каждой такой паре кратна
Аналогично, сумма делителей в каждой такой паре кратна
Ошибка.
Попробуйте повторить позже
Найдите все такие составные числа что для любого разложения на два натуральных сомножителя сумма является степенью двойки.
Подставив получим, что для некоторого натурального Пусть где и пусть для некоторого натурального числа Очевидно, что Тогда
Перемножив эти равенства, получим, что число делится на Но двойка входит в одно из чисел или в первой степени, а во второе — в степени, не большей Аналогично для чисел и Следовательно, делимость на возможна, только если в обеих упомянутых оценках двойки входит в степени ровно Это возможно, лишь если (поскольку и ). Тогда и делится на Значит, можно считать, что в наших рассуждениях выбрано Тогда и — единственное подходящее число.
Ошибка.
Попробуйте повторить позже
Дано различное натуральное число, меньшее Известно, что среди любых трех из них есть два, дающих в произведении точный квадрат. Докажите, что среди этих чисел есть точный квадрат.
Предположим, что среди этих чисел нет точного квадрата. Обозначим через все простые числа, меньшие Заметим, что по условию каждое выписанных чисел раскладывается в произведение в некоторых степенях. Каждое из наших простых чисел входит в одно выписанное число в четной или нечетной степени. Сопоставим каждому выписанному числу последовательность из и длины Число на - ой позиции будет равно если в ходит в выписанное число в нечетной степени и в противном случае (на самом деле это и есть бесквадратная часть, про которую мы говорили в теории). Предположим, что среди последовательностей выписанных чисел есть три различные. Тогда для трех соответствующих этим последовательностям чисел не выполнено условие (два числа в произведении могут давать точный квадрат, только если четности вхождения каждого - ого одинаковые).
То есть мы показали, что различных последовательностей может быть не больше Обозначим эти последовательности через и Обозначим через Очевидно что Считаем. что тогда так как при мы получим, что числа являются квадратами, а мы предположили, что их нет. Каждое из выписанных чисел дает точный квадрат либо при делении на либо при делении на Причем для чисел, которым соответствуют одинаковые последовательности, эти квадраты должны быть различными. Рассмотрим наибольшее выписанное число, которому соответствует последовательность -шек. Оно равно для некоторого натурального откуда то есть Но тогда количество выписанных чисел, которым соответствует первая последовательность, не превосходит Аналогично поступаем со второй последовательностью. Опять рассматривает наибольшее число откуда то есть откуда таких чисел не больше То есть всего чисел не больше, чем Получили противоречие с количеством данных чисел.
Ошибка.
Попробуйте повторить позже
Можно ли вычеркнуть из произведения один из факториалов так, чтобы произведение оставшихся было квадратом целого числа?
Отсюда видно, что, вычеркнув мы получим квадрат числа
Да, можно
Ошибка.
Попробуйте повторить позже
Сумма всех натуральных делителей числа более чем в 100 превосходит само число . Докажите, что есть сто идущих подряд чисел, каждое из которых имеет общий делитель с больший 1.
Источники:
Сначала докажем лемму.
_________________________________________________________________________________________________________________________________________________________________________________
Лемма.
Пусть - функция Эйлера числа (Количество чисел от до взаимно простых с ) Тогда для любого натурального числа справедливо неравенство
_________________________________________________________________________________________________________________________________________________________________________________
Доказательство леммы.
Запишем сумму делителей числа через произведение сумм степеней его простых делителей. Если то
Используя формулу суммы геометрической прогрессии, получаем:
Функция Эйлера вычисляется по формуле Тогда чтобы получить в знаменателе, домножим числитель и знаменатель на
_________________________________________________________________________________________________________________________________________________________________________________
Решение задачи.
По условию и лемме
Тогда
То есть количество чисел от до взаимно простых с меньше
Рассмотрим два случая: делится на и не делится на
1. Число делится на Тогда можно разбить числа от до на групп по идущих подряд чисел. Если количество чисел от до взаимно простых с меньше , то хотя бы в одной группе не будет числа взаимно простого с
2. Число не делится на Тогда среди чисел до можно выделить групп по идущих подряд чисел. Если в каждой группе будет число взаимно простое с , то чисел взаимно простых с хотя бы ( тоже взаимно проста с ). Это противоречит тому, что количество чисел от до взаимно простых с меньше
Ошибка.
Попробуйте повторить позже
Сумма двух различных натуральных делителей натурального числа равна 100. Какое наименьшее значение может принимать число (Среди указанных делителей могут быть единица и само число.)
Подсказка 1
Предположим, что мы взяли какие-то два делителя числа n числа и сложили их. Если каждый из этих двух делителей меньше n, то он меньше n “в сколько-то раз”. Какой вывод мы тогда сможем сделать для их суммы?
Подсказка 2
Да, в таком случае сумма этих двух делителей, равная ста, будет меньше, чем n, следовательно, n больше ста. Это не очень удовлетворительный результат, потому что первый пример, приходящий в голову — 99+1 — это пример меньше, чем на 100. Какой вывод можно отсюда сделать?
Подсказка 3
Тогда получается, что один из делителей заведомо равен самому числу. В таком случае, введя d как меньший делитель, можно записать условие в виде достаточно простого выражения!
Подсказка 4
Из нашей записи получится, что n/d+1 должно быть делителем числа 100. При этом для каждого фиксированного d чем больше n/d, тем больше n. Отсюда и получим искомый ответ!
Если один из наших делителей — само число , а второй — некоторое число и , то мы получаем
Чем больше, тем и само больше.
Наименьшее такое, что является делителем 100, это 3. При таком получаем .
Если же нет среди двух наших делителей, то , откуда .
Ошибка.
Попробуйте повторить позже
Последовательность Фибоначчи задана рекуррентно . С каким остатком число 3 в степени делится на 13?
Чтобы найти остаток при делении на достаточно знать остаток при делении на потому что
По индукции доказывается, что остатки при делении чисел Фибоначчи на повторяются с периодом
Поскольку делится на с остатком имеем
Ошибка.
Попробуйте повторить позже
Натуральное число назовем удачным, если для любого натурального такого, что делится на число делится на Найдите количество удачных чисел, меньших
Лемма. Число является удачным тогда и только тогда, когда каждое простое число входит в разложение на простые множители с одним из следующих показателей:
Доказательство. Назовем целое неотрицательное число счастливым, если не существует такого целого что Заметим, что счастливыми являются в точности числа При в этом можно убедиться прямой проверкой. Если же то выберем такое максимальное число что Тогда и по выбору то есть несчастливо.
Пусть число неудачно, то есть делится на но не делится на для некоторого Тогда некоторое простое входит в разложение в меньшей степени, чем в разложение Пусть входит в разложения и в степенях и соответственно; тогда но Значит, число — несчастливое. Итак, если все степени вхождения простых чисел в счастливы, то удачно.
Если же где не кратно и несчастливо то при число делится на а не делится на то есть неудачно.
Согласно лемме, каждое неудачное число имеет простой делитель, входящий в разложение на простые множители с показателем или более Поскольку и каждое неудачное число, меньшее принадлежит одному из следующих непересекающихся классов:
Числа вида где нечётно и
Числа вида где нечётно и
Числа вида где или
Число
Числа вида где не кратно и
Таким образом, общее количество неудачных чисел, меньших равно а количество удачных чисел равно
Ошибка.
Попробуйте повторить позже
Найдите все натуральные и для которых
Для удобства обозначим первый НОК через а второй, через Тогда равенство можно записать в виде Рассмотрим произвольное простое число Пусть оно входит в в степени а в — в степени Тогда в оно входит в степени в — в степени Значит, в оно входит в степени
Теперь оценим степень вхождения в левую часть равенства:
Степени вхождения в левой и правой части равны, поэтому
Запишем как
и приведём подобные. Получим, что
Заметим, что строгий знак в полученном неравенстве возможен лишь когда Также отметим, что последнее равенство возможно лишь когда Действительно, если то иначе равенство будет верным лишь при Аналогично рассматривается другой случай. Предположим, что . Если равенство верно для любого простого , то . Тогда уравнение примет вид: а значит
Пусть существует такое для которого тогда Уравнение симметрично, поэтому пусть тогда равенство примет вид Правую часть можно оценить сверху: то есть откуда Простое число может входить в в степени если оно равно в степени если оно равно в степени в иных случаях. Однако поэтому Значит, Получается, что если такое существует, то оно равно и входит в одно число в первой степени, а в другое — в нулевой. То есть либо где не кратно либо наоборот. Подставим в равенство и получим откуда Учитывая симметрию, запишем ответ.
Ошибка.
Попробуйте повторить позже
Натуральные числа таковы, что — целое. Докажите, что — точный куб.
Приведём дроби к одному знаменателю: Будем считать, что переменные взаимно просты, иначе можно просто сократить на НОД. Пусть некоторое простое число входит в в некоторой натуральной степени. Все переменные на делиться не могут. Пусть на делится только одна переменная, например Чтобы дробь была целой, необходимо, чтобы делилось на но этого не может быть, поскольку не делится на а — делится.
Значит, число распределено по двум переменным. Пусть оно входит в в степени а в — в степени Тогда в оно входит в степени в — в степени в — в степени
Ясно, что поскольку знаменатель, а также второе и третье слагаемые числителя делятся на а значит и делится на Значит степень вхождения в не меньше Предположим, что Заметим, что знаменатель делится на так как он делится на а Также на делятся первое и второе слагаемые числителя. Значит, на делится и однако входит в это число лишь в степени Значит, то есть входит в в степени В силу произвольности выбора получаем требуемое.