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

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

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

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

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

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

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

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

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

Задача 1#96443

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

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

Подсказка

Дробь всегда можно сократить на наибольший общий делитель ее числителя и знаменателя, если он больше 1. Можно ли вычислить НОД в нашем случае?

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

Дробь можно сократить на НОД числителя и знаменателя, если он больше $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.$ На сколько частей поделят большее колесо отметины от гвоздя?

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

Подсказка 1

Разделим колесо длиной 102 на 102 равных части (длиной 1 по окружности) и каждой точке деления поставим в соответствие число от 0 до 101. Можно полагать, что первая отметина гвоздя находится в точке 0. Также сразу ясно, что все отметины гвоздя могут попасть только в отмеченные точки. А как узнать, в какой точке появится отметина после x полных оборотов колеса длиной 19?

Подсказка 2

Верно! Можно заметить, что отметина появятся в точке, равной остатку от деления числа 19x на 102. Перепишем это утверждение по определению остатку 19x = 102y + r. Осталось узнать, какие r могут получиться! Как это сделать?

Подсказка 3

Точно! Давайте представим уравнение в виде 19x + 102y = r (переобозначим и вместо -y напишем y). Можно заметить, что 19 и 102 взаимно просты. Что можно сказать о решениях этого диофантового уравнения?

Подсказка 4

Конечно! По теореме о линейном представлении НОД найдутся такие числа a и b, что 19a + 102b = 1. А можно ли теперь узнать, какие r можно представить в виде 19x + 102y = 1?

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

Количество частей равно количеству отметин. Вычислим число отметин. Выберем первую точку на колесе длины $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. Например, 37 - 11 = a - b. Что получится в конце?

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

Обозначим для удобства $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?$

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

Подсказка 1

Для удобства в этой задаче можно полагать, что в НОДе числа могут быть отрицательными, а сам он всегда положителен. Первый шаг алгоритма Евклида дает ((n+1)²+20,n²+20) = (2n+1, n²+20). Можно ли теперь по алгоритму Евклида сделать так, чтобы получившееся выражение превратилось в выражение вида (a+b,ab)?

Подсказка 2

Конечно! Вычтем n(2n+1) из второго аргумента. Тогда получится (2n+1,-n²-n+20). Это равно (2n+1, (n+5)(n-4)). Тогда (n+5) + (n-4) = 2n+1. Предположим, что наш НОД больше 1. Что можно сказать о простых числах, которые его делят?

Подсказка 3

Верно! Можно утверждать, что простые числа, делящие выражение вида (ab, a+b) делят оба числа a и b. Тогда, поскольку (n+5,n-4)=(9,n-4), то все простые делители такого НОДа равны 3. Что можно сказать об n?

Подсказка 4

Верно! Тогда n = 3s + 1. Подставляем и получаем, что наш НОД равен 3(3(s+2)(s-1), 2s+1). Поскольку 2s + 1 = (s+2) + (s-1), то можно снова применить утверждение о простых делителях выражений (ab,a+b) и получить, что наш новый простой делитель либо равен 3, либо делит оба числа s+2 и s-1. Чему тогда равен этот простой делитель?

Подсказка 5

Верно! Тогда этот простой делитель равен 3. Получаем, что s = 3k + 1. После подстановки получается 9(9k(k+1),2k+1). Числа k и k+1 взаимно просты, тогда из утверждения о выражениях (a+b,ab) получается, что k(k+1) и 2k+1 взаимно просты. Какое наибольшее значение может принимать наш НОД?

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

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

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)

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

Подсказка 1

Хочется получить какую-то оценку на эти НОДы. Понятно, что НОД(а,b) не больше чем a. Может попробовать что-то поделать с такой оценкой?

Подсказка 2

Если оценить так каждый НОД, получается как-то слишком грубо. Какой алгоритм приходит в голову, когда речь идёт о НОДах? Конечно же, алгоритм Евклида! Может, как-то улучшить оценку для НОД(a,b) с помощью него?

Подсказка 3

Если воспользоваться алгоритмом Евклида получиться, что: НОД(a,b)=НОД(a,b-a). Тогда т.к. НОД(a,b-a) не больше чем b-a, то и НОД(a,b) будет не больше чем b-a. если сделать тоже самое с НОД(b,c), что получится?

Подсказка 4

