Тема Высшая проба

Теория чисел на Высшей пробе

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

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

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

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

Подтемы раздела высшая проба

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

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

Задача 1#80738

Можно ли число 2024 представить в виде $a5+b3$ , где $a$ и $b$ — натуральные числа?

Источники: Высшая проба - 2024, 11.1 (см. olymp.hse.ru)

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

Подсказка 1

Если a ≥ 5, то левая часть уже слишком большая. Остаётся перебрать четыре значения для а и проверить, чему равно b

Подсказка 2

Должен найтись подходящий вариант!

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

3 10 5 3 2024 =1000+ 1024= 10 +2 = 4 +10

Ответ: да

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

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

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

Задача 2#80739

В некотором числе 10 единиц, 100 двоек, 1000 троек, …, $109$ девяток, расположенных в некотором порядке. Каждую секунду в нём стирают последнюю цифру. Правда ли, что в какой-то момент после начального получится число, делящееся на 9?

Источники: Высшая проба - 2024, 11.2 (см. olymp.hse.ru)

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

Подсказка 1

Давайте подумаем, каким образом нам можно число, которое кратно 9, независимо от остатка, который будет нами получен на каждом этапе вычеркивания. Удобная конструкция для нас - чтобы в течение 9 шагов у нас постоянно менялся остаток и не повторялся. Тогда, за 9 шагов у нас точно будет момент, когда остаток равнялся 0. Попробуйте придумать такую конструкцию.

Подсказка 2

Давайте попробуем вычеркнуть все 9 из числа(действительно, к чему бы они, если на деление на 9 они никак не влияют). Значит, если докажем, что в какой-то момент было число кратное 9 у полученного числа, то и у начального оно тоже было. Также, заметим, что под нашу конструкцию из первой подсказки подходит вариант, когда у нас стоит много одинаковых цифр подряд(хотя бы 9), взаимнопростых с 9, ведь там будет постоянно меняться остаток. То есть, нам надо набрать много одинаковых цифр подряд. Как это можно сделать?

Подсказка 3

Заметим, что чисел 8 у нас очень много. Больше чем 9 раз суммарно всех остальных. Давайте разобьем наше число на блоки по 9 цифр, которые не пересекаются. Что можно сказать про эти блоки? А что тогда надо доказывать в условиях на восьмерку?

Подсказка 4

Остается доказать, что найдется блок из цифр, равных 8. И это правда, так как иначе, в каждом блоке есть цифра, которая не 8 и тогда, цифр, не равных 8, у нас хотя бы 1/9 от общего количества. Противоречие. Значит, есть блок восьмерок. Победа.

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

Заметим, что если для исходного числа существует такой момент, то и для числа $A$ , полученного вычеркиванием всех девяток из исходного, он так же существует, поскольку каждое вычеркивание не меняет остаток при делении суммы цифр на 9.

Рассмотрим число $A$ . В силу неравенства $8 7 10 > 9⋅(10 + ...+ 10)$ , отношение количества восьмерок к оставшимся числам, больше 9. Отметим подряд идущие блоки по 9 чисел. Докажем, что существует блок, элементами которого являются лишь восьмерки. Пусть это не так, тогда в каждом блоке есть цифра отличная от восьмерки, следовательно, количество цифр, не являющихся восьмерками, хотя бы $1∕9$ от общего количество, что противоречит полученному неравенству.

Рассмотрим блок, состоящий только из восьмерок. Пусть число, полученное из $A$ вычеркиванием всех цифр до найденного блока, имеет остаток $s <9$ при делении на 9. Каждое вычеркивание 8 увеличивает остаток при делении на 9 на 1, следовательно, вычеркнув $9− s$ элементов в блоке, мы получим искомое число.

Ответ: да

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

Задача 3#67768

Натуральные числа $a,b,c$ таковы, что $1≤ a< b< c≤ 3000.$ Найдите наибольшее возможное значение величины

НОД(a,b)+ НОД (b,c)+ НОД (c,a)

Источники: Высшая проба - 2023, 11.3 (см. olymp.hse.ru)

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

