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

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

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

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

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

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

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

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

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

Задача 1#33372

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

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

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

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

Пусть $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

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

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

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)

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

Заметим, что $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, отбор

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

Пусть сначала $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$ соответственно.

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

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

Если оба числа $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

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

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

Обозначим $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#49156

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

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

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

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

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

Заметим, что $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}$

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

Задача 8#49161

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

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

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

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

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