Тема ТЕОРИЯ ЧИСЕЛ

Уравнения в целых числах

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

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

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

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

Подтемы раздела теория чисел

Разделы подтемы Уравнения в целых числах

Выбор модуля и перебор случаев в уравнениях над Z

Разложение на целые скобки

Оценки в уравнениях над Z

Уравнения на НОД и НОК

Линейные диофантовы уравнения

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

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

Задача 181#49156Максимум баллов за задание: 7

Для каких натуральных $y$ уравнение

2 x + НОД (y;4)⋅x − 6Н ОД(y;3)= 0

имеет целые решения?

Источники: Росатом-12, 11.5

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

Подсказка 1

По сути перед нами квадратное уравнение относительно х, но со странными коэффициентами. Подумайте, как можно в явном виде определить эти коэффициенты.

Подсказка 2

Да, мы можем определить эти коэффициенты только по остатку от y при делении на 12. То есть нужно перебрать 12(на самом деле меньше вариантов), получить квадратное уравнение и решить задачу(но главное-правильно записать ответ, ведь мы берем только остаток, и а y может быть и другим)

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

Заметим, что $a= НОД(y;4)∈ {1,2,4},b= НО Д(y;3)∈{1,3}$ , обе принадлежности определяются остатком $y$ по модулю $12$ . Разберём случаи

$a =1,b= 1$ . Получаем уравнение $x2+ x− 6= 0$ , которое имеет целые корни $x= −3,2$ . Этому случаю удовлетворяют остатки $1,5,7,11$ .
$a =2,b= 1$ . Получаем уравнение $2 x +2x− 6= 0$ , которое целых корней не имеет.
$a =4,b= 1$ . Получаем уравнение $2 x +4x− 6= 0$ , которое целых корней не имеет.
$a =1,b= 3$ . Получаем уравнение $x2 +x− 18= 0$ , корней нет.
$a =2,b= 3$ . Получаем уравнение $x2 +2x− 18= 0$ , корней нет.
$a =4,b= 3$ . Получаем уравнение $x2 +4x− 18= 0$ , корней нет.

Ответ:

$y ∈{{1,5}+ 6k}, k∈ ℕ∪{0}$

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

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

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

Задача 182#49161Максимум баллов за задание: 7

Найдите натуральные числа $n$ , для которых

( 2 ) ( 2 ) НОК n,n +15 ⋅НОК(n,n+ 3)=5 n + 45 .

Источники: Росатом-12, 11.4

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

Подсказка 1

Попробуйте поподстовлять достаточно большие n в это уравнение и что-то заметить. Какая часть уравнения выбивается и почему?

Подсказка 2

Давайте посмотрим на выражение. Видно, что слева что-то очень большое, как минимум потому, что НОК(n,n^2+15)-это что-то (по примерным оценкам) точно большее квадрата(если мы оцениваем в общем виде), да еще, к тому же, НОК(n,n+3)-это тоже что-то большое, так как их максимальный НОД это 3(их разница делится лишь на 1 и 3). Значит, в задаче используется оценка. Подумайте как оценить каждый НОК

Подсказка 3

Любой НОК(a,b)>=max(a,b). Зная это, каждый из НОК-ов оценивается понятно, и произведение НОК-ов - кубическая функция. Но при этом квадратная ее больше или равна. Часто ли такое случается?

Подсказка 4

Ну конечно же, не часто. Потому что рано или поздно кубическая функция станет больше квадратичной. И это происходит только при n<=5. Осталось перебрать и получить ответ.

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

Воспользуемся очевидным неравенством $Н ОК(a,b)≥ max{a,b}$ . Отсюда следует

2 2 3 2 5(n +45)≥(n + 15)⋅(n+ 3) ⇐ ⇒ f(n)= n − 2n + 15n− 180 ≤0

Заметим, что $f′(x)= 3x2 − 4x+ 15> 0∀x∈ ℝ$ , то есть функция монотонно возрастает. Поскольку при $n = 6$ имеем $f(n)=54> 0$ , то $n ≤5$ . Заметим также, что один из НОК-ов должен делиться на $5$ , что не выполняется при $n= 1,3,4$ , поэтому остаётся перебрать два случая

$n =2$ . Получаем $38⋅5⁄= 5⋅(1+45)$ .
$n =5$ . Получаем $40⋅40⁄= 5⋅70$ .

Ответ:

решений нет

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

Задача 183#81761Максимум баллов за задание: 7

Найдите все тройки натуральных чисел $(x,y,z),$ такие что $x≤ y ≤ z,$ удовлетворяющие уравнению

3( 3 3) x y +z = 2012(xyz+2)

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

Для начала отметим, что $x$ делит $2012⋅2 =23⋅503.$ Это выполнено так как $(x, xyz +2)≤ 2.$ Если $503 |x,$ то правая часть уравнения делится на $3 503,$ откуда следует, что $2 503 |xyz+ 2.$ Это не верно так как $503|x.$ Следовательно, $m x= 2 ,$ где $m ∈ {0,1,2,3}.$ Если $m ≥2$ , то $6 2 |2012(xyz+ 2).$ Однако в таком случае 2012 и $m xyz +2= 2 yz+ 2$ делятся на $2 2$ и $1 2$ соответственно и не делятся на большие степени $2.$ Значит $x =1$ или $x= 2,$ откуда следует, что выполнено одно из уравнений