Подсказка 1

Хочется получить какую-то оценку на эти НОДы. Понятно, что НОД(а,b) не больше чем a. Может попробовать что-то поделать с такой оценкой?

Подсказка 2

Если оценить так каждый НОД, получается как-то слишком грубо. Какой алгоритм приходит в голову, когда речь идёт о НОДах? Конечно же, алгоритм Евклида! Может, как-то улучшить оценку для НОД(a,b) с помощью него?

Подсказка 3

Если воспользоваться алгоритмом Евклида получиться, что: НОД(a,b)=НОД(a,b-a). Тогда т.к. НОД(a,b-a) не больше чем b-a, то и НОД(a,b) будет не больше чем b-a. если сделать тоже самое с НОД(b,c), что получится?

Подсказка 4

Итак, мы имеем что НОД(a,b) не больше b-a, а НОД(b,c) не больше c-b. Если их сложить, получится, что их сумма не больше чем (b-a)+(c-b)=с-а. Если оценить, что НОД(а,с) не больше чем a, то окончательно сумма всех НОДов будет не больше с, которое не больше 3000. Осталось только придумать пример...

Подсказка 5

Понятно, что с=3000. Чтобы достигалась оценка, необходимо, чтобы НОД(a,c)=a. Тогда с делится на a. Если мы сделаем так, что b тоже поделится на a, то, возможно, придумаем пример

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

Воспользуемся алгоритмом Евклида для $Н ОД(a,b),$ получим

НОД(a,b)= НО Д(a,b− a)

Заметим, что, так как НОД двух натуральных чисел не превосходит каждое из них,

НОД (a,b− a)≤ b− a⇒ НО Д(a,b)≤b − a

Аналогично получаем, что

НО Д(b,c)≤c− b

А также

Н ОД(c,a)≤ a

Складывая эти три неравенства, получаем

Н ОД(a,b)+ НОД(b,c)+ НОД(c,a)≤ (b− a)+ (c− b)+a = c≤3000

В качестве примера на $3000$ можно предъявить, например, $a= 1000,b= 2000,c= 3000.$ В этом случае

НО Д(a,b)+Н ОД(b,c)+Н ОД(c,a)= 1000+ 1000 +1000= 3000

Ответ: 3000

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

Задача 4#61459

Имеется дробь $1 n$ . Семиклассник Семёнов каждую минуту прибавляет к её числителю и знаменателю по $1$ и смотрит, можно ли сократить полученную дробь. Семёнов утверждает, что первый раз сократимая дробь получилась после $1000$ шагов. Стоит ли ему верить?

Источники: Высшая проба - 2020, 7.3 (см. olymp.hse.ru)

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

Подсказка 1

Давайте сначала поверим юному математику и посмотрим на дробь через 1000 минут. Какой вывод можно тогда сделать о делимости её знаменателя?

Подсказка 2

Верно, знаменатель кратен какому-то из простых делителей числа 1001. Пусть этот делитель равен p. Если бы мы хотели опровергнуть слова семиклассника, то скорее всего слова о том, что дробь сократилась впервые, верно?

Подсказка 3

Нужно найти такое число, которое выражается через слагаемые n и p и при этом делится на p. Хороша идея взглянуть на знаменатель дроби.

Подсказка 4

Мы обнаружили число n + p - 1, которое делится на р. Это как будто знаменатель дроби через р-1 минуту. А что с её числителем? Найдём противоречие, которое искали в подсказке 2?

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

Предположим, что Семёнов сказал правду, то есть в первый раз числитель и знаменатель $1+k n+k$ имеют общий делитель больше единицы через $k= 1000$ минут.

Получится $-1001- 7⋅11⋅13 n+1000 = n+1000$ , откуда $n +1000$ делится на какое-то число из множества ${7,11,13},$ давайте это число обозначим буквой $p.$

Заметим, что $1001$ делится на $p$ (если непонятно, то посмотрите, что такое $p$ ). Тогда $p+ (n+ 1000)− 1001= n+ p− 1$ тоже делится на $p$ .

