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

Делимость и делители (множители) → .06 Алгоритм Евклида

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

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

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

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

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

Разделы подтемы Делимость и делители (множители)

Условия про НОД и НОК

Разложение на множители, основная теорема арифметики

Количество, сумма, произведение делителей

Степени вхождения простых

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

Алгоритм Евклида

Теоретико-числовые свойства биномиальных коэффициентов

Теоретико-числовые свойства чисел Фибоначчи

Целые гауссовы числа

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

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

Задача 1#96443

На какие натуральные числа может быть сократима дробь $13n+-8? 8n +5$

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

Дробь можно сократить на НОД числителя и знаменателя, если он больше $1.$ Попробуем найти НОД числителя и знаменателя. Для этого применим алгоритм Евклида

(13n+ 8,8n+ 5)=(5n+ 3,8n +5)= (5n +3,3n +2)=

= (2n+ 1,3n +2)= (2n +1,n+ 1)=(n,n+ 1) =1

Таким образом, наибольший общий делитель числителя и знаменателя равен $1,$ поэтому дробь несократима.

Ответ:

Дробь несократима

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

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

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

Задача 2#96444

Колесо длины $19,$ в обод которого вбит гвоздь, достаточно долго едет по колесу длины $102.$ На сколько частей поделят большее колесо отметины от гвоздя?

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

Количество частей равно количеству отметин. Вычислим число отметин. Выберем первую точку на колесе длины $102,$ на которой появилась отметина, и обозначим ее $0.$ От этой точки против часовой стрелки отметим последовательно точки $1,2,...,101$ так, чтобы расстояние по окружности между соседними точками было равно $1.$ Таким образом, мы разбили колесо длины $102$ на $102$ равные части. Заметим, что отметины гвоздя могут появляться только в отмеченных точках, так как первая отметина появилась в точке $0$ и длина у меньшего колеса целая. Каждая точка, в которой появится отметина гвоздя, может быть вычислена, как остаток от деления $19x$ на $102,$ где $x$ — количество полных оборотов, совершенных от первого попадания в точку $0$ колесом длины $19$ к данному моменту. Таким образом, из деления с остатком получаем $19x =102y+ r,$ где $r$ — остаток.

Вопрос задачи сведен к вопросу о том, какие числа $0 ≤r≤ 101$ могут быть представлены в виде $19x− 102y.$ Очевидно, что $19$ и $102$ взаимно просты, поэтому имеется пара $(x0,y0)$ такая, что $19x0− 102y0 = 1.$ Умножим это равенство на $0 ≤r≤ 101$ и получим $19(rx0)− 102(ry0)= r.$ Следовательно, все числа от $0$ до $101$ рано или поздно получатся, значит, отметины будут во всех отмеченных точках, и количество частей, на которые разделится колесо, равно $102.$

Ответ:

$102$

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

Задача 3#96445

Найдите с помощью алгоритма Евклида линейное представление НОД чисел $37$ и $11.$

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

Обозначим для удобства $a =37,b=11.$ Проделаем алгоритм Евклида, дополнительно указывая представления чисел в виде линейных комбинаций чисел $a,b$

(a,b)=(37,11)= (37− 3⋅11,11)= (4,11) =(a− 3b,b)

(a − 3b,b)= (4,11)= (4,3)=(a− 3b,b− 2a+6b)= (a− 3b,7b− 2a)

(a− 3b,7b − 2a)= (4,3)=(1,3)= (a− 3b− 7b+ 2a,7b− 2a)= (3a − 10b,7b− 2a)

Очевидно, что $37$ и $11$ взаимно просты, поэтому мы уже нашли линейное представление НОД — это $3a− 10b =3⋅37− 10⋅11.$

Ответ:

$3⋅37− 10⋅11$

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

Задача 4#96448

Какое наибольшее значение может иметь наибольший общий делитель чисел $n2+ 20$ и $(n+ 1)2+ 20$ для натуральных $n?$

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