y3+ z3 =2012(yz+ 2) или y3+ z3 = 503(yz+1)

В обоих случаях простое $503= 3⋅167+2$ делит $y3 +z3.$ Утверждается, что $503|y +z.$ Это очевидно если $503|y$ или $503 |z,$ так что будем рассматривать случай $503∤y$ и $503∤z.$ Тогда $502 502 y ≡ z (mod 503)$ по малой теореме Ферма. С другой стороны, из $3 3 y ≡ −z (mod 503)$ следует, что $3⋅167 3⋅167 y ≡ −z (mod 503),$ то есть $501 501 y ≡ −z (mod 503).$ Из этих двух сравнений следует, что $y ≡− z (mod 503),$ что и требовалось доказать.

Таким образом, $y+ z = 503k,$ где $k≥ 1.$ Поскольку $3 3 ( 2 ) y + z = (y +z) (y − z) +yz ,$ два уравнения выше принимают вид

2 k(y− z)+ (k− 4)yz = 8 k(y− z)2+ (k− 1)yz = 1

Рассмотрим уравнение $(1).$ Утверждается, что если оно выполнено, то $(k− 4)yz ≤8,$ откуда $k≤ 4.$ Действительно, если $k >4,$ то $1 ≤(k− 4)yz ≤ 8,$ откуда $y ≤8$ и $z ≤ 8.$ Это невозможно поскольку $y+z =503k≥ 503.$ Отметим дальше, что если выполнено уравнение $(1),$ то $y3 +z3$ четное. Поэтому $y+ z = 503k$ также является четным числом, откуда $k$ четное. Тогда $k= 2$ или $k= 4.$ Ясно, что у $(1)$ нет целочисленных решений при $k= 4.$ Если $k= 2$ то $(1)$ обращается в $(y+ z)2 − 5yz = 4.$ Поскольку $y+ z = 503k =503⋅2,$ уравнение принимает вид $5yz =5032⋅22− 4.$ Однако $5032⋅22− 4$ не кратно $5.$ Таким образом, уравнение $(1)$ не имеет целочисленных значений.

Из уравнения $(2)$ следует, что $0 ≤(k− 1)yz ≤ 1,$ поэтому $k =1$ или $k= 2.$ Также верно, что $0≤k(y− z)2 ≤1,$ поэтому $k= 2$ только тогда, когда $y = z.$ Однако в таком случае из первого двойного неравенства получаем, что $y =z =1,$ что противоречит неравенству $y+ z ≥503.$ Значит $k= 1$ и уравнение (2) принимает вид $(y − z)2 = 1,$ откуда $z− y = |y − z|= 1.$ Из условий $k = 1$ и $y+ z = 503k$ получаем, что $y = 251$ , $z = 252.$ Таким образом, $(2,251,252)$ является единственным решением исходного уравнения.

Ответ:

$(2,251,252)$

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

Задача 184#41317Максимум баллов за задание: 7

Два трёхзначных числа таковы, что сумма остальных трёхзначных чисел ровно в $770$ раз больше одного из них. Найдите наибольшее из этих чисел.

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

Подсказка 1

Пусть наши числа это x и y. В условии упоминается сумма всех трехзначных без них, получается нужно её записать. Тогда эта сумма делится на 770. Что тогда можно сказать об x + y?

Подсказка 2