Но отсюда сразу следует, что дробь уже через $p− 1$ шагов сократима: $1+p−1- --p-- n−1+p = n+p−1$ . А Семёнов сказал, что первый раз дробь сократима будет через $1000$ шагов. Но $p− 1 <1000$ . Семёнов, ты не прав!

Ответ:

нет

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

Задача 5#89083

В последовательности чисел Фибоначчи $1,1,2,3,5,8,13,21,...$ каждое следующее число, начиная с третьего, равно сумме двух предыдущих. Докажите, что среди чисел Фибоначчи нет ни одной натуральной степени числа $7.$

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

Подсказка 1

Какое первое число в последовательности чисел Фибоначчи кратно 7? Чему равен его индекс?

Подсказка 2

Первое число Фибоначчи, кратное 7 - это 21, которое является 8 числом Фибоначчи. Продолжив выписывать элементы данной последовательности можно заметить, что первые несколько членов, индексы которых кратны 8, делятся на 7. Докажите, что на 7 делятся те и только те члены последовательности чисел Фибоначчи, индексы которых кратны 8. Как можно доказать, что никакое из данных чисел не является степенью 7?

Подсказка 3

Показать, что каждое из них имеет простой делитель отличный от 7. Можно ли это сделать, найдя зависимость делимости членов последовательности от их индекса, аналогичную уже полученной?

Подсказка 4

Да, достаточно показать, что на 3 делятся те и только те числа Фибоначчи, номер которых делится на 4.

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

Для начала докажем, что на $7$ делятся те и только те числа Фибоначчи, номер которых делится на $8.$ Докажем это по индукции. База: Первое число Фибоначчи, кратное $7$ — это $21,$ которое является $8$ числом Фибоначчи.

Переход: Пусть этот факт был верен для всех чисел Фибоначчи с номерами от $1$ до $8k.$ Докажем, что он верен для чисел от $8k+1$ до $8k+ 8.$ Пусть число с номером $8k − 1$ имело остаток $a$ от деления на $7(a ⁄=0).$ Тогда числа с номерами $8k +1,...,8k +8$ будут иметь следующие остатки: $a,a,2a,3a,5a,a,6a,0.$

Теперь докажем, что на $3$ делятся те и только те числа Фибоначчи, номер которых делится на $4.$ Доказательство аналогично.

Следовательно, если число Фибоначчи делится на $7,$ то его номер делится на $8.$ Значит его номер делится на $4,$ а значит, само число обязано делиться на $3.$ Значит оно не может быть равно натуральной степени числа $7.$

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

Задача 6#80965

Найдите все натуральные числа, у которых разность между суммой двух самых больших собственных делителей и суммой двух самых маленьких собственных делителей является простым числом. (Делитель натурального числа называется собственным, если он отличен от $1$ и самого этого числа.)

Источники: Высшая проба - 2019, 9.5(см. olymp.hse.ru)

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

Имеет место один из двух случаев.
(a) Пусть оба наименьших делителя $p$ и $q$ — простые числа. Тогда простым будет число $n n r= (p + q)− (p+ q),$ откуда $pqr= (p +q)(n − pq).$ Поскольку числа $p+q$ и $pq$ взаимно просты, то $r =p +q,$ откуда $p= 2$ и $n = 4q.$ Но тогда в силу выбора $q$ получаем $q = 3$ и $n= 12.$
(b) Пусть наименьшие делители имеют вид $p$ и $2 p ,$ где $p$ простое. Тогда простым будет число $n n- 2 r= (p + p2)− (p+ p),$ откуда $2 3 p r= (p +1)(n − p ).$ Поскольку числа $p$ и $p+1$ взаимно просты, то $r= p+ 1.$ Это возможно только в случае $p= 2,r =3.$ В этом случае $2 3 p =n − p ,$ откуда $n= 12.$ Но этот случай невозможен, так как у $12$ один из двух наименьших делителей это $3.$

Ответ:

$12$

Курсы

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

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

Задача 7#77850

