Теория чисел на ММО
Ошибка.
Попробуйте повторить позже
Докажите, что если при число целое, то оно точный квадрат.
Подсказка 1
Внимательно посмотрим на выражение. Если наше выражение целое при любых натуральных n, то оно четное. Обозначим его за 2k.
Подсказка 2
Что можно сказать про k после возведения в квадрат полученного уравнения на n и k?
Подсказка 3
Что k — чётное, то есть k = 2m. Получили, что произведение взаимно простых равно квадрату числа. А часто ли такое происходит?
Подсказка 4
Нужно разобрать 2 случая, один из которых не подойдет из-за остатков по модулю 3
Если число целое при , то оно чётное. Обозначим . Тогда . Возводя это равенство в квадрат, получаем
Число чётное: , где .
Тогда
Поскольку числа и взаимно просты, следует рассмотреть два случая:
1) , где ;
2) , где .
В первом случае имеем , то есть даёт остаток 2 при делении на 3 . Это невозможно, так как точный квадрат может давать при делении на 3 только остатки 0 или 1.
Во втором случае получаем - точный квадрат.
Ошибка.
Попробуйте повторить позже
Некоторые неотрицательные числа удовлетворяют равенству Докажите, что
Источники:
Подсказка 1
Числа неотрицательны, присутствует и произведение, и сумма... Как их можно связать?
Подсказка 2
Неравенством о средних!
Подсказка 3
Также можно попробовать рассмотреть равенство из условия как квадратный трëхчлен относительно чего-нибудь.
Первое решение. По неравенству о средних:
Второе решение. Числа и неотрицательны, поэтому исходное равенство можно рассматривать как квадратное уравнение относительно
По условию это уравнение имеет хотя бы одно решение, а значит,
Ошибка.
Попробуйте повторить позже
Таня последовательно выписывала числа вида для натуральных чисел и заметила, что полученное при число делится на А при каком наименьшем она получит число, делящееся на
Источники:
Подсказка 1
Никому ещё не вредило разложение чисел на простые множители в задачках на теорию чисел. Давайте разложим 2022 и поймём, какие условия накладывает каждый из множителей.
Подсказка 2
Мы понимаем, что нам достаточно просто перебрать все остатки по каждому из модулю, чтобы найти все условия на n, но как бы ускорить этот перебор?
Подсказка 3
Попробуйте подумать, какое максимальное кол-во решений может иметь сравнение n^7 = 1 (mod 337) на отрезке [0;336], а ещё подумать, что происходит с решением сравнения, если его возвести в произвольную положительную степень?
Подсказка 4
Мы понимаем, что решений не больше 7 и что возведение решения в положительную степень не портит сравнение, остаётся перебрать маленькие n, пока мы не сможем применить эти 2 факта, проверить, что хотя бы одно из них удовлетворяет остальным условиям, полученным из сравнений по mod 2 и mod 3, и выбрать из них наименьшее.
Пусть натуральное число таково, что делится на Тогда делится на и на поэтому — нечётное число, имеющее остаток при делении на Помимо того, делится на Заметим, что если два числа сравнимы по модулю (т.е. дают одинаковые остатки при делении на ), то седьмые степени этих чисел также сравнимы по модулю Это означает, что для нахождения искомого числа достаточно рассмотреть все целые числа из промежутка удовлетворяющие сравнению
Мы будем пользоваться следующим утверждением. Пусть — простое число, — многочлен степени с целыми коэффициентами, старший коэффициент которого не делится на тогда сравнение имеет не более решений среди целых чисел
Найдём теперь все решения сравнения на отрезке Нам известны два решения: , Заметим, что если — решение сравнения то для любого натурального числа также являются решениями. Следовательно, решениями данного сравнения являются числа
Итак, мы нашли семь решений на отрезке Так как число простое, по сформулированному выше утверждению других решений на этом отрезке нет. Из них нечётными и имеющими остаток при делении на являются и Из них наименьшее, большее есть
Ошибка.
Попробуйте повторить позже
На доске записано натуральное число. Если у него стереть последнюю цифру (в разряде единиц), то останется ненулевое число, которое будет делиться на а если первую — то на Какое наименьшее число может быть записано на доске, если его вторая цифра не равна
Источники:
Подсказка 1
Раз у нас число без последней цифры делится на 20, то и предпоследняя цифра равна 0. Тогда что можно сказать про кол-во цифр в числе, если учитывать второе условие на наше число?
Подсказка 2
Верно! Наше число хотя бы четырёхзначное. Теперь попробуем посмотреть на число, оставшееся после стирания последней цифры. Оно хотя бы трёхзначное. Попробуем перебирать трёхзначные числа, делящиеся на 20, и посмотреть в каждом случае, выполняется ли условие с делимостью на 21.
Подсказка 3
Отлично! Мы получили, что 100, 120, 140 не подходят. В случае же с 160 найти противоречие не получается. Тогда попробуем построить пример.
Предпоследняя цифра числа равна так как число без последней цифры делится на Значит, число хотя бы четырехзначное. Заметим, что число, оставшееся после стирания последней цифры, не может равняться по условию. Также это число не может равняться и так как числа вида и не делятся на Для существует единственный пример:
Ошибка.
Попробуйте повторить позже
Найдите наименьшее натуральное число которое не делится на но если вместо любой его цифры поставить семёрку, то получится число, которое делится на
Источники:
Подсказка 1
Подумаем, какие цифры не могут входить в искомое число. А если ещё использовать и то условие, что наше число минимальное из возможных?
Подсказка 2
Теперь, когда понятно, какие цифры могут входить в искомое число, можно рассмотреть две соседние цифры. Если заменить k-ую или (k+1)-ую цифру на 7, то получатся кратные семи числа, но тогда и их разность будет кратна 7. Значит можно найти эту разность и попробовать связать между собой соседние цифры (по модулю 7).
Подсказка 3
Должно получиться, что 10*a_k и а_(k+1) сравнимы по модулю 7, где a_k и а_(k+1) — k-ая и (k+1)-ая цифры числа. Заметим также, что если отбросить последнюю цифру от искомого числа, получится число, кратное 7. Теперь, используя это, можно преобразовать искомое число без последней цифры (преобразования по модулю 7) и с помощью этого получить оценку на количество цифр в нашем числе.
Подсказка 4
После оценки нужен пример на число с именно таким количеством цифр! Но мы уже знаем, какая цифра за какой должна следовать, поэтому в составлении подходящего числа нет никакой свободы выбора.
Пусть наименьшее подходящее число имеет вид Из условия следует, что среди его цифр нет и Если в числе есть цифры или то их можно заменить на или соответственно и получить меньшее число с тем же свойством. Таким образом, искомое число состоит из цифр от до
Рассмотрим соседние цифры и По условию числа с замененными семеркой цифрами и делятся на следовательно, их разность также кратна то есть для любого Значит, запись числа может быть устроена только следующим образом: за следует за следует (поскольку цифры в числе нет) и так далее.
По условию исходное число, у которого вместо последней цифры стоит делится на Следовательно, исходное число без последней цифры делится на Используя несколько раз сравнение получаем:
Поскольку не делится на заключаем, что делится на поэтому наименьшее возможное равно Таким образом, наименьшее возможное число состоит не менее чем из восьми знаков. Остается заметить, что число удовлетворяет условию задачи, а поскольку оно начинается с то это число и будет наименьшим.
Ошибка.
Попробуйте повторить позже
Верхней целой частью числа называют наименьшее целое число, большее или равное . Существует ли такое число , что для любого натурального расстояние от верхней целой части до ближайшего квадрата натурального числа всегда равно 2 ?
Подсказка 1
Есть два возможных ответа — да или нет. Если нет, то нужно доказывать, что абсолютно для любого числа в последовательность {A^i} найдется не подходящее число, что кажется очень непростой задачей. Тогда будем доказывать, что ответ «да». Если мы хотим, чтобы верхняя целая часть Aⁿ отличалось от ближайшего натурального квадрата на 2, то хотелось бы понять, чему равна эта верхняя целая часть. Вернее, что нам было бы удобнее взять за верхнюю целую часть, чтобы она отличалась от какого-то квадрата на 2? А если вспомнить как возводится число вида t+1/t в квадрат?
Подсказка 2
Хотелось бы сделать так, чтобы число вида Aⁿ + 1/Aⁿ было бы целым и A было некоторым квадратом, чтобы как раз получить t^2n + 1/(t^2n) = (tⁿ + 1/tⁿ)²-2. Осталось только понять, чему должно быть равно t, чтобы каждое выражение вида Aⁿ + 1/Aⁿ при A = t², было бы целым. Здесь вас на поиск подходящего t может натолкнуть либо мысль о процессе построения бесконечных цепных дробей, либо же тот факт, что число вида (a+b√c)^k, где a, b, k - целые, это выражение вида t+l√c. Заметьте, это верно и для отрицательных k.
Подсказка 3
Да, можно просто сказать, что t — корень некоторого уравнения с целыми коэффициентами и отрицательным коэффициентом при x, ведь тогда t+1/t = c, где с — целая положительная константа. Тогда, по модулю факта про возведение таких иррациональностей в степень можно сказать, что задача решена, поскольку мы нашли такое t, что любое выражение вида t^k + 1/t^k — целое, а значит, мы нашли подходящее А.
Пусть — больший корень многочлена , тогда .
Докажем по индукции, что число целое при любом целом неотрицательном .
Действительно, это верно при . Кроме того,
что позволяет проделать шаг индукции.
Положим , тогда
Значит, и есть верхняя целая часть , а ближайший к ней квадрат целого числа равен .
Ошибка.
Попробуйте повторить позже
Пусть и — пятизначные числа, в десятичной записи которых использованы все десять цифр ровно по одному разу. Найдите наибольшее возможное значение если ( обозначает угол в градусов).
Источники:
Данное равенство при условии, что и определены, эквивалентно равенству откуда где Следовательно, разность делится нацело на а значит, на и на Поскольку сумма всех цифр делится на то каждое из чисел и делится на
Наибольшее пятизначное число, все цифры которого различны, равно Ближайшее к нему меньшее число, делящееся на равно и содержит повторяющиеся цифры. Последовательно уменьшая это число на получаем числа Первые два из них также содержат повторяющиеся цифры. Третье состоит из различных цифр, но поскольку то его тангенс не определён. Число также состоит из различных цифр. Если взять, например, то получим поэтому число искомое.
Ошибка.
Попробуйте повторить позже
Можно ли представить число в виде суммы кубов двух натуральных чисел?
Подсказка 1
Существует ряд модулей, по которым кубы натуральных чисел дают "приятные остатки". К их числу относиться, например, модуль 8 - куб натурального числа может давать только остатки 0,1,3, -3, -1 по данному модулю. А по какому модулю можно рассмотреть данное уравнение?
Подсказка 2
Ясно, что при этом нам придется рассматривать число 11^2018 по данному модулю, поэтому будет проще, если 11^2018 будет давать какой-то понятный остаток по рассматриваемому модулю (точнее остаток, который мы сможем найти, что не всегда бывает просто).
Подсказка 3
Давайте рассмотрим уравнение по модулю 9. Какие остатки могут давать кубы натуральных чисел по этому модулю?
Подсказка 4
Только остатки 0, 1 или -1. С чем в свою очередь сравнимо число 11^2018 по модулю 9?
Подсказка 5
Ясно, что 11^2018 сравнимо с 2^2018 по данному модулю. Осталось заметить, что 2^6=64 сравнимо с 1 по модулю 9. Вообще говоря, для каждого числа a существует число b такое, что a^b сравнимо с 1 по данному модулю. В некоторых задачах данное число b можно найти перебором, тем более в тех задачах, где в качестве основания рассматриваются 2, потому что ее первые степени считаются довольно быстро. Закончите решение, воспользовавшись этим сравнением.
С одной стороны, поскольку и имеем
То есть число даёт остаток при делении на С другой стороны, кубы натуральных чисел дают только остатки и при делении на Значит, сумма кубов двух натуральных чисел может дать лишь остатки или при делении на но не может дать
Нет
Ошибка.
Попробуйте повторить позже
Известно, что в десятичной записи числа все цифры различны. Есть ли среди них цифра
Подсказка 1
Разумно начать решать от обратного, предположить, что 0 там нет. Но как тогда искать противоречие? Вообще число очень большое и единственная информация, которую можно относительно просто узнать, это остатки при делении на некоторые числа.
Подсказка 2
Попробуйте определить количество цифр у числа, тогда сразу поймëте, какой остаток надо искать.
Заметим, что
Следовательно, С другой стороны,
Поэтому в записи числа ровно девять цифр. Если среди них нет нуля, то сумма цифр в десятичной записи этого числа равна Отсюда следует, что делится на что не так. Противоречие.
да
Ошибка.
Попробуйте повторить позже
Найдите наибольшее натуральное число, все цифры в десятичной записи которого различны и которое уменьшается в пять раз, если зачеркнуть первую цифру.
Источники:
Подсказка 1
Попробуйте представить число так, чтобы оно имело вид суммы двух слагаемых, одно из которых-число после зачеркивания.
Подсказка 2
Да, мы представили n=a*10^(k-1)+m, где a-первая цифра, k-кол-во цифр. Но ведь тогда a*10^(k-1)=4m. Попробуйте оценить k, зная, что в числе нет одинаковых цифр.
Подсказка 3
Ура! Мы получили, что k<=4(так как иначе на конце будет две одинаковые цифры-нули). Остается перебрать варианты и выбрать максимальное число.
По условию (где число, составленное из всех цифр, кроме первой, — первая цифра). Пусть – количество цифр в числе Отсюда
Если то у числа а значит, и у искомого числа, есть две совпадающие цифры (два нуля на конце). Если же то
Ясно, что чем больше тем больше исходное число. При число состоит из цифр, а не из трех. При мы получаем а исходное число равно Значит, наибольшее искомое число равно
Ошибка.
Попробуйте повторить позже
Найдите все такие пары натуральных чисел и что для всякого натурального взаимно простого c число делится на
Подсказка 1
Понятно, что a=1 подходит. Пусть теперь a больше 1, попробуйте тогда подобрать какой-то пример для n, который сделает выполнение условия невозможным.
Подсказка 2
Показатель степени у а слишком сложный. Попробуйте подобрать такое n, чтобы внутри этой степени возник остаток 1.
Если то а значит, делится на
Пусть Возьмём тогда и следовательно,
Если то в силу неравенства получаем неравенство что противоречит
Если то должно делиться на все что невозможно.
Таким образом, пары, в которых нам не подходят.
- любое натуральное число.
Ошибка.
Попробуйте повторить позже
Найдите наименьшее натуральное число, десятичная запись квадрата которого оканчивается на 2016.
Пусть это число . Тогда . Отсюда и . Тогда так как разница множителей равна 8, то ровно одно из них делится на 5 и поэтому оно делится сразу на и оба множителя кратны 4 (так как если один не кратен, то и второй не кратен и тогда их произведение не может быть равно ). Отсюда один из множителей делится на 500 = . Значит, . Давайте проверим эти числа
Итак, минимальное число равно 996.
Ошибка.
Попробуйте повторить позже
Найдите наименьшее натуральное число, кратное 99, в десятичной записи которого участвуют только чётные цифры.
Обозначим через и сумму цифр, стоящих на чётных и нечётных местах соответственно. Из признаков делимости на 9 и на 11 следует, что кратно 9, а кратно 11. Но все цифры чётные, поэтому делится на 18, а — на 22. Также заметим, что . Если , то . Но из этого следует, что , чего не может быть в силу чётности и . Если , то в нашем числе будет не менее 7 цифр, поскольку 8·6 = 48 < 54. Пусть . Тогда или . В первом случае одно из чисел и равно 29, а другое – 7, чего не может быть. Во втором случае . Заметим, что 18 нельзя представить в виде суммы менее чем трёх чётных цифр, поэтому наше число хотя бы шестизначное. Осталось заметить, что наименьшее шестизначное число, удовлетворяющее условиям задачи, — это 228888. Действительно, первая цифра не может быть меньше 2, вторая — тоже, поскольку если она равна 0, то общая сумма цифр не больше .
Ошибка.
Попробуйте повторить позже
Будем называть натуральное число почти квадратом, если это либо точный квадрат, либо точный квадрат, умноженный на простое число. Могут ли почти квадратов идти подряд?
Подсказка 1
Вам дано 8 последовательных чисел. Подумайте, почему именно 8, а не меньше.
Подсказка 2
Это сделано для того, чтобы они имели разные остатки при делении на 8. Рассмотрите числа 8k, 8k + 1, ..., 8k + 7 в контексте условия задачи.
Подсказка 3
Давайте посмотрим на число 8k + 2. Что вы видите? Конечно, оно делится на 2, но не делится на 4. А что это значит? А про другие числа что можно сказать?
Cреди восьми последовательных натуральных чисел найдутся числа, дающие остатки и при делении на Они делятся на но не делятся на так что они обязаны иметь вид и Тогда то есть что невозможно. Противоречие.
нет
Ошибка.
Попробуйте повторить позже
Докажите, что для любого натурального найдётся натуральное число, десятичная запись квадрата которого начинается единицами, а заканчивается какой-то комбинацией из единиц и двоек.
Подсказка 1!
Воспользуйтесь индукцией! Попробуем построить такие числа по индукции. База простая, верно?
Подсказка 2!
Да! M1 = 1. Попробуем теперь по Mn построить число M(n+1). Для этого нужно рассмотреть все возможные такие числа.
Подсказка 3!
Давайте попробуем сделать так: Mn + k*10^n, чтобы условие выполнилось про единицы, рассмотрим все числа для k от 0 до 9. Осталось разобраться со вторым!
Положим и построим по индукции такие числа , что десятичная запись оканчивается на единицу, а десятичная запись числа оканчивается на комбинацию из n единиц и двоек.
Пусть число уже построено, то есть выполнено предположение для . Рассмотрим числа вида , где . Десятичная запись каждого из них оканчивается на 1. Кроме того,
Посмотрим на последние цифр десятичной записи каждого из слагаемых этой суммы.
Запись числа оканчивается на комбинацию из единиц и двоек по предположению индукции. Обозначим через -ю с конца цифру этого числа. Нетрудно видеть, что десятичная запись оканчивается на нулей, перед которыми идет последняя цифра числа (так как оканчивается на единицу). Десятичная же запись слагаемого оканчивается на нулей.
Имеем, что последние цифр десятичной записи чисел совпадают с последними цифрами десятичной записи числа . При этом -я с конца цифра числа совпадает с последней цифрой суммы . Если нечётно, то для некоторого сумма оканчивается на единицу (помним, что . Если чётно, то для некоторого k сумма оканчивается на двойку. Следовательно, одно из чисел можно взять в качестве числа .
Итак, мы получили числа, которые заканчиваются на какую-то комбинацию из единиц и двоек. Более того, мы даже знаем, что последняя цифра всегда будет единицей.
Пусть и . Тогда в силу получаем
Следовательно, найдётся такое натуральное число , которое не меньше , но меньше . Тогда десятичная запись квадрата этого числа начинается на единиц.
Рассмотрим число , где больше количества цифр в десятичных записях чисел и . Тогда первые цифр десятичной записи числа
совпадают с первыми цифрами десятичной записи числа , а последние цифр — с последними цифрами десятичной записи числа . Следовательно, число удовлетворяет условию задачи.
что и требовалось доказать
Ошибка.
Попробуйте повторить позже
Натуральные числа от до как-то разбили на пары, числа в каждой из пар сложили, а полученные сумм перемножили. Мог ли результат оказаться квадратом натурального числа?
Подсказка 1
Чтобы понять, стоит ли придумывать пример, или доказывать, что не мог, попробуйте придумать примеры для меньшего количества чисел.
Подсказка 2
Например, можно большинство чисел разбить на чётное количество пар равной суммой.
Разбив числа от до на пары
получим чётное число пар с суммой Числа от до можно разбить так: Для них в результате получим произведение Значит, в итоге получится полный квадрат.
да
Ошибка.
Попробуйте повторить позже
Ваня записал несколько простых чисел, использовав ровно по одному разу все цифры от до Сумма этих простых чисел оказалась равной Можно ли, использовав ровно по одному разу те же цифры, записать несколько простых чисел так, чтобы их сумма оказалась меньше?
Подсказка 1
У вас есть конкретный набор цифр. Попробуйте понять, какие у вас могут быть простые числа, какие на них могут быть ограничения?
Подсказка 2
Давайте посмотрим, например, на цифру 4. Она явно не может быть на первом месте в простом числе. Подумайте в эту сторону и с остальными цифрами.
Например,
да
Ошибка.
Попробуйте повторить позже
Что больше: или
Подсказка 1
Неравенства a > b и a - b > 0 эквивалентны. Попробуем вместо сравнения исходных чисел сравнить их разность с нулем. Как можно преобразовать разность, чтобы было удобно ее оценивать?
Подсказка 2
Конечно! Перегруппируем слагаемые так, чтобы получилась разность двух скобок, внутри каждой у степеней одинаковое основание, а затем вынесем общий множитель. Как теперь сравнить числа?
Подсказка 3
Верно! Используем, что 2011 > 2009 и докажем, что в разности какое-то из чисел больше.
Запишем разность двух чисел, которые хотим сравнить, и преобразуем её:
Заметим, что и Следовательно, уменьшаемое больше вычитаемого, то есть разность положительна. Значит, первое число больше, будет знак
Ошибка.
Попробуйте повторить позже
Найдите наименьшее натуральное для которого число не является делителем числа
Источники:
Если то делится на (так как числа и содержатся среди чисел ). Так как то достаточно проверить делимость на при
Ясно, что делится на так как среди чисел заведомо найдётся чисел, кратных и чисел, кратных ( и ).
делится на так как среди чисел заведомо найдётся чётных чисел и чисел, кратных ().
не делится на так как число простое, и поэтому среди чисел есть лишь числа, кратных ().
Ошибка.
Попробуйте повторить позже
Чему может быть равно произведение нескольких различных простых чисел, если оно кратно каждому из них, уменьшенному на Найдите все возможные значения.
Подсказка 1!
1) Давайте попробуем восстанавливать наши множители с самого начала. Важное свойство почти всех простых чисел - нечетность. Значит перемножение будет делиться на двойку!
Подсказка 2!
2) Итак, поняли, что одно из простых чисел это 2. Попробуем понять, что тогда может быть следующим по возрастанию множителем в числе. Пусть это p2. Тогда раз наше число делится на p2-1, чему может быть равно p2?
Подсказка 3!
3) Верно, p2-1 может быть только двойкой, тогда p2 это 3! Теперь попробуйте таким же раскручиванием цепочки довести ее до конца, до момента, когда все множители, которые могут получиться, будут составными!
Хотя бы одно из простых чисел нечётно, потому число кратно двум. Пусть это где Далее будем находить числа по порядку
Число содержит делителем может быть только поскольку остальные делители больше откуда оно равно и Подойдёт пойдём дальше.
Число содержит делителями могут быть только но оба они меньше потому Подойдёт
Число содержит может быть равно только поскольку В первом случае составное, во втором и подходит
Пусть теперь число содержит отсюда равно одному из чисел где все числа, увеличенные на один, будут составными, откуда больше четырёх простых чисел быть не может.