Тема Делимость и делители (множители)

Оценки для доказательства делимости

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

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

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

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

Подтемы раздела делимость и делители (множители)

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

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

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

Найдите все тройки (не обязательно различных) натуральных чисел $a,b,c$ такие, что каждое из чисел $a+ bc,$ $b+ ca,$ $c+ab$ является простым делителем числа $2 2 2 (a +1)(b + 1)(c +1).$

Источники: ВСОШ, РЭ, 2024, 10.9 (см. olympiads.mccme.ru)

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

Подсказка 1:

Давайте сначала предположим, что все три числа различны. Может ли одна скобка делиться на два числа из этих трёх?

Подсказка 2:

Нет, ведь произведение любых двух чисел больше любой скобки. Докажите это. Значит, каждая скобка делится на какое-то из этих чисел. Давайте заметим, что условие задачи инвариантно относительно перестановки переменных. Поэтому давайте их упорядочим и рассмотрим наименьшую скобку. В каких случаях наименьшая скобка может делиться на какое-то из чисел?

Подсказка 3:

Пусть теперь какие-то из чисел совпали. В каком случае это возможно и как будет выглядеть условие?

Подсказка 4:

Итак, вы пришли к тому, что среди a, b, c точно есть единица. Пусть это c. Тогда 2(a² + 1)(b² + 1) должно делиться на простое число a + b. Обратите внимание на НОД скобочек.

Подсказка 5:

Итак, вы пришли к тому, что хотя бы два числа из a, b, c должны быть 1. Пусть это b и c. Тогда 4(a² + 1) должно делиться на a + 1. Посмотрите на НОД a² + 1 и a + 1.

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

Видим, что

a= b= c=1

удовлетворяет условию. Далее будет доказано, что других ответов нет.

1) Предположим, что

s= (a2+ 1)(b2+1)(c2+ 1)

делится на $pqr,$ где

p= a+ bc,q = b+ ca,r= c+ab

это следует из условия, если дополнительно предполагать, что $p,q,r$ различны.

Заметим, что один из трех сомножителей $a2+ 1,$ $b2+ 1,$ $c2 +1$ не может делиться на произведение двух из чисел $p,q,r,$ так как он меньше этого произведения. Действительно, рассмотрим, например, $pq.$ Из раскрытия скобок видим, что

pq > c2(ab)+ab≥ c2 +1, pq > b2c+ ab≥ b2+ 1

и аналогично

pq > a2+ 1.

Следовательно, каждый из сомножителей $a2+ 1,$ $b2+ 1,$ $c2+1$ должен делиться ровно на одно из чисел $p,q,r.$ Пусть, для определенности, $a$ — наименьшее из чисел $a,b,c.$ Тогда $a2 ≤ bc$ и $1≤ a,$ поэтому $a2 +1$ может делиться на $p= bc +a$ только в случае $a2 = bc$ и $a = 1,$ т.е в случае

a = b=c =1.

Далее, $2 a ≤ ac$ и $1≤ b,$ поэтому $2 a +1$ может делиться на $q = ac+ b$ только в случае $2 a = ac$ и $b= 1,$ т.е в случае

a = b=c =1.

Аналогично, $a2+ 1$ может делиться на $r= ab+c$ только при

a = b=c =1.

2) Пусть какие-то два из трех чисел $p,q,r$ совпадают, скажем, $p =q.$ Тогда

0= q− p= b+ca− a− bc= (a− b)(c− 1).

Значит, либо $a= b,$ либо $c= 1.$ Первый случай возможен лишь при $a= b=1,$ иначе

p= a+bc= a+ ac= a(a+ c)

— составное число, что дает противоречие. Значит, в любом случае среди $a,b,c$ присутствует единица, скажем, $c= 1.$

Тогда наши данные простые числа — это $p= a+ b,$ $q = a+ b$ и $r= ab+ 1,$ и они должны быть делителями

s= 2(a2+ 1)(b2+1).

Если хотя бы одно из чисел $a,b$ больше 1, то $p> 2$ и на $p= a+b$ обязан делиться хотя бы один из сомножителей $a2+1$ и $b2+ 1.$ А поскольку разность

(a2 +1)− (b2+ 1)=(a− b)(a+ b)

делится на $p= a+ b,$ получаем, что оба числа $a2+1,$ $b2+ 1$ делятся на $p.$ Тогда если $r$ отлично от $p= q,$ то $s$ делится на $pqr,$ что разобрано в случае $1.$