Чётное число $2N > 2$ называется подходящим, если оно делится на модуль разницы между наибольшим из своих чётных делителей, отличных от $2N$ , и наибольшим из своих нечётных делителей. Сколько существует подходящих чётных чисел, не превосходящих $2018?$

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

Подсказка 1

Попробуем записать число в виде 2^k*m, где m - нечетно. Запишем условие и подумаем, какие ограничения можно наложить на переменные!

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

Предположим, что число $2N$ подходящее. Пусть $2N = 2km,$ где $m$ нечётное. Если $k≥ 2,$ то условие говорит, что $k 2 m$ делится на $k−1 k−1 2 m − m= m (2 − 1),$ что возможно только при условии $k= 2.$ Если $k= 1$ и $m =ps,$ где $p$ минимальный простой нечетный делитель $m,$ то $2ps$ делится на $2s− ps= (2− p)s,$ откуда имеем $. p.. (p− 2),$ значит, $p =3.$ Число $N$ или имеет остаток $2$ по модулю $4$ или имеет остаток $3$ по модулю $6.$ Тем самым число $2N$ является подходящим, если число $N$ может иметь остаток $2, 3, 6, 9, 10$ по модулю $12.$ Это значит, что в каждом ряду из $12$ последовательных четных чисел ровно пять подходящих. Используя равенство $2018= 2⋅(12⋅84+ 1),$ получаем ответ $420= 5⋅84.$

Ответ: 420

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

Задача 8#61644

Найдите все натуральные числа $n$ от $1$ до $100$ включительно такие, что если перемножить все делители числа $n$ (включая $1$ и $n$ ), получим число $3 n .$

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

Ясно, что $n= 1$ подходит, ведь произведение из условия будет равно $1 =n3.$ Рассмотрим теперь $n> 1.$ Обозначим произведение его делителей буквой $P.$

Если число $n$ не является точным квадратом, то его делители можно разбить на $s$ пар с произведением $n$ в каждой (если число $n$ делится нацело на $√ - k < n$ , то оно делится нацело и на $n n-- √- m = k > √n = n$ ). Например, $18 =1 ⋅18= 2⋅9= 3⋅6$ . Так что делители бьются на пары с произведением $n$ в каждой, откуда $s P =n .$

По условию $3 P =n$ , тогда $s= 3.$ Число должно иметь $6$ делителей.

Если число является точным квадратом, то есть ещё делитель $√- n,$ поэтому $s+1 3 P = n 2 = n$ — противоречие с тем, что $s$ — целое число пар.

Для $k k n =p11⋅...ptt ,ki ∈ℕ$ количество различных делителей равно $t (1+ k1)...(1+ kt)≥ 2$ (берём каждое простое в каждой степени, считая нулевую). Если число $n$ должно иметь ровно $6$ делителей, то $6≥ 2t =⇒ t= 1 или t =2$ .

При $t= 1$ получаем $n= p5$ . Среди чисел от $1$ до $100$ подходит только $n =32.$

При $t= 2$ получаем $n= p1p22.$ Из условия на промежуток

$p22 ≤ 1020= 50 ⇐⇒ p2 ≤7 ⇐ ⇒ p2 ∈ {2,3,5,7}$ .

Добавим также условие $p22 ≥ 4 =⇒ p1 ≤ 25$ , затем остаётся просто перебрать по очереди все $p2$ , а затем выбрать подходящие простые $p1 ≤ 25$ , получим числа

22⋅3 =12,22 ⋅5 =20,22 ⋅7 =28,22⋅11 =44,22 ⋅13= 52,22⋅17= 68,22⋅19= 76,22⋅23= 92

32⋅2= 18,32⋅5= 45,32⋅7= 63,32⋅11= 99

52⋅2=50,52⋅3= 75

72⋅2= 98

Ответ:

$1,12,18,20,28,32,44,45,50,52,63,68,75,76,92,98,99$

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

Задача 9#75971

Тройка целых чисел $(x,y,z),$ наибольший общий делитель которых равен $1,$ является решением уравнения

2 2 3 2 2 y z+ yz =x + x z− 2xz

Докажите, что $z$ является кубом целого числа.