Сумма всех чисел без x и это (999+100/2 * 900 - x - y, а т.к. это делится на 770, значит x+y = 210(mod 770). Какой тогда может быть их сумма? Остаётся лишь рассмотреть случаи x+y. Как после этого находить x и y по отдельности?

Подсказка 3

Поделив сумма всех чисел без x и y на 770, найдем x или y, а оттуда проверим, выполняется ли условие!

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

Посчитаем сумму всех трёхзначных чисел без двух выбранных $x,y :x< y$

999+100 100+ ...+999− x− y = 2 ⋅900− x− y = 450⋅1099− x − y =494550− x− y

Из условия следует, что эта сумма в $770$ раз больше $x$ или $y,$ так что

494550− x− y7≡70 0.

494550 ≡ 210 ≡ x+ y. 770 770

Тогда $x+y ∈{210,980,1750}$ — другие значения невозможны, поскольку оба числа трёхзначные. Разберём эти три случая:

$x +y = 1750,494550− x− y = 640⋅770,$ то есть $x= 640,y = 1110$ — такое невозможно.
$x +y = 980,494550 − x− y = 641⋅770,$ тогда $y = 641,x= 339.$ Здесь наибольшее будет $641.$
$x +y = 210,494550 − x− y = 642⋅770,$ здесь $y = 642$ и $x< 0,$ также невозможно.

Итак, единственным возможным значением будет $641.$

Ответ:

$641$

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

Задача 185#70323Максимум баллов за задание: 7

Дано простое число $p.$ Решите в натуральных числах уравнение

2 2 x = y +2010p

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

Подсказка 1

Воспользуйтесь ФСУ.

Подсказка 2

Разложите 2010 на простые множители.

Подсказка 3

Что можно сказать о четностях (x+y) и (x-y)?

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

$2010= 2⋅3⋅5⋅67;$

Преобразуем исходное уравнение

2 2 x − y = 2010p⇔ (x− y)(x +y)= 2⋅3⋅5⋅67

Заметим, что $x− y$ и $x+ y$ одинаковой четности, так как $x+ y = x− y+ 2y.$

Поэтому, так как $2010$ четно, обе скобки тоже должны быть четными. И тогда $p= 2,$ иначе

. (x− y)(x +y)..4,

но $2010p$ не кратно $4.$

Получаем

(x− y)(x+ y)= 22⋅3⋅5⋅67

Поскольку $x,y ∈ℕ,$ обе скобки положительные, а также $x +y > x− y.$

Следовательно, возможны только следующие случаи:

⌊ x− y = 2⋅3⋅5 и x+ y = 2⋅67 || x− y = 2⋅3 и x+ y = 2⋅5⋅67 ||⌈ x− y = 2⋅5 и x+ y = 2⋅3⋅67 x− y = 2 и x+ y = 2⋅3⋅5⋅67

Решив систему уравнений в натуральных числах в каждом из случаев, получаем ответ.

Ответ:

$(82,52),(338,332),(206,196),(1006,1004)$ при $p= 2,$ иначе решений нет.

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

Задача 186#70326Максимум баллов за задание: 7

Целые числа $m$ и $n$ таковы, что

4m+ 5n= mn − 9

Найдите, какое наибольшее значение может принимать $m$ .

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

Подсказка 1

Когда мы видим выражение вида a * mn + b * n + c * m + d, то первым делом нам нужно попробовать его разложить на скобки, добавив некоторую константу к обеим частям уравнения. Попробуйте это сделать, ведь с множителями удобнее работать чем с слагаемыми!

Подсказка 2

Получится (m-5)(n-4)=29. Много ли целых чисел могут давать в произведении 29?

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

Первое решение. Постараемся разложить на скобки:

mn − 4m− 5n− 9= 0

mn− 4m − 5n+ 20= 29

(m − 5)(n − 4)= 29

В правой части простое число, поэтому в левой части целые числа в скобках могут равняться только 1 и 29, либо -1 и -29. Наибольшее значение $m$ достигается при $m − 5 =29 ⇐⇒ m = 34.$

______________________________________________________________________________________________________________________________________________________

Второе решение. Запишем равенство в виде

m = 9+-5n =5+ -29- ≤5+ 29= 34 n− 4 n − 4

Равенство реализуется при $n =5.$

Ответ: 34

Курсы

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

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

Задача 187#104432Максимум баллов за задание: 7

Найдите все такие пары натуральных чисел $a$ и $b,$ что $a1000 +1$ делится на $b619$ и $b1000+ 1$ делится на $a619.$

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

Если $a =1,$ то, очевидно, $b=1;$ при этом пара $(1,1)$ подходит. Осталось разобрать случай $a,b>1.$ Заметим сразу, что $a$ и $b$ взаимно просты; пусть $a> b.$

Число

1000 1000 1000 ( 1000 ) A =a + b + 1=a + b + 1

делится на $a619;$ аналогично, $A$ делится на $b619,$ а из взаимной простоты и на их произведение. Итак, $a1000+b1000+ 1≥ a619b619,$ а значит, $1001 1000 619619 a ≥ 2a ≥ a b ,$ или $382 619 a ≥ b .$ С другой стороны, $1001 1000 619 b > b + 1≥ a .$ Итак,

1001⋅382 619⋅382 619⋅619 b > a ≥ b

Но $1001⋅382< 6192$ — противоречие.

Ответ:

$(1,1)$

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

Задача 188#67141Максимум баллов за задание: 7

Решите уравнение в целых числах:

∘ --2-------- 9x +80x− 40= 3x − 20y

Источники: ПВГ-2010, 11.5 (см. pvg.mk.ru)

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

Подсказка 1:

Хммм... В условии есть корень, от которого сразу же хочется избавиться. Что можно сделать?

Подсказка 2:

Конечно! Запишем себе где-то на полях условие, что 3x−20y неотрицательно и смело возведём в квадрат. Давайте теперь в левой и правой части разложим выражения так, чтобы получить произведение множителя на скобку. Что можно сказать, помня, что x и y — целые?

Подсказка 3:

Да! Заметим, что (2 + 3y) не может быть равным нулю, поэтому на него можно поделить! Окей, с одной стороны получили всё ещё целый x, а с другой — отношение двух двучленов. Что всё это значит?

Подсказка 4:

Да! Получаем, что часть с игриками должна быть целым числом! Умножим обе части на 9. Получим 9x-30y+20=49/(3y+2). Тогда 3y+2 — делитель числа 49. Осталось только перебрать все возможные случаи и записать ответ!

Подсказка 5:

(Не забудем, что 3x−20y неотрицательно!) Чтобы сократить перебор, можно посмотреть на то, какие остатки дают левая и правая части, например, при делении на 3 ?)

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