Итак, мы имеем что НОД(a,b) не больше b-a, а НОД(b,c) не больше c-b. Если их сложить, получится, что их сумма не больше чем (b-a)+(c-b)=с-а. Если оценить, что НОД(а,с) не больше чем a, то окончательно сумма всех НОДов будет не больше с, которое не больше 3000. Осталось только придумать пример...

Подсказка 5

Понятно, что с=3000. Чтобы достигалась оценка, необходимо, чтобы НОД(a,c)=a. Тогда с делится на a. Если мы сделаем так, что b тоже поделится на a, то, возможно, придумаем пример

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

Воспользуемся алгоритмом Евклида для $Н ОД(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 = 26029

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

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

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

Подсказка 1

Каким-то образом у нас в условии есть утверждение про квадрат, а числа у нас какие-то странные…быть может, поискать какие-то свойства у них?

Подсказка 2

Число а - квадрат! Тогда мы можем записать условие на остаток от деления на N и выполнить некоторые преобразования, чтобы понять, какие числа имеют с N общие делители.

Подсказка 3

Оказывается, (b-59)(b+59) делится на N! Тогда хотя бы одна из этих скобок имеет с N общие множители, а, значит, мы можем найти их НОД с N) Как это сделать?

Подсказка 4

По алгоритму Евклида находим НОД((b-59), N), остаётся лишь понять, а на что ещё делится N?)

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

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

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

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

Подсказка 1

Сложно анализировать число только из единиц, т.к. сложно разобрать даже его делители...тогда было бы по хорошему его как-то преобразовать в более приятный вид. И подумаем над вопросом: "А откуда тут вообще 41? Почему не 42, например?"

Подсказка 2

Число, состоящее из единиц, можно записать как (10^n - 1)/9. А использовать 41 хочется только как простое число... Выходит, что (10^n - 1)/9 должно делиться на 41. Когда это возможно?

Подсказка 3

Когда 10^n - 1 делится на 41. Хмм, 41 простое... Какая известная теорема может помочь нам в нахождении хотя бы одного n, удовлетворяющему предыдущему предложению?

Подсказка 4

Малая теорема Ферма утверждает, что при n = 40 10^40 - 1 делится на 41. Теперь хочется как-то найти k из условия... а на что должно делиться n, чтобы 10^n - 1 делилось на 41? Мы не можем найти все такие случаи, но может попробовать найти хотя бы одного такое k и доказать, что утверждение работает в обе стороны.

Подсказка 5

Рассмотрим все такие d, что 10^d - 1 делится на 41 и выберем среди них наименьшее m. Докажем, что если n делится на m, то 10^n - 1 делится на 10^m - 1, а, значит, и на 41. Если это получится, то у нас найдено k, но условие "тогда и только тогда" пока не доказано. Теперь попробуем доказать, что если 10^n - 1 кратно 41, то n кратно m.

Подсказка 6

Мы взяли m наименьшим, т.к. обычно это помогает в поиске противоречий. Для того чтобы доказать утверждение из подсказки 5, попробуем найти НОД(10^n - 1, 10^m - 1).

Подсказка 7

В процессе поиска c помощью алгоритма Евклида можно заметить, что у нас в конце концов появится 10^(НОД(m, n)) - 1. Предположим, что n не делится на m, тогда НОД(n, m) < m. Осталось лишь найти противоречие с тем, что m - наименьшее взятое число из набора.

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

Заметим, что

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?$

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

Подсказка 1

Давайте доказывать, что такой многочлен существует. Более того, давайте доказывать, что x^17 подходит. Как это можно сделать?

Подсказка 2

Для проверки достаточно показать, что сравнение a^17 = b ^17 бывает только при a = b. Как это можно сделать? Вспомните про первообразный корень и докажите это.

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

Докажем, что $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)

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

Подсказка 1

Чтобы упростить дробь, мы должны сократить числитель и знаменатель на их наибольший общий делитель. Какой алгоритм мы знаем для нахождения НОД двух чисел?

Подсказка 2

Давайте применим алгоритм Евклида для числителя и знаменателя. Найдите остаток от деления знаменателя на числитель. Это можно сделать делением «уголком».

Подсказка 3

Если сделать всё правильно, то остаток будет равен -14x⁴-7x²+49. Теперь выполните тот же алгоритм для нашего числителя и остатка и будем его продолжать, пока одно из выражений не станет равным 0, оставшееся выражение и будет НОД числителя и знаменателя. Осталось только сократить на него.

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

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

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

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$

Предыдущий раздел

Следующий раздел