Источники: Высшая проба - 2017, 11.4(см. olymp.hse.ru)

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

Подсказка 1

В исходном выражении уже есть куб. Можно ли как-то его переписать так, чтобы получилось, что z делит этот куб?

Подсказка 2

Верно! z(y² + yz - x² + 2xz) = x³. Теперь, если доказать, что НОД z и y² + yz - x² + 2xz, то задача будет решена. Как это сделать?

Подсказка 3

По алгоритму Евклида можно получить, что НОД этих чисел такой же, как НОД z и y² - x². Пойдем от противного: может ли этот НОД быть равен t > 1?

Подсказка 4

Точно! Если t > 1, то x³ делится на t. Кроме того, t делится на некоторое простое q, а тогда и x делится на это q. Какой вывод можно сделать?

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

Запишем равенство в следующем виде: $z(y2+ yz− x2 +2xz)= x3.$ Если мы докажем, что НОД $z$ и $y2+yz− x2+ 2xz$ равен $1,$ то тогда $z$ будет кубом. Предположим, что $z$ в этой ситуации не является кубом. Тогда в разложение $z$ входит какое-то простое число $p$ в степени, не кратной $3.$ Скобка $2 2 y + yz− x +2xz$ на $p$ не делится, значит $p$ входит в $3 x$ в степени, не кратной $3,$ чего быть не может.

Итак, докажем взаимною простоту $z$ и $2 2 y + yz− x + 2xz.$ Ясно, что НОД этих чисел равен НОДу $z$ и $2 2 y − x .$ предположим, что этот НОД равен $t> 1.$ Тогда $3 x$ делится на $t.$ Пусть $t$ делится на некоторое простое число $q,$ тогда на $q$ делится $x$ и $2 2 y − x .$ Значит, $y$ также делится на $q.$ Также $z$ делится на $t,$ а значит и на $q.$ Получается, что НОД $x,y$ и $z$ больше $1,$ противоречие. Значит, НОД $z$ и $2 2 y − x$ равен $1,$ что и требовалось.

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

Задача 10#88130

Найдите все натуральные числа $n$ от 400 до 600 такие, что если перемножить все делители числа $n$ (включая 1 и $n$ ), получим число $5 n$ .

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

Утверждается, что $n$ удовлетворяет условию задачи, если и только если его разложение $n= pk1...pks 1 s$ на простые множители имеет вид либо $9 n =p$ , либо $4 n= p1p2$ .

Действительно, для каждого $j =1,...,k1$ имеется $(k2+ 1)...(ks+ 1)$ делителей числа $n$ , содержащих $p1$ в степени $j$ в разложении на простые множители: все эти делители имеют вид $j m1 ms p1p2 ...ps , mi ∈ {0,...,ki}$ . Следовательно, произведение всех делителей числа $n$ содержит $p1$ в степени $1 (k2+ 1)...(ks +1)(1+...+k1)= 2(k1+1)...(ks+1)k1$ . Условие, что произведение всех делителей равно $5 n$ , эквивалентно утверждению, что каждое $pj$ входит в их произведение в степени $5kj$ , и, тем самым, предыдущее выражение равно $5k1$ . Другими словами,

1 2 (k1+ 1)...(ks+ 1)= 5.

С другой стороны, $kj ≥ 1$ . Отсюда следует, что $s≤ 2$ . Пусть $s= 2$ . Тогда одно из $kj$ , скажем, $k1$ равно 1 , а тогда $k2 = 4$ (простота числа 5). В случае, когда $s= 1,k1 = k$ , получаем уравнение $12(k+ 1)= 5$ , то есть $k =9$ . Итак, все числа $n ⁄= 1$ , удовлетворяющие условию задачи, имеют разложение на простые множители вида либо $n= p1p42,p1 ⁄= p2$ , либо $n = p9;p1,p2,p>1$ . Перечислим те из них, которые лежат между 400 и 600.

Числа $n= p1p42$ . Имеем $p42 ≤600∕2= 300$ , тем самым, $p2 ≤ 4,p2 ∈ {2,3}$ . Итак, $16 ≤p42 ≤ 81$ . Следовательно, $4 =[400∕81]< p1 ≤ [600∕16]= 37$ , а, значит,