Остается вариант

p= q = r.

Рассуждаем как в предыдущем случае и получаем, что хотя бы два из трех чисел $a,b,c$ обязаны равняться $1.$ Пусть, например,

a =b =1,p= q = r= c+1,s= 4(c2+ 1).

Случай $c=1$ уже был ранее. Если $c> 1,$ то $c+ 1$ — нечетное простое, значит $c2+1$ должно делиться на $c+ 1.$ Отсюда

(c2+ 1)− (c+1)= c(c− 1)

должно делиться на $c+ 1.$ Но это невозможно, так как

0< c− 1< c<c +1

и $c+ 1$ — простое.

Ответ:

$(1,1,1)$

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

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

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

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

Найдите все простые $p,$ для которых числа $p+ 1$ и $p2+1$ являются удвоенными квадратами натуральных чисел.

Источники: СПБГУ-23, 11.2 (см. olympiada.spbu.ru)

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

Подсказка 1

Пусть p+1 = 2x², p²+1 = 2y². Вот давайте вычтем эти два выражения: будет p(p-1) = 2(y-x)(y+x). Про что можно тут подумать, раз слева стоит простой множитель?

Подсказка 2

Про делимости! У нас делится на p либо 2, либо y-x, либо y+x. Если проверить p = 2, то он не подойдет. А может ли y-x делится на p?

Подсказка 3

Можно заметить, что т.к. p+1 = 2x², то x<p, а также y<p и x<y. Тогда y-x тем более < p и он на него не делится. Остается, что y+x делится на p. Используя наши оценки на x и y, поймите, чему равно y+x и решите полученную системку!

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

Пусть

2 2 2 p+1 =2x и p +1 =2y ,

тогда

2 2 p(p− 1)= 2(y − x )= 2(y− x)(y+ x)

Поэтому одно из чисел 2, $y− x$ и $y+ x$ кратно $p.$ Если 2 кратно $p,$ то $p= 2,$ что невозможно, поскольку $p+1 =3$ не является удвоенным квадратом.

Первый способ.

Из неравенства $x < y < p$ следует, что

x+ y = p

Таким образом, имеем систему из двух уравнений

