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

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

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

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

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

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

Подтемы раздела уравнения в целых числах

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

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

Задача 1#33372

Найдите количество троек натуральных чисел $(a;b;c)$ , удовлетворяющих системе уравнений

{ HO Д(a;b;c)=6, HO К(a;b;c)=215⋅316.

Источники: Физтех - 2021, 11.4 (см. olymp.mipt.ru)

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

Подсказка 1

Из второго условия системы мы понимаем, что единственными простыми делителями чисел a, b, c могут быть лишь 2 и 3. Тогда можем представить эти числа как произведение степеней 3 и 2(a=2^α₁ * 3^α₂, b=2^β₁ * 3^β₂, c=2^γ₁ * 3^γ₂). Как тогда можно перезаписать условие системы через новые переменные?

Подсказка 2

С новыми переменными мы получаем, что max(α₁, β₁, γ₁) = 15, min(α₁, β₁, γ₁) = 1, max(α₂, β₂, γ₂) = 16, min(α₂, β₂, γ₂) = 1. Отлично! Теперь можно отдельно рассмотреть условия на α₁, β₁, γ₁ и условия на α₂, β₂, γ₂. Затем найти кол-во подходящих троек в каждом случае и, перемножив, получить ответ.

Подсказка 3

Для условий на α₁, β₁, γ₁, имеем, что какое-то из чисел равно 15, второе равно 1, а третье является любым целым числом от 1 до 15 включительно. Осталось только перебрать варианты наборов чисел и сложить кол-во случаев в них. Аналогично для α₂, β₂, γ₂.

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

Пусть $a =2α1 ⋅3α2,b= 2β1 ⋅3β2,c= 2γ1 ⋅3γ2$ (никаких других простых множителей числа $a$ , $b,c$ содержать не могут - иначе нарушается второе условие системы). Отсюда

max(α ;β ;γ) max(α ;β ;γ ) min(α ;β ;γ ) min(α ;β ;γ ) HOK (a;b;c)= 2 1 1 1⋅3 2 2 2, HOД(a;b;c)= 2 1 1 1 ⋅3 2 2 2.

Учитывая данную в условии систему, получаем соотношения

{ max(α1;β1;γ1)= 15, { max (α2;β2;γ2)= 16, min(α1;β1;γ1)= 1 и min(α2;β2;γ2)=1. (1)

Рассмотрим первую систему $(1)$ . Возможны следующие наборы чисел $(α1;β1;γ1)$ :

$(1;1;15)− 3$ набора (за счёт различных перестановок этих чисел);

$(1;15;15)$ — также три набора;

$(1;k;15)$ , где $2 ≤k ≤14−$ есть $13$ различных значений $k$ и для каждого из них $6$ перестановок — всего $78$ вариантов.

Итак, есть $3+ 3+6 ⋅13= 84$ способа выбрать тройку чисел $(α1;β1;γ1)$ . Аналогично устанавливаем, что для выбора $(α2;β2;γ2)$ есть $3+ 3+ 6⋅14= 90$ ( $2 ≤k ≤15$ — $14$ значений) способов. И поскольку один выбор осуществляется независимо от другого, то общее количество способов равно $84⋅90 =7560$ .

Ответ:

$7560$

Критерии оценки

Найдено количество троек для степеней одного из простых чисел только в одном случае – 2 балла.

Получено одно или оба соотношения вида {︃ max (𝛼1; 𝛽1; 𝛾1) = 𝑘, min (𝛼1; 𝛽1; 𝛾1) = 1 и {︃ max (𝛼2; 𝛽2; 𝛾2) = 𝑚, min (𝛼2; 𝛽2; 𝛾2) = 1. и других продвижений нет – 1 балл за задачу (этот балл не суммируется с указанным выше).

Неарифметическая (комбинаторная) ошибка (вместо правила произведения применено правило суммы, некоторые случаи посчитаны дважды или пропущены и т.п.) – не более 1 балла за задачу.

Неверно решена «числовая часть» (из условия сделаны неверные выводы, например, утверждается, что одно из чисел должно равняться произведению 𝑝^𝑚𝑎𝑥 𝑞^𝑚𝑎𝑥 или 𝑝𝑞; используются неверные утверждения, например, НОД(𝑎, 𝑏, 𝑐) НОК(𝑎, 𝑏, 𝑐) = 𝑎𝑏𝑐) – 0 баллов за задачу.

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

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

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

Задача 2#72732

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

5mn-- НОК (m,n)− 2НО Д(m, n)= 7

В качестве ответа введите все возможные значения $m$ через пробел в порядке возрастания.

Источники: САММАТ - 2021, 10

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

Подсказка 1

Вспомним равенство mn = НОД(m,n) * НОК(m,n). Тогда пусть НОК(m,n) = x, НОД(m,n) = y. Теперь наше уравнение свелось к уравнению относительно x и y в целых числах. Какие решения оно может иметь?

Подсказка 2

После преобразований у нас получится уравнение 7x - 14y - 5xy = 0. Попробуйте разложить его на множители так, чтобы в правой части осталось целое число!

Подсказка 3

Уравнение можно записать в виде x(7 - 5y) - 14y = 0. Теперь у первого слагаемого есть скобочка. Попробуйте такую же получить и у второго!

Подсказка 4

Если умножить уравнение на 5, то получится 5x(7 - 5y) + 14 * (-5y) = 0. Теперь добавим с обеих сторон 14 * 7. Получается (7-5y)(5x+14) = 14*7. Какие решения имеет это уравнение?

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

Как известно,

HOK (m,n)⋅НОД (m,n)= mn

Для удобства введем обозначения:

HOK (m,n) =x,НОД (m,n)= y

Так как $m,n ∈ℕ$ , то $x,y ∈ ℕ.$

Исходное уравнение примет вид:

(x− 2y)= 5xy⇒ 7(x− 2y) =5xy ⇒ 7x− 14y− 5xy =0 7

14 x(7 − 5y)− 14y = 0⇒ x(7− 5y)− 5 ⋅5y = 0

x(7 − 5y)− 14-⋅(5y− 7+ 7)=0 5

x(7− 5y)− 14⋅(5y − 7)− 14⋅7= 0 5 5

( 14) 14⋅7 (7 − 5y) x+ 5 = 5

(7− 5y)(5x+14)= 14⋅7

$x,y ∈ ℕ,$ следовательно, $5x+14 ∈ℕ$ и, значит, $7− 5y ∈ ℕ.$ Поскольку $y ∈ℕ,$ то это возможно лишь при $y =1.$

В таком случае,

2⋅(5x+ 14)= 14⋅7⇒ 5x+ 14= 49 ⇒ 5x= 35 ⇒ x= 7

Следовательно, $HOK (m,n)= 7,HOД(m,n)= 1.$ Что означает, что числа взаимно простые и возможны две ситуации: $m= 1,n= 7$ или $m = 7,n = 1.$

Ответ: 1 7

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

Задача 3#94776

Найдите количество пар натуральных чисел $(a;b)$ , каждое из которых меньше миллиона, удовлетворяющих равенству

Н ОК (a,b+ 1)= HOK (b,a+ 3)

Источники: Бельчонок - 2021, 11.4 (см. dovuz.sfu-kras.ru)

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

Подсказка 1

Тут главное — вспомнить, что такое НОК! Это наименьшее общее кратное чисел, НОК(x, y) ⋮ x, ⋮ y. А нам хотелось бы наоборот понять, какими свойствами обладают числа a и b, можем ли записать какое-то выражение с их помощью, которое будет делиться на НОКи в левой и правой части?

Подсказка 2

Ага, можем записать произведение a(b+1) к примеру! Оно будет делиться на НОК(a, b+1), а на что ещё? Аналогично можно составить ещё одно произведение из правой части.

Подсказка 3

Выходит, что a(b + 1) ⋮ b, ⋮ (a+3), в каких случаях такое может быть? И ещё выходит, что b(a+3) ⋮ a, ⋮ (b+1). Разберите все возможные варианты и поймите, какими свойствами обладают a и b!

Подсказка 4

После того как определили, как а выражается через b, можно подставить это в изначальное равенство на НОКи и подумать, когда оно возможно. Так там будут встречаться тройки, можно подумать про этот модуль. И найти количество подходящих пар!

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

Заметим, что $b(a+ 3)$ делится на НОК $(b,a+ 3)$ , который равен НОК $(a,b+ 1)$ и в свою очередь делится на $a$ . Также $a(b+ 1)$ делится на НОК $(a,b+ 1)=HOK (b,a +3)$ , а последнее выражение делится на $b$ , поэтому $a$ делится на $b$ . Значит, либо $a= b$ , либо $a=$ $3b$ . В первом случае получаем

a(a+ 1)=HOK (a,a+ 3)

следовательно, $a(a+1)= (a+ 3)(a− 2)+ 6$ делится на $a+ 3$ . Таким образом, $a+ 3$ есть делитель 6 , откуда $a= 3,b= 3$ — увы, эта пара чисел не удовлетворяет уравнению. Во втором случае, получаем

НО К (3b,b+ 1)=HOK (b,3(b+1))

Если $b$ кратно 3 , то левая часть делится на большую степень тройки, чем правая. Если $b+1$ кратно 3, то правая часть делится на большую степень тройки, чем левая. Если же $b$ дает при делении на 3 остаток 1 , то обе части равны $3a(a+1)$ . Итак, требуется найти количество натуральных чисел $b= 3x+ 1$ , таких что $3b< 1000000$ . Их ровно 111111.

Ответ: 111111

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

Задача 4#72734

Найти все пары натуральных чисел $x$ и $y$ таких, что их наименьшее общее кратное равно $1+ 2x+3y.$

В качестве ответа введите все возможные значения $x$ через пробел в порядке возрастания.

Источники: Всесиб-2019, отбор

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

Подсказка 1

Из условия следует, что 1+3y делится на x, а 1+2x делится на y. Кажется, что это может дать нам неплохие оценки на x и y...

Подсказка 2

Пускай для начала 1<x≤y. Из делимости 1+3y на x следует, что 1+2x=ky. Если k>2, то x>y. Тогда k=1 или k=2. Какой из случаев не реализуется?

Подсказка 3

При k=2, 1+2x должно делится на 2, что неверно. Тогда 1+2x=y ⇒ 4+6x делится на x. Следовательно, x надо искать среди делителей 4. Пускай теперь x>y>1. Что мы можем сказать про k, где 1+3y=kx?

Подсказка 4

Верно, k<4! При этом k не может равняться 3. Если k=2, то 1+3y=2x ⇒ y=2t+1, x=3t+2. При этом 1+2x=6t+5 должно делится на 2t+1. Посмотрите на НОД(6t+5, 2t+1) и разберитесь со случаем k=1!

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

Пусть сначала $x≤ y$ Заметим, что $y$ не может делиться на $x,$ иначе наименьшее общее кратное $x$ и $y$ равно $y,$ а это меньше $1+ 2x+ 3y.$ В частности, $x> 1.$

Далее, наименьшее общее кратное $x$ и $y$ делится на $x$ и $y,$ поэтому $1+ 2x +3y$ делится на $x$ и $y,$ а значит $1+2x$ делится на $y$ и $1+3y$ делится на $x.$ Из делимости $1+ 2x$ на $y$ следует $1 +2x= ky ≥ y,$ что вместе с предположением $x≤ y$ влечёт $k =1,y = 2x+ 1.$ Тогда из делимости $1+ 3y =6x+ 4$ на $x$ и $x> 1$ следуют делимость 4 на $x$ и возможности $x= 2,4.$ Проверка показывает, что решением в этом случае является $x =4,y = 9.$

Теперь рассмотрим случай $x≥ y > 1,$ из делимости $1 +3y ≤ 1+ 3(x− 1)= 3x − 2$ на $x$ следует $1+3y =x$ или $1+ 3y = 2x.$ Если $1+ 3y = x,$ то $1+ 2x= 6y +3$ делится на $y,$ тогда $3$ делится на $y$ и $x= 10,y =3$ является решением задачи.

Если $1+3y =2x,$ то $y$ нечётно, $y =2k +1,k> 0,x =3k+ 2.$ Тогда $1+ 2x =6k +5$ должно делиться на $y = 2k+ 1,$ значит $6k+ 5− 3(2k+ 1)=2$ делится на $y =2k +1≥ 3,$ что невозможно.

Ответ: 4 10

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

Задача 5#79772

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

n = x+ y+(x,y)+ [x,y]

для некоторых натуральных чисел $x$ и $y.$

Здесь $(x,y)$ и $[x,y]$ обозначают наибольший общий делитель и наименьшее общее кратное чисел $x$ и $y$ соответственно.

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

Подсказка 1

Нам хочется что-то понять про число n, поэтому разумно будет попытаться разложить правую часть на множители. С изначальным условием не очень удобно совершать тождественные преобразования. Давайте обозначим НОД(x, y)=d, тогда x=ad, y=bd и как раскладывается правая часть?

Подсказка 2

Верно, n=d(a+1)(b+1)! Как мы понимаем, нам подходят любые d, a и b, удовлетворяющие условию НОД(a, b)=1. При каком b это условие всегда выполнено?

Подсказка 3

Верно, при b=1! Это означает, что любое n вида 2d(a+1) нам подходит. Поэтому появляется предположение о том, что любое четное число, большое 2, нам подойдет. Осталось доказать, что если n раскладывается, то оно обязательно должно быть четным...

Подсказка 4

Так как НОД(a, b)=1, то одновременно a и b делится на 2 не могут. Используйте это и завершите решение!

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

Первое решение.

Если оба числа $x$ и $y$ одной четности, то все четыре слагаемых $x, y, (x, y)$ и $[x, y]$ имеют ту же четность и их сумма четна. Если они имеют разную четность, то $(x, y)$ нечетно, а $[x, y]$ четно, потому в сумме будет два четных и два нечетных числа и она снова будет четна. Каждое ее слагаемое не меньше одного, поэтому вся сумма не меньше $4.$ Следовательно, ответом задачи может быть только четное число больше двух.

С другой стороны, для произвольного четного $n> 2$ положив $n x= 1, y = 2 − 1,$ получим $(x,y)= x= 1$ и $n [x, y]= y = 2 − 1,$ откуда $x +y+ (x, y)+[x, y]=n$ — представляется в требуемом в условии виде.

Второе решение.

Если обозначить $(x, y)= d,$ то

x =x1d, y =y1d, [x, y]= x1y1d,

где $x1, y1$ взаимно просты, значит, одно из них обязательно нечетно. Тогда

n= x+ y+(x, y)+ [x, y]= d(1+ x1)(1+ y1),

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

Ответ: Все чётные числа, большие двух

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

Задача 6#72731

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

( 3 ) ( 3 ) 3 Н ОД n − 2,n +2 + НО К n− 2,n + 2 = n +n

Введите все возможные варианты в порядке возрастания через пробел.

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

Подсказка 1

Вспомним равенство НОД(a,b) * НОК(a,b) = ab, которое верно для любых целых чисел. Какие решения может иметь система НОД(a,b) + НОК(a,b) = a + b, НОД(a,b) * НОК(a,b) = ab?

Подсказка 2

Верно! НОД(a,b) = a и НОК(a,b) = b или НОД(a,b) = b и НОК(a,b) = a. Каким эквивалентным условием можно заменить эти условия?

Подсказка 3

НОД(a,b) = a, НОК(a,b) = b <=> b делится на a. Ясно, что может быть реализован только вариант b = n^3 + 2, a = n - 2. При каком условии b делится нацело на a?

Подсказка 4

Верно! Тогда и только тогда, когда неполное частное (n^3+2)/(n-2) является целым числом. Найдите все такие n!

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

Обозначим $a= n− 2;b =n3+ 2.$ Тогда уравнение запишется в виде НОД $(a,b)+$ НОК $(a,b)= a+ b.$ Напишем еще одно соотношение, верное для любых целых $\text{[math]}$ и $b.$ Получим систему

{ НОД (a,b)+НО К(a,b)= a+b НОД (a,b)⋅ НОК (a,b)= a⋅b

Очевидно, что решением этой системы может быть только

{ НОД (a,b)= a { НО Д (a,b)= b НОК (a,b)= b или НО К (a,b)= a

Поскольку НОК всегда не меньше НОДа, второй случай невозможен. Остается ${ НОД (a,b)= a НОК (a,b)= b$ , что равносильно тому, что $b$ делится на $a.$

n3+ 2 10 n-− 2-= n2+ 2n +4+ n-− 2

Из этого равенства видно, что $n3+ 2$ будет делиться на $n− 2$ тогда и только тогда, когда $n− 2$ является делителем $10.$

n− 2= 1⇒ n= 3;n− 2= 2⇒ n= 4;

n− 2= 5⇒ n =7;n− 2= 10⇒ n= 12.

Ответ: 3 4 7 12

Курсы

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

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

Задача 7#84806

Найдите все пары натуральных $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)$

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

Задача 8#49156

Для каких натуральных $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}$

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

Задача 9#49161

Найдите натуральные числа $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$ , поэтому остаётся перебрать два случая