p1 ∈ {5,7,11,13,17,19,23,29,31,37},p2 ∈{2,3}.

Выписывая всевозможные произведения $n =p1p42$ , лежащие в промежутке от 400 до 600 , с вышеуказанными $p1$ и $p2$ , получаем $5⋅34 = 405,7⋅34 = 567,29⋅24 = 464,31⋅24 =496,37⋅24 = 592$ .

Единственное $n =p9$ , лежащее между 400 и 600 , есть $512=29$ . Итого получаем список всех возможных чисел $n$ :

n =405,464,496,512,567,592.

Ответ: 405,464,496,512,567,592

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

Задача 11#94877

На доске написано несколько цифр (среди них могут быть одинаковые). На каждом шаге две цифры стираются и пишутся цифры, из которых состоит их произведение. (Например, вместо $5$ и $6$ пишется $3$ и $0$ , а вместо $2$ и $4$ пишется $8$ ). Доказать, что через несколько шагов на доске останется одна цифра.

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

При решении задачи будем использовать свойство уменьшения первого разряда. Оно состоит в том, что при умножении двух цифр $a$ и $b$ получается либо однозначное число (цифра), либо двузначное, и в последнем случае первая цифра двузначного произведения меньше, чем минимальная из цифр $a,b$ .

Действительно, двузначные числа $a0 =10× a$ и $b0 =10× b$ больше, чем $ab$ , так как $a,b< 9$ . Тем самым на каждом шаге либо получается на цифру меньше (первый случай), либо число цифр сохраняется, но минимальная из всех цифр, написанных на доске, не увеличивается.

_________________________________________________________________________________________________________________________________________________________________________________

Будем доказывать утверждение задачи индукцией по числу $n.$ При $n = 1$ утверждение очевидно. Утверждение для $n = 2$ следует из свойства уменьшения первого разряда, в силу которого через несколько шагов останется одна цифра.

_________________________________________________________________________________________________________________________________________________________________________________

Пусть утверждение доказано для $n =k$ . Пусть $m$ — минимальная из цифр, написанных на доске. Достаточно показать, что через несколько шагов либо число цифр уменьшится, либо минимальная цифра уменьшится: появится цифра меньше $m$ .

Предположим противное. Тогда число цифр не уменьшается и в каждый момент есть цифра $m$ , к которой очередной шаг задачи не применяется: каждый шаг не затрагивает хотя бы одну цифру $m$ . В противном случае, если осталась одна или две цифры $m$ , и к ней (соответственно, к ним обеим) применен шаг задачи, и при этом число цифр не уменьшается, то минимальная цифра уменьшится в силу свойства уменьшения первого разряда.

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

Интенсивы

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

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

Задача 12#73180

На доске написаны числа $1∕2,1∕3,...,1∕100$ . Разрешается стереть любые два числа $a$ и $b$ и записать вместо них $a+b− ab$ . После нескольких таких операций на доске осталось одно число. Чему оно может быть равно?

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

Если на доске написаны числа $x,x ,...,x 1 2 k$ , то будем следить за величиной $(x − 1)(x − 1)...(x − 1) 1 2 k$ . Заметим, что вместо выражения вида $(a− 1)(b− 1)$ будет выражение $a+ b− 1 − ab= −(a− 1)(b− 1)$ . То есть за каждый ход рассматриваемое выражение меняет знак. Изначально оно было равно

( 1 ) (1 ) ( 1 ) 1 2 99 1 2 − 1 3 − 1 ... 100 − 1 = −2 ⋅3 ⋅...⋅100 = − 100.

Значит, и через 98 операций наше выражение будет равно $− 1100-$ . То есть в конце будет выписано число $− 1100 + 1= 0,99.$

Ответ: 0,99

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

Задача 13#89720

Найдите наименьшее натуральное число, представимое в виде $20x2+ 80xy+ 95y2$ для целых $x$ и $y.$

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

Подсказка 1