В задаче будем искать наибольший положительный НОД, но будем считать, что числа в алгоритме Евклида могут быть отрицательными. Тогда по алгоритму Евклида

2 2 2 2 ((n+ 1)+ 20,n + 20)=(2n+ 1,n + 20)= (2n+ 1,− n − n +20)= (2n +1,(n +5)(n − 4))

Заметим, что $2n+ 1= (n +5)+ (n − 4).$ Докажем небольшую лемму.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть $p$ — простое число. Тогда $p|ab$ и $p|(a+ b)$ $⇔$ $p|a$ и $p|b.$

_________________________________________________________________________________________________________________________________________________________________________________

Таким образом, если числа $2n+ 1$ и $(n+ 5)(n− 4)$ имеют общий делитель $d >1$ то все простые числа $p|d$ являются делителями чисел $n+ 5$ и $n− 4.$ Поскольку $(n+ 5,n− 4)= (9,n− 4),$ то все такие простые числа являются делителями $9.$ Тогда, если простое число делит и $2n +1,$ и $(n+ 5)(n− 4),$ то оно равно $3.$ Таким образом, $n= 3s+1,s∈ ℕ.$ Получаем после подстановки в выражение для НОД

((3s+ 6)(3s− 3),6s+ 3)= 3(3(s +2)(s− 1),2s+ 1)

Заметим, что $(s+2)+ (s− 1)= 2s +1.$ Тогда по лемме простое число, делящее $(3(s+ 2)(s− 1),2s+ 1)$ либо равно $3,$ либо делит оба числа $s+ 2$ и $s− 1.$ По алгоритму Евклида $(s+ 2,s− 1)= (3,s− 1).$ Таким образом, любое простое число, делящее $(3(s+ 2)(s− 1),2s+ 1),$ равно $3.$ Следовательно, $s= 3k +1.$ Снова подставляем!

3(27k(k+1),3(2k+ 1))= 9(9k(k+ 1),2k+1)

Снова заметим, что $2k +1 =k +(k+ 1),$ однако числа $k$ и $k +1$ взаимно просты, поэтому общих делителей у $k(k+ 1)$ и $2k+ 1$ нет. Это значит, что $(9k(k +1),2k+ 1)≤ 9,$ тогда $2 2 ((n +1) +20,n + 20)≤ 81.$ Положим $k =4,$ тогда $2k +1 =9,$ и $(9k(k+1),2k +1)= 9.$ Так как $k= 4,$ получаем $s= 13$ и $n= 40.$ Таким образом, мы получили и пример, и оценку.

Ответ:

$81$

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

Задача 5#67768

Натуральные числа $a,b,c$ таковы, что $1≤ a< b< c≤ 3000.$ Найдите наибольшее возможное значение величины

НОД(a,b)+ НОД (b,c)+ НОД (c,a)

Источники: Высшая проба - 2023, 11.3 (см. olymp.hse.ru)

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

Воспользуемся алгоритмом Евклида для $Н ОД(a,b),$ получим

НОД(a,b)= НО Д(a,b− a)

Заметим, что, так как НОД двух натуральных чисел не превосходит каждое из них,

НОД (a,b− a)≤ b− a⇒ НО Д(a,b)≤b − a

Аналогично получаем, что

НО Д(b,c)≤c− b

А также

Н ОД(c,a)≤ a

Складывая эти три неравенства, получаем

Н ОД(a,b)+ НОД(b,c)+ НОД(c,a)≤ (b− a)+ (c− b)+a = c≤3000

В качестве примера на $3000$ можно предъявить, например, $a= 1000,b= 2000,c= 3000.$ В этом случае

НО Д(a,b)+Н ОД(b,c)+Н ОД(c,a)= 1000+ 1000 +1000= 3000

Ответ: 3000

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

Задача 6#68099

Обозначим

a= 3481,b= 4120,N = 26069

Известно, что остаток от деления числа $b2$ на $N$ равен $a.$ Найдите разложение числа $N$ на простые множители.

Источники: Межвед-2023, 11.7 (см. www.academy.fsb.ru)

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

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