Сначала бездумно возведём обе части в квадрат, в конце уже проверим, чтобы $3x− 20y$ было неотрицательно.

2 2 2 9x +80x− 40=9x − 120xy +400y

2 40x(2+ 3y) =40(10y + 1)

Так как $x,y$ целые, то можно поделить на ненулевое $2+ 3y$ обе части уравнения и получить, что целым числом должно являться

x= 10y2-+1- 3y+2

Поделим многочлен на многочлен в столбик: для начала избавимся от $2 10y,$ для этого надо домножить $3y+ 2$ на $10 3 y.$ Получим

10 20 10y2+ 1= (3y+ 2)⋅3-y− 3-y+ 1

Теперь разделим $− 230y$ на $3y+ 2:$

− 20-y = − 20⋅(3y +2)+ 40 3 9 9

Тогда

10y2+ 1= 10y⋅(3y +2)− 20⋅(3y +2)+ 40+ 1= 3 9 9

10 20 49 = 3 y⋅(3y +2)− 9 ⋅(3y +2)+ 9

Получим

10y2+ 1 10 20 49- -3y+-2-= -3 y− 9-+ 3y9+-2

Тогда получается, что должно быть целым и число

10 20 -49∕9- x= 3 y− 9 + 3y+ 2

После переноса слагаемых и умножения на $9$ обоих частей получим

49 9x− 30y+ 20= 3y+-2 .

Делителями (целыми) числа $49$ являются $− 49,− 7,− 1,1,7,49.$ Заметим, что только $− 1,−7,−49$ дают остаток $2$ по модулю $3,$ поэтому скобка $3y+ 2$ может принимать только эти значения. Разберём случаи

$3y+ 2= −1 ⇐⇒ y = −1 =⇒ 20+ 9x − 30y = −49 ⇐⇒ x= −11$
$3y+ 2= −7 ⇐⇒ y = −3 =⇒ 20+ 9x − 30y = −7 ⇐⇒ x= −13$
$3y+ 2= −49 ⇐⇒ y = −17 =⇒ 20 +9x− 30y =− 1 ⇐⇒ x= −59$

Остаётся проверить, что $3x− 20y$ принимает неотрицательные значения для полученных решений. Из трёх кандидатов не подходит только первая пара, потому что $3⋅(− 11)− 20⋅(−1)= −13< 0.$

Ответ:

$(−13,− 3),(−59,−17)$

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

Задача 189#91037Максимум баллов за задание: 7

В диване живут клопы и блохи. Боря лежит на диване и рассуждает: если клопов станет в несколько раз больше, то всего насекомых будет $2012,$ а если блох станет во столько же раз больше, а число клопов не изменится, то всего насекомых будет $2011.$ Сколько же насекомых живет в диване сейчас?

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

Подсказка 1

Обозначим переменными количество клопов и блох, также введём коэффициент, показывающий во сколько раз мы увеличиваем выражение. Кажется теперь можно составить уравнения...

Подсказка 2

Теперь можно попытаться разложить на множители то, что у нас получилось и попытаться увидеть что-нибудь красивое. Мы получили, что произведение двух скобок равно 1, значит мы с уверенностью можем сказать чему равно количество насекомых и коэффициент увеличения.

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

Пусть в диване живут $x$ клопов и $y$ блох. Через $n$ обозначим количество, в которое будем увеличивать. Тогда по условию имеем $nx +y = 2012,x+ ny = 2011.$ Если вычесть из второго равенства первое, мы получим $(n− 1)(x− y)= 1.$ То есть $n − 1$ делит $1,$ а значит $n − 1$ равно либо $1,$ либо $− 1.$ Второй вариант нам не подходит, потому что тогда $n= 0.$ Следовательно, $n =2.$ Если сложить равенства, полученные выше, и поделить на $3,$ получим: $x+ y = 1341.$

Ответ:

$1341$

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

Задача 190#104433Максимум баллов за задание: 7

Целые числа $a,$ $b,$ $c,$ натуральное число $n$ и простое число $p$ таковы, что

n n n a +pb= b + pc =c + pa

Докажите, что $a= b= c.$

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

Первое решение. Если два из чисел $a,$ $b,$ $c$ равны, то сразу следует, что все три равны. Поэтому можно предположить, что числа различны попарно. Вычитая из первого уравнения второе, имеем $n n a − b = −p(b− c)$ и два аналогичных, которые при умножении дают

an− bn bn− cn cn− an 3 -a−-b-⋅-b−-c-⋅-c−-a-= −p (1)

Если $n$ нечётно, то разности $an− bn$ и $a− b$ имеют одинаковый знак, и произведение слева положительно, в то время как $− p3$ отрицательно. Следовательно, $n$ должно быть чётным.

Пусть $d$ — наибольший общий делитель разностей $a− b,$ $b− c,$ $c− a,$ так что