Давайте рассмотрим число, полученное из данного путем деления на 3. Если для нового выражения мы найдем минимальное число, представимое таким образом, то и для изначально уравнения минимальным будет данное, умноженное на 5.

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

Поделим все на $5.$

2 2 2 2 4x +16xy+ 19y = 4(x+ 2y) + 3y

По модулю $4$ полученное выражение сравнимо либо с $0,$ либо с $3.$ Тогда это выражение, раз оно принимает натуральное значение, хотя бы $3.$ Причем значение, равное $3,$ достигается при $y = 1,x= −2.$ Тогда минимальное натуральное значение исходного выражения равно $15.$

Ответ:

$15$

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

Задача 14#72110

Найдите все натуральные числа $n$ , такие, что число $n2+ 77n$ является точным квадратом натурального числа.

Источники: Высшая проба - 2015, задача 9.6(см. olymp.hse.ru)

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

Решим уравнение $n2+ 77n =q2$ в натуральных числах. Преобразуем левую часть следующим образом: $n2+ 2⋅ 77⋅n+ 772-− 772= q2. 2 4 4$ Теперь запишем уравнение в виде $772 2 772- (n+ 2 )− q = 4 .$ Домножим равенство на $4$ и разложим левую часть на множители через разность квадратов: $2 (2n − 2q+ 77)(2n +2q+ 77)=77 .$ Осталось перебрать возможные варианты. Для упрощения перебора заметим, что $2n− 2q+ 77 <2n +2q+ 77.$ Следовательно, для скобочек возможны следующие варианты: $1$ и $2 77 ,$ $7$ и $2 7⋅11,$ $11$ и $2 7 ⋅11,$ $49$ и $121.$ Осталось разобрать каждый случай и написать ответ.

Ответ:

$1444,175,99,4$

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

Задача 15#64855

Найдите все пары взаимно простых натуральных чисел $a$ и $b$ такие, что $2a2 +3b2$ делится на $2a+3b.$

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

Подсказка 1

Пусть m = 2а+3b. Тогда отсюда выражается, например, 2а, которое при возведении в квадрат превращается в 4а^2. А у нас в изначальном выражении есть 2а^2, значит таким образом мы сможем узнать что-то о соотношении b и m. Аналогично узнаем про число а и m.

Подсказка 2

Верно, и 15b^2 кратно m, и 10a^2. Используя понимание взаимной простоты чисел а и b мы должны осознать, какие простые делители есть у m.

Подсказка 3

Могут ли простые делители числа m входить в него больше, чем в первой степени? Получив ответ на этот вопрос, мы найдем единственно возможные варианты числа m = 2а+3b и проверим их, помня, что работаем с натуральными числами.

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

Заметим, что $4a2− 9b2 = (2a+ 3b)(2a − 3b) ≡ 0, 2a+3b$ отсюда $4a2 − 9b2− 2(2a2+3b2)=− 15b2 ≡ 0 2a+3b$ и $4a2− 9b2+ 3(2a2+ 3b2)= 10a2 ≡ 0. 2a+3b$ Пусть $2a+ 3b$ содержит некоторый делитель $d,$ который взаимно прост с $10$ и $15$ — тогда на это число должны делиться $a2$ и $b2,$ что невозможно, поскольку $(a2,b2)= 1.$ Отсюда $2a +3b$ делится только на $2,3,5$ (из простых чисел). Если какое-то простое число $p$ входит в него большей степени $q > 1,$ то $pq−1$ делит $a2$ и $b2,$ значит, степень каждого простого не больше первой. То есть $2a+ 3b$ может принимать значения $1,2,3,5,6,10,15,30.$ Первые три невозможны, пятёрка даёт нам $a= b= 1,$ что подходит. Пятый случай также невозможен, в шестом $a =b =2,$ условие взаимной простоты не выполнено. Для $15$ есть случаи $a =b =3$ и $a= 6,b= 1,$ нам подойдёт только второй. Для $30$ получаем $(3,8),(6,6),(9,4)$ — подойдут первый и третий случаи. Остаётся выписать ответ.