Тема 19. Задачи на теорию чисел

19.06 НОК, НОД и взаимная простота чисел

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

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

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

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

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

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

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

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

Коля получает пятёрку через каждые 6 дней, Вася получает пятёрку через каждые 9 дней, а Андрей получает пятёрку через каждые 15 дней. Те дни, когда они втроём получают по пятёрке, они называют днями икс. Через сколько дней наступит следующий день икс, если известно, что сегодня тоже день икс?

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

Количество дней до следующего дня икс равно

Н ОК(6;9;15)= НО К(2⋅3; 3⋅3; 3⋅5)= 2⋅3 ⋅3⋅5= 90.

Ответ: 90

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

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

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

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

Известно, что $a, b∈ ℕ$ взаимно просты и дробь $3a-+5b 5a +3b$ сократима на число $d ∈ℕ,$ $d⁄= 1.$ Найдите наибольшее возможное $d.$

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

Так как требуется найти наибольшее возможное $d,$ то

d= НО Д(3a + 5b;5a+ 3b).

Число $5(3a+ 5b)− 3(5a+ 3b)= 16b$ делится на $d.$ Число $5(5a+ 3b)− 3(3a+ 5b)= 16a$ делится на $d.$ Так как $a$ и $b$ взаимно просты, то 16 делится на $d.$

Проверим, может ли быть $d= 16.$ Число $3a+ 5b− (5a+ 3b)= 2(b − a)$ делится на $d.$ Если $d = 16,$ то $(b− a)$ делится на 8.

Возьмём, например, $b= 9,$ $a= 1,$ тогда

3a-+5b = 48= 16-⋅3 , 5a +3b 32 16 ⋅2

то есть $d =16$ — подходит.

Ответ: 16

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

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

Известно, что $a,b∈ ℕ,$ при этом $ab= 2016.$ Какое наибольшее значение может принимать $НО Д(a;b)?$

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

Пусть $d= НО Д(a;b),$ тогда оба числа $a$ и $b$ делятся на $d,$ следовательно, $ab$ делится на $d2.$

Разложим число 2016 на простые множители:

5 2 2016 =2 ⋅3 ⋅7

Рассмотрим наибольший полный квадрат, на который может делиться 2016:

4 2 2 2 ⋅3 =12 ⇒ d ≤12

Проверим, может ли быть так, что $d= 12.$ Пусть $d= 12,$ тогда для некоторых натуральных $m$ и $n$ имеем:

a= 12m, b= 12n 144mn =2016 ⇒ mn = 14

Положим $m = 2,$ $n = 7,$ тогда получим

a= 24, b= 84, ab =2016 НО Д(a;b)= НО Д(24;84)= 12

Таким образом, наибольшее возможное значение $Н ОД(a;b)$ равно 12.

Ответ: 12

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

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

Найдите $НОД (34,1717).$

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

НО Д(34,1717)= НО Д(2⋅17,101⋅17)= 17,

так как $НОД (2,101)= 1.$

Ответ: 17

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

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

Докажите, что дробь $18n-+1, 45n +1$ где $n∈ ℤ,$ несократима.

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

Пусть

Н ОД(18n+ 1,45n + 1)= a.

Тогда по определению наибольшего общего делителя $(18n + 1)...a$ и $. (45n+ 1)..a,$ но тогда

.. (5(18n+ 1)− 2(45n +1)).a.

Так как

5(18n + 1) − 2(45n+ 1)= 90n + 5− 90n− 2= 3,

то $3 ...a,$ значит, $a$ равно либо 1, либо 3.

Но так как $18n +1$ не делится на 3, то $a =1,$ следовательно,

Н ОД(18n+ 1,45n + 1)= 1.

Таким образом, дробь $18n+-1 45n+ 1$ — несократима.

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

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

Найдите $НОД (60,539).$

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

( 2 2 ) НО Д(60,539)= НО Д 2 ⋅3⋅5,7 ⋅11 = 1,

так как в разложении чисел 60 и 539 нет одинаковых простых множителей.

Ответ: 1

Курсы

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

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

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

а) Найдите $НО Д(1598,987)$ , выполнив явные шаги алгоритма Евклида.

б) Найдите все целые решения уравнения $1598x+ 987y = 1.$

Указание: если два целых числа равны, то они делятся на одни и те же числа.

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

а) Алгоритм Евклида заключается в последовательном делении с остатком

1.: Делим 1598 на 987 с остатком: $1558= 987⋅1+ 611$
Получили, что неполное частное равно 1, а остаток равен 611.
2.: Делим 987 на 611 с остатком: $987= 611⋅1+ 376$
Получили, что неполное частное равно 1, а остаток равен 376.
3.: Делим 611 на 376 с остатком: $611= 376⋅1+ 235$
Получили, что неполное частное равно 1, а остаток равен 235.
4.: Делим 376 на 235 с остатком: $376= 235⋅1+ 141$
Получили, что неполное частное равно 1, а остаток равен 141.
5.: Делим 235 на 141 с остатком: $235= 141⋅1+ 94$
Получили, что неполное частное равно 1, а остаток равен 94.
6.: Делим 141 на 94 с остатком: $141= 94⋅1+ 47$
Получили, что неполное частное равно 1, а остаток равен 47.
7.: Делим 94 на 47 с остатком: $94= 47⋅2+ 0$
Получили, что частное равно 2, а остаток равен 0.

Так как остаток равен 0, то НОД — это последний ненулевой остаток, то есть 47.

НО Д(1598,987)= 47

б) Найдем все целые решения уравнения $1598x+ 987y = 1.$ Заметим, что если $x$ и $y$ — целые, то левая часть уравнения будет целой. Значит, имеем равенство двух целых чисел.

Согласно указанию, если два целых числа равны, то они делятся на одни и те же числа. Левая часть уравнения $1598x+ 987y$ делится на 47, так как по пункту а) $Н ОД(1598,987)= 47,$ но правая часть уравнения на 47 не делится.

Значит, два целых числа $1598x+ 987y$ и 1 не равны ни при каких целых $x$ и $y,$ то есть уравнение не имеет решений.

Ответ:

а) 47

б) Нет решений

Интенсивы

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