a− b= du; b− c =dv; c− a= dw

где $Н ОД(u,v,w)= 1$ и $u+ v+ w= 0.$

Из $an− bn = −p(b− c)$ следует, что $(a− b) | p(b− c),$ то есть

u | pv; аналогично v | pw,w | pu

Поскольку $НОД (u,v,w)= 1$ и $u +v +w =0,$ не более чем одно из чисел $u,$ $v,$ $w$ может делиться на $p.$ Если $p$ не делит ни одно из них, имеем

u | v, v | w, w | u

откуда $|u|= |v|= |w|=1;$ но это противоречит $u+ v+ w= 0.$

Таким образом, $p$ должно делить ровно одно из этих чисел. Без ораничений общности, $p | u,$ то есть $u =pu1.$ Теперь получаем, аналогично предыдущему, $|u1|= |v|= |w |=1.$ Из уравнения $pu1+v +w = 0$ следует, что $p$ было чётно, то есть $p= 2.$ Таким образом, $v+ w =− 2u1 =±2,$ откуда $v = w(= ±1)$ и $u = −2v.$ Наконец, $a− b=− 2(b− c).$

Зная, что $n$ чётное, пусть $n =2k,$ перепишем уравнение $an− bn = −p(b− c)$ с $p= 2$ в виде

k k k k (a + b )(a − b)= −2(b− c)= a− b

Второй множитель слева делится на $a− b,$ поэтому первый множитель $(ak +bk)$ должен быть $±1.$ Тогда ровно одно из чисел $a$ и $b$ должно быть нечётным; однако $a − b= −2(b− c)$ чётно, что влечет противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Начало такое же, как в первом решении. Предполагая, что $a,$ $b$ , $c$ не все равны, а значит, все различны, мы выводим уравнение $(1)$ , то есть $n$ чётное. Положим $n =2k.$

Предположим, что $p$ нечётное. Тогда целое число

an−-bn n−1 n−2 n−1 a− b = a + a b+ ...+ b

которое является множителем в $(1),$ также должно быть нечётным. Эта сумма из $2k$ слагаемых нечётна только если $a$ и $b$ имеют разную чётность. То же верно для пар $b,$ $c$ и $c,$ $a,$ то есть $a,$ $b,$ $c,$ $a$ чередуются по чётности, что невозможно.

Таким образом, $p= 2.$ Исходное уравнение показывает, что $a,$ $b,$ $c$ должны быть одинаковой чётности. Поэтому мы можем разделить $(1)$ на $p3,$ то есть на $23,$ чтобы получить следующее произведение шести целых множителей:

k k k k k k k k k k k k a-+b--⋅ a-− b-⋅ b-+-c-⋅ b-−-c-⋅ c-+-a-⋅ c-− a-= −1 (2) 2 a − b 2 b− c 2 c− a

Каждый из множителей должен быть равен $± 1.$ В частности, $ak+ bk =±2.$ Если $k$ чётное, это равносильно $ak +bk = 2$ и даёт $|a|= |b|= 1,$ откуда $ak − bk = 0,$ что противоречит $(2).$

Пусть $k$ нечётное. Тогда сумма $k k a +b ,$ равная $±2,$ имеет $a+ b$ как множитель. Поскольку $a$ и $b$ одинаковой чётности, это означает, что $a+b =±2;$ и аналогично, $b+ c= ±2,$ $c+ a= ±2.$ В некоторых двух из этих уравнений знаки должны совпадать, следовательно, некоторые два из $a,$ $b,$ $c$ равны, что вновь дает противоречие.

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

Задача 191#91948Максимум баллов за задание: 7

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

Источники: Всеросс., 2006, ЗЭ, 10.2(см. math.ru)

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

Подсказка 1

Необходимо показать, что если для некоторых натуральных чисел x, y верно (x−1)³+x³+(x+1)³=y³, то x кратно 4. Раскройте скобки и приведите подобные слагаемые.

Подсказка 2

Мы получили, что 3(x²+2)=y³. Как можно воспользоваться тем, что y кратно 3?

Подсказка 3

Пусть y=3z. Тогда имеем, x(x²+2)=9z³. Что можно сказать о числе НОД(x, x²+2)?

Подсказка 4

Он равен 1 или 2. Если он равен 1, то что можно сказать про произвольное простое число p, отличное от 3, делящее z?

Подсказка 5

Оно делит ровно одно из чисел x и x²+2, причем входит в него в степени, кратной 3. Тогда x =9u³ и x²+2=v³, либо x =u³, x²+2 =9v³ при некоторых натуральных u,v. Докажите, что каждый из этих случаев невозможен.

Подсказка 6

Осталось разобрать случай НОД(x, x²+2). Почему при этом x кратно 4?

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

Пусть среднее из последовательных чисел равно $x.$ Тогда для некоторого натурального $y$ верно уравнение

3 3 3 3 (x− 1) + x +(x+ 1) =y

что экививалентно

(2 ) 3 3x x + 2 = y

