№19. Задачи на олимпиадные темы

Основная теорема арифметики, НОД и НОК

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

Осваивайте новые концепции ежедневно

Вдумывайтесь в теоретические материалы

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

Подтемы раздела: №19. Задачи на олимпиадные темы

Теоретическая справка

#572

Необходимые определения и ОТА

Определение Натуральное число $p$ является простым, если оно имеет ровно два различных делителя: 1 и $p.$

NB Заметим, из данного определения следует, что число 1 не является простым. К тому же число 2 является единственным четным простым числом.

Определение Наибольшим общим делителем (НОД) двух чисел $m$ и $n$ называется наибольшее натуральное число, на которое делятся и $m,$ и $n.$ Допустимые обозначения: НОД $(m,n);$ $(m,n)$ .

Аналогом слова «делится» является значок $. ..,$ то есть запись $. a..b$ означает, что $a$ делится на $b.$ Например, из определения выше очевидно, что $. m ..(m,n)$ и $. n ..(m, n).$

Определение Наименьшим общим кратным (НОК) двух чисел $m$ и $n$ называется наименьшее натуральное число, которое делится и на $m,$ и $n.$ Допустимые обозначения: НОК $(m,n);$ $[m,n].$

Иными словами НОК — это наименьшее натуральное $k$ такое, что $k...m$ и $k ...n.$

Теорема (Основная теорема арифметики или ОТА)

Любое натуральное число $n> 1$ единственным образом представимо в виде произведения степеней простых множителей, то есть

n= pα1⋅pα2⋅...pαk, где p < p < ...<p — просты е числа, α ,α ,...,α — натуральные. 1 2 k 1 2 k 1 2 k

Например, число 60 раскладывается так:

2 60 =2 ⋅2⋅3⋅5= 2 ⋅3⋅5

Менее формально можно сказать, что по ОТА любое натуральное число, кроме 1, раскладывается на простые множители единственным образом.

NB Разложение числа по ОТА, записанное выше, также называют каноническим.

Определение Два числа $a$ и $b$ называются взаимно простыми, если в их разложениях нет ни одного общего простого множителя. Очевидно, что данное определение взаимно простых эквивалентно следующему:

Определение Два числа $a$ и $b$ называются взаимно простыми, если их НОД равен 1.

Задачи на ОТА

1. Существует ли натуральное число с произведением цифр 2310?

Ответ. Не существует

Решение. Разложим число 2310 на простые множители, получим $2310= 2⋅3 ⋅5 ⋅7⋅11.$

Допустим, что существует некоторое простое число, произведение цифр которого равно 2310, тогда, как видно по разложению на простые множители, произведение цифр должно делиться на 11. Однако ни одна ненулевая цифра не делится на 11, значит, такое невозможно.

NB Заметим, что нам было важно, что 11 является простым и не может быть разложено на более мелкие множители, следовательно, одна из цифр должна быть кратна 11, что приводит к противоречию.

2. Сколько существует пар простых чисел, которые отличаются друг от друга на 15?

Ответ. Единственная пара 2 и 17

Решение. Уже было замечено, что 2 — единственное четное простое число. Воспользуемся этим.

Пусть мы имеем $p1+ 15= p2.$ Допустим, $p1$ нечетно, тогда левая часть равенства четна, следовательно, $p2$ — некоторое четное простое, большее 15. Получаем противоречие. Остается случай, когда $p1$ четно, то есть фактически равно 2. Получаем пару 2 и 17.

3. Разделите числа 2, 4, 6, 10, 22, 25, 40, 66 на две группы так, чтобы произведения в двух группах были равны. Сколькими способами это можно сделать?

Ответ. Единственный допустимый способ:

$I: 22 ⋅6⋅25⋅2⋅4$

$II: 66⋅10⋅40$

Решение. Разложим каждое из чисел на простые множители:

2= 2, 4 = 22 6= 2⋅3, 10 =2 ⋅5 22= 2⋅11, 25 =52 40= 23⋅5, 66 =2 ⋅3⋅11

Заметим, что равенство произведений чисел в группах равносильно тому, что наборы простых множителей в них одинаковые. Будем постепенно формировать группы.

Числа 22 и 66 — единственные, содержащие в разложении множитель 11, следовательно, они должны быть помещены в разные группы. Для удобства назовем I группу с числом 22 и II группу с числом 66.

$pict$

Заметим, что из оставшихся чисел только 6 содержит в разложении 3, причем группа II уже содержит 3, а I не содержит. Значит, число 6 должно оказаться в I группе.

$pict$