Заметим, что $26069= 131⋅199.$ Далее проверкой до целой части от соответствующего арифметического корня проверяем оба множителя на простоту. Разложение получено.

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

Заметим, что $2 a= 59.$ Тогда

b2 ≡N 592

(b− 59)(b+ 59)≡N 0.

Следовательно, пары чисел $(b− 59) и N$ или $(b+ 59) и N$ имеют общие делители, отличные от 1. Найдём наибольший общий делитель чисел $(b+59) и N$ по алгоритму Евклида:

26069= 6⋅4179+ 995

4179= 4⋅995 +199

995= 5⋅199

Следовательно, $НОД((b+59),N )=199$ — простое число. Остаётся разделить $N$ на $199.$

Ответ:

$131⋅199$

Курсы

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

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

Задача 7#68879

Натуральные числа вида $11 ...1 ◟ ◝◜n-◞$ (десятичная запись состоит из $n$ единиц) будем обозначать $R . n$ Докажите, что существует такое натуральное число $k,$ что $Rn$ делится на 41 тогда и только тогда, когда $n$ делится на $k.$

Источники: Иннополис-2023, 10-12 (см. dovuz.innopolis.university)

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

Заметим, что

10n−-1 Rn = 9

Так как числа $9$ и $41$ взаимно просты, то $Rn$ кратно $41$ тогда и только тогда, когда $n 10 − 1$ кратно $41.$ Поскольку $41$ — простое, согласно малой теореме Ферма

1040− 1 ... 41

Рассмотрим все натуральные $d,$ при которых $10d − 1$ кратно $41;$ наименьшее такое $d$ обозначим за $m.$

Если $n$ делится на $m,$ то

10n− 1= 10tm − 1= (10m − 1)(10(t− 1)m +10(t−2)m + ⋅⋅⋅+10m +1)

Значит, $n 10 − 1$ делится на $m 10 − 1,$ а значит, и на $41,$ что и требовалось.

В обратную сторону: если $n 10 − 1$ кратно $41,$ то рассмотрим $n m НО Д(10 − 1,10 − 1).$ Воспользуемся алгоритмом Евклида, т.е. свойством НОД

НО Д(a,b)= НОД(a− kb,b),где a,b,k∈ ℕ

Теперь

НОД(10n− 1,10m− 1)= НОД(10n− 1− 10n−m(10m− 1),10m− 1)

НОД(10n− 1− 10n+ 10n− m,10m − 1)= НО Д(10n−m − 1,10m− 1)

Повторяя эти действия, убеждаемся, что в конце получается число $НОД(n,m) 10 − 1.$

Если $n$ не делится на $m,$ то

НОД(n,m)< m

Значит, $m$ — не минимальное натуральное число, при котором $m 10 − 1$ кратно $41$ — противоречие. Значит, $n$ кратно $m,$ что и требовалось доказать.

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

Задача 8#71300

При каком условии на $k$ и $n$ уравнение

kx+ yn= 1

имеет решение в целых числах?

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

Совершенно очевидно, что если $НОД(k,n)=d >1$ , то левая часть делится на $d$ , значит, и правая часть должна делиться на $d$ , но 1 точно на $d >1$ не делится.

Если же $НОД(k,n)=1$ , то применим алгоритм Евклида к числам $k$ и $n$ . При этом на очередном шаге будем выражать новые числа линейным образом через $k$ и $n$ . Например, после первого шага мы ищем $НОД(n− k,k)$ , если $n> k$ , потом снова вычитаем из большего меньшее, и так далее. В итоге мы придем к тому, что одно из чисел в скобках станет равно 1, и при этом будет выражено линейно через $k$ и $n$ . Значит, мы смогли выразить 1 в виде $kx +yn =1$ , что и требовалось.