Таким образом, $y$ делится на $3,$ следовательно, $y = 3z$ для некоторого натурального $z.$ Уравнение теперь имеет вид

(2 ) 3 x x +2 = 9z

Очевидно, что $НОД (x,x2+ 2)≤ 2.$ Пусть $НОД (x,x2+ 2)= 1.$ Тогда либо $x =9u3$ и $x2+ 2= v3,$ либо $x =u3,x2+2 =9v3$ при некоторых натуральных $u,v.$ В первом случае $81u6$ $+2 =v3,$ что невозможно, так как куб целого числа при делении на $9$ даёт остаток $0$ или $±1.$ Аналогично второе равенство влечёт, что $u6+2 =9v3,$ что невозможно по тем же причинам. Итак, $НОД (x,x2+ 2) =2,x(x2+2)= 9z3.$ Тогда $x$ (и, следовательно, $z$ ) чётно, поэтому $x(x2+ 2)$ делится на $8.$ Поскольку $x2+ 2$ не делится на $4,$ получаем, что $x$ делится на $4.$

Интенсивы

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

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

Задача 192#115887Максимум баллов за задание: 7

Перед чемпионатом мира по футболу тренер сборной России решил провести три тренировочных матча (каждый продолжительностью $90$ минут) с участием семи игроков, чтобы оценить их навыки. В любой момент времени во время матча на поле находится ровно один из них. Суммарное время (измеряемое в минутах), проведённое на поле каждым из четырёх первых игроков, должно быть кратно $7,$ а для каждого из трех оставшихся — кратно $13.$ Количество замен игроков во время каждого матча не ограничено. Сколько существует возможных распределений игрового времени между игроками при заданных условиях?

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

Пусть $x i$ $(i=1,2,...,7)$ — время $i$ -го игрока на поле. Требуется найти количество наборов натуральных чисел, удовлетворяющих уравнению:

x1+x2+ ...+ x7 = 270

при условиях: $xi ... 7 (i= 1,2,3,4), xj ... 13 (j = 5,6,7)$

Положим:

x1 +x2+ x3+ x4 = 7m, x5+ x6+x7 =13n.

Тогда:

7m + 13n = 270,

где $m, n∈ ℕ,$ $m ≥ 4,$ $n ≥3.$

Найдём все пары натуральных чисел $(m, n),$ удовлетворяющие уравнению:

(m,n)= (33,3), (20,10), (7,17)

Случай 1: $(m,n)= (33,3)$

Здесь $x5 = x6 = x7 = 13.$ Положим $xi =7yi$ ( $i= 1,2,3,4),$ тогда:

y1+ y2+ y3 +y4 = 33

Количество решений по методу шаров и перегородок:

C43−31−1 = C332 = 4960

Случай 2: $(m,n)= (20,10)$

Положим $xi = 7yi$ ( $i= 1,2,3,4$ ) и $xj = 13yj$ ( $j = 5,6,7).$ Тогда:

y1+ y2 +y3+ y4 =20, y5+ y6+ y7 =10

Количество решений по методу шаров и перегородок:

4−1 7−1 C20−1⋅C10− 1 = C319 ⋅C29 = 34884

Случай 3: $(m,n)= (7,17)$

Аналогично:

y1+ y2+ y3 +y4 = 7, y5+ y6 +y7 = 17

Количество решений по методу шаров и перегородок:

C4−1⋅C7−1 = C3⋅C2 = 2400 7−1 17−1 6 16

Общее количество допустимых распределений:

4960+34884+2400= 42244

Ответ:

$42244$

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

Задача 193#81757Максимум баллов за задание: 7

Решите в натуральных числах уравнение

x y z 3 +4 = 5 .

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

Подсказка 1

Попробуйте посмотреть на остатки от деления.

Подсказка 2

У выражения в правой части остаток от деления на 3 должен совпадать с остатком от деления на 3 левой части, каким тогда будет z?

Подсказка 3

z должно быть четным, чтобы остаток от деления на 3 равнялся единице. На какие ещё остатки можно посмотреть?

Подсказка 4

Из-за совпадения остатков по модулю 4, x тоже будет чётным.

Подсказка 5

Преобразуйте равенство 4ʸ = 5ᶻ - 3ˣ.

Подсказка 6

4ʸ = 2²ʸ, а z и x — четные. Какой вывод можно сделать?

Подсказка 7

Получится, что 2²ʸ = (5ᵘ - 3ᵛ)(5ᵘ + 3ᵛ), где z = 2u, x = 2v. Тогда скобки справа являются степенями двойки.

Подсказка 8

Выразите 5ᵘ и 3ᵛ.

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

Правая часть при делении на $3$ должна давать тот же остаток, что и левая, то есть $1.$ Поэтому $z$ чётно. Аналогично, левая часть делится на $4$ с остатком $1,$ поэтому $x$ тоже чётно. Итак,

y z x 2u 2v 2y u v u v 4 = 5 − 3 =5 − 3 ,то есть 2 =(5 − 3)(5 + 3)