Посмотрим на множитель 5. 10 и 40 содержат его в первой степени, 25 — во второй, следовательно, в одной из групп должно оказаться число 25, а в другой — пара чисел 10 и 40. Чтобы понять, что в какой группе, рассмотрим простой множитель 2. Во все числа в совокупности 2 входит в 10 степени, значит, итоговая степень 2 в каждой из групп должны быть равна 5. Пара 10 и 40 содержит 2 в 4 степени, если мы поместим ее в первую группу, степень двойки в ней составит уже $2 +4 = 6,$ то есть превысит 5. Остается единственный допустимый способ расположения по группам чисел, кратных 5.

$pict$

Остались числа 2 и 4, их располагаем единственным подходящим способом в группу I, получаем итоговое разбиение. Заметим, что нигде не было альтернатив, мы просто «восстанавливали» ситуацию, то есть способ является единственным по построению.

$pict$

4. Прямоугольник с целыми длинами сторон разбит на двенадцать квадратов со следующими длинами сторон: 2, 2, 3, 3, 5, 5, 7, 7, 8, 8, 9, 9. Каков периметр прямоугольника?

Ответ. 90

Решение. Найдем площадь $S$ прямоугольника, она равна сумме площадей квадратов, на которые он разбит

( ) S =2 ⋅22+ 32+ 52+ 72+ 82+ 92 = 2 ⋅(4+ 9+ 25+ 49+ 64+ 81)= 464

Разложим на простые, получим $4 464= 2 ⋅29.$ Площадь равна произведению сторон, рассмотрим все возможные способы представления числа 464 в виде произведения двух множителей, пользуясь его разложением: $1 ⋅464;$ $2 ⋅232;$ $4 ⋅116;$ $8 ⋅58;$ $16 ⋅29.$ Заметим, что в каждом представлении, кроме последнего, один из множителей меньше 9, то есть одна из сторон такого прямоугольника меньше 9. Это противоречит тому, что такой прямоугольник в своем разбиении содержит квадрат со стороной 9, значит, единственный возможный вариант достигается при длинах сторон 16 и 29. Периметр в таком случае равен 90.

Важные факты про НОК и НОД

Факт 1. $a$ и $b$ — натуральные числа. Их НОД обозначим $(a,b),$ НОК обозначим $[a,b].$ Тогда выполняется соотношение

a⋅b= (a,b) ⋅[a,b],

то есть произведение НОК и НОД равно произведению чисел.

Доказательство

Возьмем произвольное простое число $p$ и докажем, что оно содержится в разложениях на простые левой и правой частей в одинаковой степени. Из этого будет сразу следовать равенство.

Пусть степень вхождения $p$ в разложение на простые множители числа $a$ равна $α,$ в разложение $b$ — $β$ ( $α$ и $β$ могут быть равны нулю). Тогда степень вхождения $p$ в левую часть равна $α + β.$

Степень вхождения $p$ в $(a,b)$ равна $min(α,β).$ Действительно, больше она быть не может, так как в этом случае одно из чисел не будет делиться на НОД, что противоречит определению, меньше она быть не может, так как возникает противоречие с максимальностью НОД. По аналогичным соображениям степень вхождения $p$ в $[a,b]$ равна $max (α,β).$

Итого имеем, что в левую часть $p$ входит в степени $α + β,$ а в правую в степени $min(α,β)+ max(α,β),$ но очевидно, что $α+ β =min(α,β)+ max(α,β)$ для любых $α$ и $β.$ Следовательно для любого простого $p$ верно, что оно входит в разложения обеих частей в равной степени, значит, равенство выполняется.

Факт 2. $a$ и $b$ — натуральные числа, их НОД равен $d.$ Тогда $( ) a, b = 1, d d$ то есть такие числа взаимно просты.

Доказательство

Допустим противное, пусть $( a b) d,d$ делится на некоторое простое $p.$ Тогда $a .. d .p$ и $b.. d .p.$ Положим $d1 =p ⋅d.$ Тогда $.. a.d1,$ $.. b .d1,$ $d1 > d,$ получили противоречие с тем, что $d$ — НОД $a$ и $b.$

Формула для количества делителей числа

Лемма Пусть натуральное число $n$ имеет канонический вид

α α α n= p11⋅p22⋅...pkk , где p1 < p2 < ...<pk — просты е числа, α1,α2,...,αk — натуральные.

Тогда общее количество $Dn$ различных делителей числа $n$ выражается формулой

Dn = (α1+ 1)⋅(α2 +1)⋅...⋅(αk +1)

Доказательство

Определим произвольный делитель $d$ числа $n$ как некоторое число, в разложение которого каждый простой множитель входит в степени не большей, чем степень вхождения этого простого множителя в разложение числа $n.$ Это можно записать так

d= pβ11⋅pβ22 ⋅...pβkk , где 0≤ β1 ≤ α1,0≤ β2 ≤ α2, ...,0 ≤ βk ≤ αk

