Текст статьи Вагутен В. Н. Алгоритм Евклида и основная теорема арифметики // Квант. — 1972. — № 6. — С. 30—35.
Все знают, что любое целое положительное число можно разложить в произведение простых множителей; так например,
Эти факты считаются очевидными. Между тем доказать их не так просто. Это мы сделаем в конце статьи, а начнём с самых простых утверждений, относящихся к делимости целых чисел, и расскажем о том, как найти наибольший общий делитель двух чисел, не раскладывая их на простые множители.
Всюду латинскими буквами
1. Делимость суммы, разности и произведения
Мы говорим, что целое число
Сразу выведем два простых утверждения:
- Если числа
$a$ и$b$ делятся на$c$, то и их сумма$a+b$, и их разность$a-b$ делятся на$c$; - Если
$a$ делится на$c$, а$b$ делится на$d$, то их произведение$ab$ делится на$cd$.
Докажем 1°. Поскольку
Докажем 2°. Пусть
Задача 1. Докажите, что если
Задача 2. Какие из следующих утверждений верны, а какие нет:
- если одно слагаемое делится на 6, а другое не делится на 6, то их сумма не делится на 6;
- если каждое из двух слагаемых не делится на 6, то их сумма не делится на 6;
- если сумма двух слагаемых не делится на 6, то хотя бы одно из них не делится на 6;
- если сумма двух слагаемых не делится на 6, то каждое слагаемое не делится на 6;
- если произведение нескольких сомножителей делится на 6, то и один из сомножителей делится на 6?
Задача 3. Про целые числа
Задача 4. Докажите, что если
2. Деление с остатком
Все знают правило деления одного целого числа
если
Задача 5. В одном из подъездов 8-этажного дома на первом этаже находятся квартиры от №97 до №102. На каком этаже и в каком (по номеру) подъезде находится квартира №211? (На всех этажах одинаковое число квартир и все подъезды устроены одинаково).
Задача 6. Было 5 листов бумаги. Некоторые из них разрезали на 5 кусков каждый. Затем некоторые из получившихся кусков снова разрезали на 5 частей, и так сделали несколько раз. Могли ли в результате получить 1971 кусок?
Задача 7. Найдите наименьшее шестизначное число, которое делится на 3, на 7 и на 13.
Задача 8. Какой остаток даёт число
- при делении на 4;
- при делении на 8;
- при делении на 9?
3. Наибольший общий делитель [НОД]
Пусть
Если
Задача 9. Произведение двух чисел равно 600. Какое наибольшее значение может иметь НОД таких чисел?
Задача 10. Докажите, что если
Задача 11. Какое наибольшее число одинаковых букетов можно составить из 264 белых и 192 красных тюльпанов?
Задача 12.
- На листке клетчатой бумаги нарисован прямоугольник размером
$10\times15$, на его диагонали лежат 6 узлов сетки (рис. 2). Пусть имеется прямоугольник$m\times n$, стороны которого проходят по линиям сетки. Сколько узлов сетки лежит на его диагонали? - Сколько решений в натуральных числах
$x$, $y$ имеет уравнение$mx+ny=mn$, где$m$ и$n$ — данные натуральные числа? (Напомним, что натуральными называются целые положительные числа).
4. Алгоритм Евклида
Для того, чтобы найти НОД двух чисел, можно, конечно, действовать так: выписать все делители каждого из чисел, выбрать общие делители, а затем взять из них наибольший. Можно поступить иначе, не отыскивая отдельно делители каждого из чисел.
Докажем следующую важную лемму.
Лемма 1. Пусть
С этой целью покажем, что у пары чисел
Докажем сначала первое утверждение. Пусть
Перейдём ко второму утверждению. Если
Доказанная лемма позволяет легко и быстро находить НОД двух чисел. Посмотрим, как это делается.
Пример. Найдём, чему равен
Решение. Разделим 6069 на 663 с остатком:
Ищем
Ответ.
Метод отыскания наибольшего общего делителя, основанный на последовательном применении леммы 1, носит специальное название — алгоритм Евклида.
Задача 13. Найдите наибольший общий делитель чисел:
$987\,654\,321$ и$123\,456\,789$, $7\,777\,777\,777$ и$777\,777$.
Задача 14. От прямоугольника
На какие квадраты будет разрезан прямоугольник? (Укажите их размеры и количество.)
Итак, алгоритм Евклида — это простой метод нахождения наибольшего общего делителя двух чисел. Если у нас имеется два числа
Ясно, что указанный процесс обязательно кончится, поскольку каждый остаток меньше предыдущего, а все остатки — неотрицательные числа. Последний остаток
С одной геометрической иллюстрацией алгоритма Евклида мы встретились в задаче 14. Более известный и важный геометрический вариант алгоритма Евклида — алгоритм отыскания наибольшей общей меры двух отрезков (рис. 4).
Рис. 4. Пусть
Если, откладывая некоторое
Задача 15. Найдите наибольшее число
5. Линейное уравнение
С помощью алгоритма Евклида можно доказать одно важное свойство наибольшего общего делителя.
Лемма 2. Если
В самом деле, остаток
Вернёмся к примеру, разобранному в предыдущем пункте, в котором мы нашли
Из первого равенства
Важным частным случаем леммы 2 является такое утверждение.
Если числа
Заметим, между прочим, что лемма 2 следует из этого утверждения. Например, уравнение, которое мы решали:
Решение
Ещё одно замечание. Мы привели способ, позволяющий находить только одно решение такого уравнения. На самом деле, если есть хотя бы одно решение, то их существует бесконечно много.
Например, числа
$$
x=-6+13t,\quad y=55-119t\tag{*}
$$
Формулы (*) дают все решения этих уравнений в целых числах. Докажем это. Пусть
Поскольку левая часть последнего равенства делится на 13, а числа 119 и 13 взаимно просты, то число
Для того, чтобы уравнение
Задача 16. Найдите такие целые числа
Задача 17. Имеют ли следующие уравнения решения в целых числах:
$105x+56y=42$; $104x+65y=43$?
Задача 18.
- Можно ли составить батарею напряжением 220 В, соединяя последовательно элементы двух типов: напряжением 6 В и 16 В, — и если можно, то сколько надо взять тех и других?
- Тот же вопрос, если напряжение элементов 6 В и 15 В.
Задача 19. Можно ли разменять 45 рублей на рублёвые, трехрублёвые и пятирублёвые купюры так, чтобы получить всего 20 купюр?
6. Основная теорема арифметики
До доказательства основной теоремы сделаем ещё один шаг — докажем лемму.
Лемма 3. Если произведение
Действительно, поскольку у нас
Лемма 3 очень часто используется при решении задач, причём иногда совсем «незаметно». Мы, например, опирались на неё в предыдущем пункте при выводе формул, дающих все решения уравнения
Задача 20. Докажите, что если число
Задача 21. Какие из следующих утверждений верны:
- если
$ab$ делится на 15, то хотя бы один из сомножителей делится на 15; - если
$ab$ делится на 17, то хотя бы один из сомножителей делится на 17; - если
$a$ делится нa 6, а$b$ делится на 10, то$ab$ делится на 15; - если
$ab$ делится на 60, а$b$ взаимно просто с 10, то$a$ делится на 20.
Напомним теперь, что натуральное число
Если
Лемму 3 можно сформулировать в частном случае так:
если произведение
Отсюда сразу выводится основная теорема арифметики.
Каждое число разлагается на простые множители и притом единственным образом.
Действительно, пусть число раскладывается на несколько множителей и хотя бы один из них не является простым числом, тогда этот множитель сам разлагается на множители; если среди его множителей снова имеется не простой множитель, он опять разлагается на множители, и т. д. Поскольку каждый множитель числа меньше самого числа, такой процесс не может продолжаться бесконечно, и мы обязательно придём к разложению числа на простые множители.
Докажем теперь, что не может быть двух различных разложений числа на простые множители. Предположим, что имеются два разложения числа
Задача 22. Разложите числа 1971, 1972 и 1973 на простые множители.
Задача 23.
- Докажите, что если
$m$ и$n$ взаимно просты и$am=bn$, то существует такое целое$k$, что$a=kn$, $b=km$. - Докажите, что если
$m$ и$n$ взаимно просты и$x^m=y^n$, то найдётся такое целое число$z$, что$x=z^n$, а$y=z^m$.
Ответы, указания, решения
- По условию
$a=kb$ и$b=lc$. Отсюда$a=(kl)c$. Утверждение а) верно: докажем это. Пусть
$a+b=c$, причём$a$ делится на 6, а$b$ не делится на 6. Докажем, что$c$ не делится на 6. Предположим противное: пусть$c$ делится на 6. Но тогда$b=c-a$ делится на 6 (см. 1°). Мы получили противоречие с условием задачи.Утверждение б) неверно. Для опровержения его достаточно привести противоречащий пример: 7 + 5 = 12. Здесь каждое из двух слагаемых не делится на 6, в то время как их сумма делится на 6.
Утверждение в) верно: если бы оба слагаемых делились на 6, то тогда и их сумма делилась бы на 6.
Утверждение г) неверно. Противоречащий пример: 6 + 5 = 11.
Утверждение д) неверно. Противоречащий пример:
$2\cdot3=6$. - Нет, не следует. Противоречащий пример:
$a=3$, $b=1$, $c=2$; тогда$a+b=4$ делится на 2, и$a-b$ делится на 2, но ни$a$, ни$b$ не делятся на 2. - Из равенств
$ab=(a+b)^2-(a^2+ab+b^2)$, $a^2+b^2=(a+b)^2-2ab$ следует, что$ab$ и$a^2+b^2$ делятся на$a+b$. Из равенства$a^4+b^4=(a^2+b^2)^2-2a^2b^2$ следует, что$a^4+b^4$ делится на$(a+b)^2$. - Так как на одном из этажей в каком-то подъезде находится 6 квартир (с № 97 по № 102), то и на всех этажах находится по 6 квартир в каждом подъезде. Так как в каждом подъезде 8 этажей, то всего в подъезде
$6\cdot8=48$ квартир. Поскольку$211=48\cdot4+19$, то квартира № 211 находится в 5-м подъезде, а так как$19=4\cdot4+3$, то эта квартира находится на 5-м этаже. - При разрезании одного куска на 5 частей число всех кусков увеличивается на 4. Таким образом, число кусков будет всегда иметь вид
$4k+1$, т. е. давать при делении на 4 остаток 1. Однако$1971=4\cdot492+3$, и ответ отрицательный. - Шестизначное число должно делиться на
$3\cdot7\cdot13=273$, а$100\,000=366\cdot273+82$, можно добавить 191, получится$100\,191=367\cdot273$. - a) 1; б) 5; в) 8.
- Пусть
$a$ и$b$ — данные числа,$d=\gcd(a,b)$. Тогда$a=kd$, $b=md$, где числа$k$ и$m$ уже не имеют общих делителей, больших единицы, т. е.$k$ и$m$ взаимно просты. Из того, что$ab=600$, следует, что$kmd^2=600$. Но наибольший квадрат целого числа, на который делится число 600, есть число 100, поэтому наибольшее значение$d$ равно 10. Пример:$a=60$, $b=10$. - 24 букета.
- а)
$\gcd(m,n)+1$; б)$\gcd(m,n)-1$. -
$987\,654\,321=8\cdot12\,345\,789+9$; $123\,456\,789$ делится на 9 и$\gcd(987\,654\,321, 123\,456\,789)=9$. - 77.
- Два квадрата размером
$141\times141$, три$42\times42$, два$15\times15$, один$12\times12$, четыре$3\times3$. $\gcd(324,141)=3$, поэтому меньших квадратов не будет. $\alpha=\dfrac3{140}$. После деления на
$\gcd(85,204)=17$ получим:$5x+12y=1$. Но$12=2\cdot5+2$, $5=2\cdot2+1$, откуда $$ 1=5-2\cdot2=5-2(12-2\cdot5)=5\cdot5-2\cdot12. $$Одно решение:
$x=5$, $y=-2$. Общее решение:$x=5+12t$, $y=-2-5t$, где$t$ — любое целое число.- а) Да; б) нет.
-
Мы должны найти такие целые числа
$x$ и$y$, чтобы выполнялось равенство$6x+16y=220$ или$3x+8y=110$. Одно из решений:$x_1=330$, $y_1=-110$. Общее решение можно записать так: $$ x=330-8t,\quad y=-110+3t.\tag{*} $$ где$t$ — любое целое число. Теперь естественно выбрать такое$t$, чтобы$x$ и$y$ были неотрицательными. (Можно, конечно, подключать аккумуляторы «в обратную сторону» — «плюс» к «плюсу», но мы постараемся обойтись без этого.)Учтём это требование:
$330-8t\ge0$, т. е.$t\le\dfrac{330}8=41\dfrac14$, $-110+3t\le0$, т. е.$t\ge\dfrac{110}3=36\dfrac23$. Подставляя$t=37$, 38, 39, 40, 41 в формулы (*), получаем 5 вариантов: $$ \def\tl#1#2{\colsep{0pt}{{\footnotesize\begin{array}{l}\text{#1}\\[-1pt]\text{#2}\end{array}}}\vphantom{\dfrac00}\quad} \def\a#1{\quad\mathclap{#1}\quad} \colsep{0pt}{\begin{array}{l|c|c|c|c|c}\hline \tl{батарей}{по 6 В}&\a{34}&\a{26}&\a{18}&\a{10}&\a2\\\hline \tl{батарей}{по 16 В}&\a1&\a4&\a7&\a{10}&\a{13}\\\hline \end{array}} $$- Здесь дело сводится к решению уравнения
$6x+15y=220$. Однако$\gcd(6,15)=3$, а 220 не делится на 3. Поэтому уравнение не имеет решений в целых числах.
- Сумма чётного числа нечётных чисел чётна, поэтому 45 рублей нельзя разменять указанным способом.
- Поскольку
$a=bd$ и делится на$c$, а$\gcd(b,c)=1$, то по лемме 3 число$d$ делится на$c$. - б), в) и г) верны; а) неверно.
$1971=3^3\cdot43$; $1972=4\cdot17\cdot29$; 1973 — простое.-
- Если
$am$ делится на$n$ и$\gcd(m,n)=1$, то$a=kn$, поэтому$b=km$. - Пусть в разложении
$x$ на простые множители некоторое простое$p$ входит в степени$a$, а в разложении$y$ — то же$p$ в степени$b$. Тогда из теоремы о единственности разложения на простые множители$am=bn$ и из задачи а) следует, что$a=kn$, $b=km$. В разложение$t$ на простые множители включим$p$ с показателем$k$, и так — для всех простых множителей чисел$x$ и$y$.
- Если