Замечание. А что произойдет, если справа написать не 1, а $s$ ? Во-первых, на $НОД(n,k,s)$ можно сократить. Если после этого $s$ не делится на $НО Д(n,k)$ , то решений, очевидно, нет. Если делится, то решения есть по тому же алгоритму Евклида. В конце надо лишь домножить на $s НОД(n,k)$ . Более интересен вопрос найти все решения подобного ЛДУ, но этот вопрос мы оставим для самостоятельных размышлений.

Ответ:

при взаимно простых $k$ и $n$

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

Задача 9#75630

Назовём многочлен $P(x)∈ ℤ[x] p$ перестановочным по простому модулю $p,$ если его значения дают все возможные остатки при делении на $p.$ Существует ли перестановочный по модулю $101$ многочлен степени $17?$

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

Докажем, что $x17$ — перестановочный многочлен. Для этого проверим, что $a17 ≡ b17 ⇔ a ≡b.$

Если $a≡ b,$ то утверждение очевидно.

Пусть $17 17 −117 a ≡ b ⇔ (ab ) ≡ 1.$ Пусть $g$ — первообразный корень по модулю 101. Тогда $−1 n ab ≡ g .$ Получаем систему:

{ 17n g100 ≡1 g ≡ 1

Тогда $gНОД(100,17n) ≡ 1.$ Так как $g$ — первообразный корень, то $НО Д(100,17n)= 100.$ Откуда получаем, что $100 | n.$ Тогда $ab−1 ≡ gn ≡ 1⇔ a≡ b.$

Тогда получаем, что $x17$ осуществляет биекцию $Z → Z , p p$ и, следовательно, является перестановочным.

Ответ: да

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

Задача 10#75796

Даны многочлены $P,Q ∈ℚ [x].$ Рассмотрим НОДы этих многочленов над $ℚ$ и над $ℝ.$ Докажите, что эти НОДы отличаются домножением на константу.

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

В $ℚ$ $НОД(P,Q)$ находится алгоритмом Евклида. Ясно, что этот же алгоритм подойдет и в $ℝ.$ Но тогда $НОД (P,Q) ℚ$ отличается домножением на константу от $Н ОДℝ(P,Q),$ что и требовалось доказать.

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

Задача 11#71645

Сократите дробь

2x6+-5x4− 3x3+-2x2− 12x−-14 4x6− 4x4− 6x3− 3x2+25x− 28

В результате сокращения степени многочленов в числителе и знаменателе должны уменьшиться.

Источники: Межвед-2022, 11.3 (см. www.academy.fsb.ru)

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

Найдем наибольший общий делитель многочленов, стоящих в числителе и знаменателе, используя алгоритм Евклида.

Для этого поделим с остатком знаменатель на числитель:

6 4 3 2 ( 6 4 3 2 ) 4 2 4x − 4x − 6x − 3x + 25x − 28= 2⋅ 2x +5x − 3x +2x − 12x − 14 − 14x − 7x +49

В результате деления получили остаток $− 14x4 − 7x2+ 49.$ Теперь числитель (который сейчас выступал в роли делителя) поделим (например, «уголком») на остаток:

6 4 3 2 ( 4 2 )( x2 2) 3 2x +5x − 3x + 2x − 12x− 14== −14x − 7x + 49 ⋅ − 2 − 7 + 4x + 2x− 14

Далее надо опять разделить делитель на остаток. В этот раз остаток от деления оказывается равным нулю:

( ) −14x4− 7x2 +49= − 7x ⋅4x3+ 2x− 14 2

Это означает, что многочлен $4x3+ 2x− 14$ является искомым наибольшим общим делителем числителя и знаменателя исходной дроби и он может быть «вынесен за скобки» (чтобы избежать появления дробных коэффициентов, будет удобнее использовать многочлен $2x3 +x − 7):$

Итак,

( )( ) 2x6-+5x4−-3x3-+2x2−-12x-− 14=-2x3+-x−-7-⋅x3+-2x+-2 4x6 − 4x4− 6x3 − 3x2+ 25x − 28 (2x3+ x− 7)⋅(2x3 − 3x+ 4)

Ответ:

$-x3+-2x-+2- 2x3− 3x+ 4$

Предыдущая подтема

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