Обе скобки справа являются степенями двойки. Пусть $5u− 3v =2k$ и $5u+ 3v = 2l,$ где $k,l≥0$ и $k+ l= 2y.$ Тогда,

u 1 ( k l) v 1 (l k) 5 =2 2 +2 , 3 = 2 2− 2

Отсюда $l>k ≥0.$ Значит, $l 2$ делится на $4.$ Тогда $k 2$ четное, но не делится на $4,$ поскольку $v 3$ нечетное целое число. Таким образом $k k =1, 2 = 2$ и $v l−1 3 = 2 − 1.$ Поскольку $k+l= 1+ l$ четное число, $l− 1$ тоже чётно, $l− 1= 2s.$ Тогда

3v = (2s− 1)(2s+ 1)

– произведение двух чисел, отличающихся на $2$ и являющихся степенями тройки. Следовательно, эти множители это $1$ и $3.$ Значит, $s= 1, l= 3, 2y = 4.$

Ответ:

$(2,2,2)$

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

Задача 194#74247Максимум баллов за задание: 7

Найдите все пары натуральных чисел $m$ и $n,$ для которых $n3+-1- mn − 1$ является целым.

Источники: Туймаада

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

Поделим многочлен $n3+1$ на $mn − 1$ с остатком. Для удобства домножим $n3+1$ на $m3,$ всё равно $m$ и $mn − 1$ взаимно просты. При делении мы получим остаток $3 m + 1.$ То есть дробь $m3+1 mn−1$ также является целой.

Теперь заметим, что число $n3+1+mn−1 n(n2+m ) ---mn−1--= -mn−-1$ является целым. Однако $n$ взаимно просто с $mn − 1,$ следовательно число $n2+m mn−1$ целое. То же самое можно сказать про $2 mmn+−n1.$ Поскольку задача стала инвариантной относительно перестановки $m$ и $n,$ мы можем считать, что $n≥ m.$ Пусть $n= m +x,x≥ 0.$

Из делимости $m2 + n$ на $mn − 1$ следует, что $m2+ n≥ mn − 1,$ то есть $m2 +m + x≥ m2+ mx− 1,$ откуда $m+ 1≥ x(m − 1).$

Если $m =1,$ то $mm2n+−n1 = nn+−11 = 1+ n2−1,$ откуда $n= 2,3.$

Если $m ⁄=1,$ то $mm+1−1 + 1≥ x.$ Ясно, что выражения слева при любом $m > 3$ лежит между $3$ и $2.$ То есть осталось перебрать случаи, когда $m = 2,3$ и $x= 0,1,2.$

Если $m =2$ , то $mm2n+−n1 = n2+n4−1$ . Решая неравенство $n+ 4≥2n − 1$ получаем, что $5≥ n$ . Нам подойдут $n= 1,2,5$ .

Если $m =3$ , то $m2+n= n+9- mn−1 3n−1$ . Снова получаем ограничение $n≤ 5$ . Перебирая, получаем $n = 1,5$ .

Если $x= 0$ , то $m =n$ и $m2+n= n2+n= -n- =1 +-1- mn−1 n2−1 n−1 n−1$ , откуда $n =2= m$ .

Если $x= 1$ , то $m2+n m2+m+1- ---2--- mn−1 = m2+m−1 = 1+ m2+m− 1$ , откуда $m = 1,n =2$ .

Если $x= 2$ , то $2 2 mmn+−n1 = mm2++m2m+2−1$ . Решая неравенство $m2+ m +2≥ m2 +2m − 1$ , получаем, что $m ≤ 3$ . Нам подойдут $m = 1$ .

Не забывая про симметрию относительно переменных, запишем ответ.

Ответ:

$(2,1),(1,2),(3,1),(1,3),(2,2),(5,3),(3,5),(5,2),(2,5)$

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

Задача 195#121179Максимум баллов за задание: 7

Пусть $a$ и $b$ - натуральные числа такие, что $ab+1$ делит $a2+b2$ . Докажите, что $a2+b2 ab+1$ является квадратом целого числа.

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

Решение 1: Выберем целые числа $a,b,k,$ такие что:

2 2 a + b = k(ab+ 1).

Для фиксированного $k$ рассмотрим пару $(a,b)$ с минимальным значением $min(a,b).$ Обозначим $b′ = min(a,b),$ $a′ =max(a,b).$ Тогда квадратное уравнение относительно $a′ :$

′2 ′ ′ ′2 a − kba +b − k= 0.

Если существует другой корень $c′,$ то:

b′c′ ≤a′c′ = b′2− k< b′2 =⇒ c′ < b′.

Если $c′ ∈ ℕ,$ то это противоречит условию минимальности $b′,$ поэтому $c′$ не может быть положительным целым. По формуле Виета:

c′ =kb′− a′,

что делает $c′$ целым. Из неравенства:

(a′+ 1)(c′+1)= b′2+ (b′− 1)k+ 1≥ 1 =⇒ c′ >− 1,

следует $c′ = 0.$ Тогда:

b′2 = k.

Таким образом, $k$ всегда является полным квадратом.

_________________________________________________________________________________________________________________________________________________________________________________