Таким образом, набор соответствующих $β$ единственным образом задает делитель. Посчитаем количество таких наборов. Есть $αi+ 1$ способов выбрать $bi$ из набора $0,1,...,αi,$ каждое $bi$ выбирается независимо, перемножив, получаем нужную формулу.

Пример. Рассмотрим число

60= 2 ⋅2⋅3⋅5= 22⋅31⋅51.

Его количество делителей будет равно $D = (2+ 1)(1+ 1)(1 +1)= 3⋅2 ⋅2= 12. 60$

Проверим полученный ответ, выписав все делители числа 60:

1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

Определения НОК и НОД для произвольного количества чисел

Определение Наибольшим общим делителем для набора из $n$ чисел называется наибольшее натуральное число, на которое делится каждое число из набора.

Определение Наименьшим общим кратным для набора из $n$ чисел называется наименьшее натуральное число, которое делится на каждое число из набора.

Рассмотрим следующую задачу:

а) Приведите пример 5 различных натуральных чисел, расставленных по кругу так, что наименьшее общее кратное любых двух соседних чисел равно 105.
б) Можно ли расставить по кругу 8 различных натуральных чисел так, чтобы наименьшее общее кратное любых двух соседних чисел равнялось 300, а наибольший общий делитель любых трех подряд идущих чисел равнялся 1?
в) Какое наибольшее количество различных чисел можно расставить по кругу так, чтобы наименьшее общее кратное любых двух соседних чисел было равно 60?

Ответ. а) 3, 35, 15, 7, 105

б) Нет

в) 8

Решение. а) Разложим 105 на простые множители: $105= 3⋅5 ⋅7.$ Зная разложение, несложно подобрать нужные 5 чисел, например

$35337⋅⋅⋅755⋅7$

б) Допустим, это возможно.

Возьмем произвольные соседние числа $a$ и $b,$ тогда $[a,b]= 300.$ По определению $[a,b]...a ⇒ 300...a,$ аналогично для $b.$ Значит, каждое число в кругу является делителем числа 300.

Разложим 300 на простые множители, получим $300= 22⋅3⋅52.$ Попробуем выделить среди делителей числа 300 те, которые точно не могут быть использованы.

Сразу можем исключить 1, так как с обеих сторон от нее должно стоять число 300, чтобы не нарушать условие про НОК соседей. Однако числа не могут повторяться.

Далее, рассмотрим делители 300, которые содержат 2 ровно в первой степени. Допустим, некоторое число $2t,$ где $t$ нечетно, стоит в кругу. Рассмотрим соседа $s$ числа $2t.$ По условию $[s,2t]= 300 ...4,$ причем $2t$ не делится на 4, следовательно, $s...4.$ Аналогично и второй сосед $r$ числа $2t$ также делится на 4. По условию должно выполняться $(s,2t,r)= 1,$ однако $s...4,$ $2t...2,$ $r ...4$ , то есть их НОД должен быть четным. Получаем противоречие, значит, ни один из делителей числа 300 вида $2t,$ где $t$ нечетно, не мог быть использован.

Выпишем все оставшиеся делители, их 11

2 2 2 2 2 2 2 2 2 2 3, 5, 2 , 5 , 3⋅5, 2 ⋅3, 2-⋅5, 3⋅5, 2 ⋅5 , 2-⋅3⋅5, 2 ⋅3⋅5

Выделены те делители, которые содержат 5 ровно в первой степени. Их мы можем исключить по соображениям, аналогичным приведенным выше. Заметим, что нам было совершенно несущественно, что именно 2 входит в первой степени, и при замене 2 на произвольное простое число ничего не изменится. Итого, неисключенными остались $11 − 4 =7$ чисел, а по кругу должны быть расставлены 8. Противоречие.

в) Допустим, мы имеем корректную расстановку на некоторое количество чисел. Возьмем произвольные соседние числа $a$ и $b,$ тогда $[a,b]= 60.$ По определению $.. .. [a,b].a ⇒ 60.a,$ аналогично для $b.$ Значит, каждое число в кругу является делителем числа 60.

Разложим 60 на простые множители, получим $2 60 =2 ⋅3 ⋅5.$ Выпишем все его делители

1, 2, 3, 5, 22, 2 ⋅3, 2 ⋅5, 3 ⋅5, 22 ⋅3, 22 ⋅5, 2 ⋅3⋅5, 22⋅3⋅5

Получили 12 различных делителей. Проверить себя можно, посчитав количество делителей по формуле количества делителей: $3 ⋅2⋅2= 12.$

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

Построим пример на 8 (красным для удобства восприятия обозначены числа, кратные 4).

$2222 22522332 ⋅⋅⋅35⋅35⋅5⋅3⋅5$

Предыдущая справка

Следующая справка