( { x +y = p ( 2(y− x) =p− 1

Решаем её

( ( { x+ y = p { 2x +2y = 2p p+1- ( 2(y − x)= p− 1 ⇒ ( 2y − 2x= p− 1 ⇒ 4x =p+ 1⇒ x = 4

Значит,

( p+1-)2 p +1= 2 4

Следовательно, $p= 7.$

Второй способ.

Если $y− x$ делится на $p,$ то

y +x >y− x≥ p⇒ 2(y− x)(y+ x)≥2p2 > p(p − 1)

Значит, это невозможно. Следовательно, $y+x$ делится на $p.$ Заметим, что

y2= p2+-1> p2−-1= p− 1 x2 p +1 p +1

Тогда если $p ≥11,$ то

y2 > 10x2 ⇒ y > 3x

Значит,

2(y− x)> y+ x≥ p

Стало быть,

2(y− x)(y+ x) >p2 > p(p +1)

Но этого не может быть. Таким образом, осталось рассмотреть случаи $p= 3,p =5$ и $p= 7.$ В первых двух из них $p+ 1$ не является удвоенным квадратом, а $p= 7$ подходит.

Ответ: 7

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

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

Найдите все натуральные числа $a$ , $b$ и $c$ такие, что

(ab−-1)(ac−-1)- bc

является квадратом целого числа.

Источники: 61 УТЮМ

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

Заметим, что $(ab−-1)(ac−-1)-=(a − 1)(a − 1) < a2 bc b c$ . При этом наше выражение не меньше $(a− 1)2$ . Тогда $(a− 1) (a− 1) =(a− 1)2 b c$ . Если $a >1$ , то $b =c= 1$ (иначе левая часть будет строго больше правой). Если же $a =1$ , и $b,c> 1$ , то левая часть снова будет больше правой. Тогда одно из чисел $b$ и $c$ равно 1, а второе может быть любым.

Ответ:

$(1,1,c)$ , $(1,b,1)$ , $(a,1,1)$ для любых натуральных $a$ , $b$ и $c$

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

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

Существует ли $2016$ различных натуральных чисел таких, что никакая сумма нескольких из этих чисел не является полным квадратом.

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

Возьмём простое число $p,$ большее $1+2+ ...+ 2016.$ Рассмотрим числа $p,2p,...,2016p.$ Любая сумма нескольких из этих чисел имеет вид $kp,$ где $k$ меньше $p,$ а потому и не кратно $p.$ То есть любая сумма делится на $p,$ но не делится на $2 p ,$ а значит не является квадратом.

Ответ:

Да

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

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

Определите все пары натуральных чисел $n$ и $m,$ для которых числа $n2+ 4m$ и $m2+ 5n$ являются квадратами.

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

Разберем два случая. Сначала предположим, что $m ≤n.$ Тогда

2 2 2 2 n < n +4m ≤ n +4n <(n+ 2)

Следовательно, $n2+4m = (n +1)2,$ откуда $4m = 2n +1,$ что невозможно из соображений четности.

Теперь предположим, что $n < m.$ Тогда

2 2 2 2 m <m + 5n < m + 6n< (m + 3)

Следовательно, либо $m2 + 5n= (m + 1)2,$ либо $m2+ 5n= (m+ 2)2,$ откуда либо $5n= 2m+ 1,$ либо $5n= 4m+ 4.$ Изучим каждый из этих подслучаев отдельно.

Если $5n= 2m + 1,$ то $4m =10n− 2$ и число $n2 +4m = n2+10n− 2$ является квадратом, тогда

2 2 2 n < n + 10n − 2< n + 10n +25

Это квадрат числа, большего $n$ и меньшего $n+ 5,$ той же четности, что и $n.$ Следовательно, либо

n2 +10n− 2= (n +2)2 = n2+4n +4,

либо

n2+ 10n− 2= (n +4)2 = n2+8n+ 16

В итоге или $n= 1$ и $m = 2,$ или $n= 9$ и $m =22.$

Если же $5n =4m +4,$ то $4m = 5n− 4$ и число $n2+ 4m =n2 +5n− 4$ является квадратом, значит,

n2 < n2+ 5n− 4< n2+6n+ 9

Это квадрат числа, большего $n$ и меньшего $n+ 3.$ Следовательно, либо

n2+ 5n − 4 =n2+ 2n+ 1,

либо

2 2 n + 5n− 4= n +4n+ 4

Первое уравнение имеет нецелый корень, а второе дает $n = 8,$ откуда $m = 9.$

Все полученные ответы подходят.

Ответ:

$(m,n)∈ {(2,1), (22,9), (9,8)}$

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

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

Старательный Роберт выписывает на доску все пары, состоящие из трехзначного и четырехзначного чисел, такие, что каждое из этих чисел делится на их разность. Сколько пар выпишет на доску Роберт?

Источники: Лига открытий - 2018

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

Рассмотрим произвольную пару, выписанную Робертом. Обозначим разность в ней через $x.$ Тогда сами числа равны $nx$ и $(n+1)x$ при некотором натуральном $n.$ При этом число $nx$ должно быть трехзначным, а $(n +1)x$ — четырехзначным. Заметим, что при $x≥ 1000$ такое невозможно. Если же $1 ≤x ≤999,$ то такое $n$ обязательно найдется, и более того, оно единственно: подходит наибольшее $n,$ при котором $nx <1000.$ Число $nx$ в таком случае трехзначно, ведь будь оно двузначно, мы могли бы увеличить $n$ хотя бы на $1.$ При этом число $(n+ 1)x ≥1000,$ но при этом, очевидно, не больше $1998,$ так как $x ≤999.$ Остальные $n,$ очевидно, не подходят: при больших значениях $n$ число $nx$ уже не трехзначно, а при меньших число $(n+ 1)x$ не четырехзначно.

Итак, при любом $1≤ x≤ 999$ существует ровно одна пара с разностью $x,$ подходящая под условие, а при остальных $x$ таких пар нет вообще. Значит, пар $999.$ Все они различны хотя бы потому, что в этих парах разная разность чисел в паре.

Ответ:

$999$

Курсы

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

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

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

Натуральное число $n$ назовём почти квадратом, если $n$ можно представить в виде $n =ab,$ где $a$ и $b$ — натуральные числа, причем $a ≤b≤ 1,01a.$ Докажите, что для бесконечно многих натуральных $m$ среди чисел $m,m + 1,m + 2,...,m + 198$ нет почти квадратов.

Источники: СпбОШ - 2017, задача 11.4(см. www.pdmi.ras.ru)

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

Подсказка 1

Если покрутить конструкцию на конкретных числах, то на уровне общих соображений, то всё становится достаточно понятно: "почти квадраты" лежат очень близко к квадратам (мы можем оценить это с помощью неравенств) и ясно, что с увеличением а у нас будут увеличиваться промежутки, на которых искомых чисел лежать не может. Но как же собрать это в строгое доказательство?

Подсказка 2

Попробуем пойти от противного. Какое утверждение обратно к нашему?

Подсказка 3

Разобьём натуральный ряд на отрезки по 199 чисел. Обратным к искомому будет утверждение о том, что во всех таких отрезках, кроме конечного количества с, будет содержаться "почти квадрат".
Сколько "почти квадратов" будет среди чисел от 1 до n²?

Подсказка 4

Получим оценку с двух сторон: оценка снизу связана с с, а оценку сверху построим из того, что b натурально и лежит в определённом промежутке. Осталось посмотреть, выполнима ли эта оценка при достаточно больших n.

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

Предположим противное. Разобьем натуральный ряд на отрезки по $199$ чисел. Тогда во всех отрезках, кроме, быть может, конечного количества $c,$ имеется почти квадрат. Отсюда следует, что среди чисел от $1$ до $2 n$ количество почти квадратов не меньше чем $n2- 199 − c,$ где $c$ — некоторая константа. С другой стороны, каждый такой почти квадрат имеет вид $ab,$ где $a≤n,$ $[ a-] b∈ a,a + 100 ,$ поэтому их количество не больше чем

n∑ ( ) 2 a100-+1 = n + n(n2+001)< n199 − c a=1

при достаточно большом $n.$ Противоречие.

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

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

Натуральные числа $a$ и $b$ больше $1.$ Известно, что числа $a2+ b$ и $a +b2$ простые. Докажите, что числа $ab+ 1$ и $a+ b$ взаимно простые.

Источники: СпбОШ - 2015, задача 11.3(см. www.pdmi.ras.ru)

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

Подсказка 1

Если утверждение не получается доказать напрямую, то можно пойти от противного: пусть требуемое не выполняется! А что точно есть у чисел, не являющихся взаимно простыми? Какие противоречия стоит искать, используя условие о двух данных простых числах?

Подсказка 2

На что может делиться произведение двух простых чисел? Попробуйте доказать, что если (ab + 1) и (a + b) имеют общий делитель p, то и произведение двух данных простых чисел, тоже делится на p.

Подсказка 3

Внимательная группировка поможет нам представить это произведение в виде суммы двух слагаемых, одно из которых делится на (ab + 1), а второе — на (a + b).

Подсказка 4

Осталось лишь аккуратно сформулировать, почему p не может быть равно какому-либо из данных простых чисел, а является именно его ещё одним делителем.

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

Пусть они не взаимно простые. Тогда $ab+1$ и $a+ b$ имеют общий простой делитель $p.$ Рассмотрим произведение чисел $a2+b$ и $a+ b2$ и преобразуем

2 2 22 3 3 2 2 (a + b)(a+ b)= a b +ab+ a +b = ab(ab+ 1)+ (a+ b)(a − ab+ b).

Тогда произведение тоже делится на $p.$ Но поскольку $p ≤a+ b< min(a2+ b,b2+ a),$ число $p$ является собственным делителем какого-то из чисел $a2+b$ или $a+ b2,$ что противоречит их простоте.

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

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

Дано натуральное число $N.$ На доске написаны числа от $N3$ до $N3 +N.$ Среди них $a$ чисел покрасили в красный цвет, а какие-то $b$ из остальных — в синий. Оказалось, что сумма красных чисел делится на сумму синих. Докажите, что $a$ делится на $b.$

Источники: СпбОШ - 2014, задача 11.3(см. www.pdmi.ras.ru)

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

Подсказка 1

Напишите оценки на сумму красных и сумму синих чисел.

Подсказка 2

Докажите, что Sa < (N+1)N³ и Sb ≥ N³. Поймите, что-нибудь про отношение суммы красных к сумме синих.

Подсказка 3

Вы доказали, что если a не делится на b, то отношение сумм хотя бы N+1. Докажите, что отношение сумм не может быть больше N.

Подсказка 4

Пусть Sa = aN³+a₁ и Sb аналогично, k — отношение сумм, докажите, что |b₁k-a₁| ≥ N³.

Подсказка 5

Теперь соберите всё вместе и найдите противоречие)

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

Если $b =1,$ то $a$ делится на $b.$ Поэтому можно считать, что $b≥ 2,$ тогда $a≤N − 1.$
Пусть сумма $a$ чисел равна $3 sa = aN + a1,$ а сумма $b$ чисел равна $3 3 sb =bN +b1 ≥ N .$ По условию $sa$ делится на $sb.$ Обозначим их отношение через $k.$ покажем, что $k≤ N.$ Действительно,

3 3 3 3 sa = aN +a1 ≤ (N − 1)N + a1 ≤(N − 1)(N + N)< (N + 1)N

(последний переход несложно проверить), и значит, $k= s∕s < (N + 1)N3 ∕N3 = N +1. a b$ Поскольку $s =ks , a b$ получим равенство $aN3 +a = k(bN3 + b), 1 1$ или, что то же самое,

3 (a− kb)N =kb1− a1.

Если $a$ не делится на $b$ , т.е. $a ⁄=kb,$ то $|(a − kb)N3 |≥N3,$ и значит, $|kb1− a1|≥ N3.$ Проверим, что на самом деле выполнено неравенство $kb1− a1 ≥ N3,$ т.е. что число $kb1 − a1$ не может быть слишком крупным отрицательным числом. Действительно, $0 ≤a1 ≤ aN$ и $0 ≤b1 < bN,$ и поэтому $kb1 − a1 ≥ −a1 ≥ −aN ≥ −N2.$ Тогда

3 2 3 N ≤ kb1 − a1 ≤ kb1 < kbN ≤ bN ≤ N .

Здесь как раз применяем, что $k ≤N.$ В итоге, противоречие.

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

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

Даны натуральные числа $a$ и $b$ , причём $a <1000$ . Докажите, что если $a21$ делится на $b10$ , то $a2$ делится на $b.$

Источники: Олимпиада Эйлера, 2010, РЭ, 4 задача(см. old.mccme.ru)

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

Рассмотрим некоторое простое число $p$ , пусть оно входит в число $a$ в степени $k a$ , в число $b$ — в степени $k b$ . Тогда из условия мы имеем, что $21ka ≥10kb$ , а нам требуется показать, что $2ka ≥ kb$ . Пусть это неверно. Тогда $2ka < kb ⇐⇒ 20ka < 10kb ≤21ka$ . Заметим, что первые два числа в неравенстве кратны десяти, поэтому $10kb ≥ 20ka+ 10$ , то есть $21ka ≥ 20ka+ 10 ⇐⇒ ka ≥10$ . Но может ли в число, меньшее $1000$ , какое-то простое число входить в хотя бы десятой степени? Нет, поскольку даже минимальное простое $10 2 > 1024$ этому условию не удовлетворяет. Мы получили противоречие, значит, требуемое доказано.

Ответ:

что и требовалось доказать

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

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

Найдите наименьшее натуральное $n,$ для которого число $nn$ не является делителем числа $2008!$

Источники: ММО-2008, 11.2(см. mmo.mccme.ru)

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

Подсказка 1

Можно ли ограничить n снизу, пользуясь определённой его степенью?

Подсказка 2

Заметим, что если n² ≤ 2008, то 2008! делится на nⁿ. Попробуйте оценить число 2008 через квадраты.

Подсказка 3

44² < 2008 < 45², какие n тогда можно рассматривать?

Подсказка 4

Нам будет достаточно проверять делимость 2008! на nⁿ при n > 45.

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

Если $n2 ≤2008,$ то $2008!$ делится на $nn$ (так как числа $n,2n,...,(n − 1)n$ и $n2$ содержатся среди чисел $1,2,...,2007,2008$ ). Так как $2 2 44 < 2008 <45 ,$ то достаточно проверить делимость $2008!$ на $n n$ при $n >45.$

Ясно, что $2008!$ делится на $45 45 90 45 =5 ⋅3 ,$ так как среди чисел $1,2,...,2007,2008$ заведомо найдётся $45$ чисел, кратных $5,$ и $90$ чисел, кратных $3$ ( $5⋅45= 22< 2008$ и $3⋅90= 270<2008$ ).

$2008!$ делится на $46 46 46 46 = 2 23 ,$ так как среди чисел $1,2,...,2007,2008$ заведомо найдётся $46$ чётных чисел и $46$ чисел, кратных $23$ ( $23⋅46= 1058< 2008$ ).

$2008!$ не делится на $47 47 ,$ так как число $47$ простое, и поэтому среди чисел $1,2,...,2007,2008$ есть лишь $42$ числа, кратных $47$ ( $47⋅42 =1974< 2008 <2021= 43 ⋅47$ ).

Ответ:

$47$

Интенсивы

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

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

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

К натуральному числу $a> 1$ приписали это же число и получили число $b,$ кратное $a2.$ Найдите все возможные значения числа $-b a2.$

Источники: Турнир городов - 2004, весенний тур, базовый вариант, 11.2

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

Подсказка 1

Когда в задаче идет речь о «приписывании» цифр, полезно оценить исходное число через степени десятки.

Подсказка 2

b/a² =(10ⁿ+1)a/a²=(10ⁿ+1)/a. Зная, что а - n-значно, как можно оценить дробь (10ⁿ+1)/a?

Подсказка 3

Подумайте, на что может делиться 10ⁿ+1.

Подсказка 4

10ⁿ+1 нечётно, сумма цифр числа равна 2, и на 5 оно тоже не делится, что осталось?

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

Если число $a$ $n$ -значно, то $b =(10n+1)a.$ Отсюда

-b (10n+-1)a 10n+-1 a2 = a2 = a

Ясно, что $n−1 a ⁄=10$ (в таком случае $b$ не кратно $2 a$ ), значит,

10n+ 1 1< ---a--< 10

Число $10n +1$ (а тем более, частное) не делится ни на $2,$ ни на $3$ (сумма цифр равна $2$ ), ни на $5,$ поэтому единственное возможное частное – $7.$ Такое частное можно получить например, при $3 n = 3, a= 143= 107+1.$

Ответ:

$7$

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

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

Найдите все пары целых чисел $(x,y),$ для которых числа $x3 +y$ и $x+ y3$ делятся на $x2+ y2.$

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

Подсказка 1:

Попробуйте обозначить НОД x и y через d и что-то про него понять.

Подсказка 2:

Итак, у вас должно было получиться, что x и y взаимно просты. Теперь давайте осознаем, что любая линейная комбинация чисел x³ + y и x² + y² или x + y³ и x² + y² будет делиться на x² + y². Попробуйте взять какую-нибудь удобным комбинацию, которая даст интересную делимость.

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

Пусть $d =$ НОД $(x,y).$ Тогда $x= du, y = dv,$ где $u$ и $v$ взаимно просты. По условию $d3u3+ dv$ делится на $d2,$ поэтому $v$ делится на $d.$ Аналогично $u$ делится на $d.$ Значит, $d= 1,$ то есть $x$ и $y$ взаимно просты. Тогда и число $2 2 x + y$ взаимно просто с $y.$ Число $( 2 2) (3 ) x x +y − x +y = y(xy − 1)$ делится на $2 2 x + y.$ Поскольку $2 2 x + y$ и $y$ взаимно просты, то $xy− 1$ делится на $2 2 x + y .$ Но это возможно только при $|xy|≤ 1.$ Действительно, в противном случае $2 2 0 <|xy− 1|< 2|xy|≤x + y .$ Непосредственная проверка всех оставшихся вариантов $(x,y =0,±1)$ дает восемь решений $(±1,±1),(0,±1),(±1,0).$

Ответ:

$(1,1), (1,0), (1,−1), (0,1), (0,−1), (−1,1), (−1,0), (−1,−1)$

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

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

Даны натуральные числа $a$ и $b$ такие, что число $a+-1+ b+-1 b a$ является целым. Докажите, что наибольший общий делитель чисел $a$ и $b$ не превосходит числа $√ ---- a+b.$

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

Подсказка 1:

Чтобы с суммой дробей было проще работать, её однозначно стоит преобразовать в дробь.

Подсказка 2:

Пусть НОД a и b равен d. В какой степени он входит в знаменатель дроби? Что можно сказать про числитель или его отдельные слагаемые?

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

Имеем:

a+-1 b+-1 a2+-b2+a-+b b + a = ab

Пусть $d$ — наибольший общий делитель чисел $a$ и $b.$ Так как $ab$ делится на $2 d ,$ то $2 2 a + b+ a+ b$ делится на $2 d.$ Число $2 2 a +b$ также делится на $2 d .$ Поэтому $a+b$ делится на $2 d$ и $√---- a +b≥ d.$