Решение 2: Предположим противное: пусть $a2+b2 c= ab+1$ не является квадратом. Без ограничения общности $a≥ b.$ Выберем пару $(a,b)$ с минимальной суммой $a+ b.$ Рассмотрим квадратное уравнение:

P(a)= a2 − bca+b2− c= 0.

Его корни $r 1$ и $r 2$ удовлетворяют:

2 r1+ r2 =bc и r1r2 = b − c.

Пусть $r1 = a,$ тогда второй корень:

b2−-c r2 = bc− a= a < a, так как c> 0.

Так как $c$ не квадрат, $r2 ⁄= 0.$ Подставляя $r2$ в исходное уравнение:

r2+ b2 c= r22b+1.

Так как $c> 0,$ то $r2b+1 >0 =⇒ r2 > 0.$ Из $r2 <a$ следует $r2+ b< a+ b,$ что противоречит минимальности $a+ b.$ Следовательно, $c$ обязано быть квадратом.

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

Задача 196#84806Максимум баллов за задание: 7

Найдите все пары натуральных $m, n$ , таких, что

НО Д(m, n)=2015!, a НОК (m,n)= 2016!

Замечание.

Пары $(m,n)$ и $(n,m)$ считаются как одна пара.

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

Подсказка 1

Давайте сначала посмотрим на НОД(m, n), что мы тогда можем сказать про сами m, n?

Подсказка 2

Верно, они оба делятся на 2015! А что тогда нам говорит НОК(m, n)?

Подсказка 3

Да, то, что между m, n раскиданы как-то степени простых чисел, произведение которых равно 2016. Остаётся только перебрать все такие варианты, не забывая о том, что ничего общего между m, n, кроме 2015!, нет, и радоваться победе над задачей!

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

Обозначим $d= НОД (m,n) =2015!,$ тогда

m =dk, n =dl,

где $НОД(k,l)= 1$ и $НОК (k,l)= 2016,$ то есть

5 2 kl=2016= 2 ⋅3 ⋅7

Распределяя простые множители между $k$ и $l,$ получаем всевозможные пары.

Ответ:

$(2015!,2016!),(2015!⋅25,2015!⋅32⋅7),(2015!⋅32,2015!⋅25 ⋅7),(2015!⋅7,2015!⋅25⋅32)$

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

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

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

Задача 197#91461Максимум баллов за задание: 7

Найти все решения в натуральных числах уравнения

12⋅x!+2⋅y!= z!

Здесь $n!$ обозначает произведение всех натуральных чисел от 1 до $n$ включительно.

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

Заметим, что $x,y <z,$ так как $12x!< z!$ и $2y!< z!.$

Если $x> y,$ то

(z! ) 2y!= z!− 12x!=x! x! − 12 ≥ x!

Второй множитель целый, так как $z > x.$ Значит,

2y!≥x!≥ (y+ 1)!

Отсюда $y = 1, x!=2$ и $x =2.$ Тогда $z!= 24 +2= 26,$ что невозможно.

Если $y > x,$ то

(z! ) 12x!= z!− 2y!=y! y! − 2 ≥ (z − 2)y!≥ (z− 2)(x+1)!

Второй множитель целый, так как $z > y.$ Значит, $12≥ (z − 2)(x +1).$

Если $x≥ 4,$ то $y ≥ 5,$ $z ≥6$ и $12≥ (z− 2)(x+1)≥ 20$ — получили противоречие.

Если $x= 3,$ то $12≥ 4(z− 2)$ и $5≥ x+ 2= 5.$ Отсюда $z = 5$ и

2y!= z!− 12x!= 48

Откуда $y = 4.$ Значит, подходит тройка $(3;4;5).$

Если $x= 2,$ то $( ) y! z!y! − 2 = 24.$ Так как $z ≥ y+ 1≥ x+ 2= 4,$ то

( ) z!− 2 ≥ z− 2≥2 y!

и поэтому $y!< 24$ и $y = 3.$ Тогда $z!= 12x!+ 2x!= 36,$ что невозможно.

Если $x= 1,$ то $y!( z!− 2)= 12. y!$ Так как $y!< 12$ и $y ≤3.$ Если $y = 2$ , то $z!= 12x!+ 2y!= 16,$ что невозможно. Если $y = 3,$ то

z!= 12x!+ 2y!=24= 4!

Значит, подходит тройка $(1;3;4).$

Если $x= y,$ то $z!= 14x!≥7.$ Раз $.. z!. 7,$ то $z ≥ 7.$ Если $z ≥ x+ 2,$ то $14x!= z!≥z(z− 1)(z− 2)!≥7⋅6y!,$ таким образом, пришли к противоречию. Значит, $z = x+ 1.$ Тогда $z = 14$ и $y =x =13$ и тройка $(13;13;14)$ — решение.

Ответ:

( $x= 1,$ $y = 3,$ $z = 4$ ), ( $x= 13,$ $y = 13,$ $z =14$ ), ( $x =3,$ $y = 4,$ $z = 5$ )

Следующая подтема