23.12.2015 Шеина Г.В. Теория и практика решения задач по алгебре, часть 1

ствию из леммы, существует Н. О. Д. ( , ) и при этом

Н. О. Д. ( , ) = Н. О. Д. ( −1, ) = .

Линейное выражение Н.О.Д. двух чисел через исходные числа

Пусть имеются три целочисленные переменные величины , , . Будем гово-

рить, что выражается линейно через переменные и с целыми коэффициен-

тами и , если можно представить в виде = + .

Покажем, что наибольший общий делитель чисел и можно выразить линей-

но через эти числа, то есть для некоторых целых чисел и справедливо ра-

венство Н. О. Д. ( , ) = + .

Заметим сначала, что если выражается линейно через переменные и с целыми коэффициентами, а величины и выражаются линейно через пере-

менные 1 и 1 с целыми коэффициентами, то величина выражается линейно через переменные 1 и 1 с целыми коэффициентами.

Проиллюстрируем это на числовом примере.

Пусть = 2 − 3 , = 41 − 2 1, = 51 − 6 1. Тогда= 2 − 3 = 2 ∙ (41 − 2 1) − 3 ∙ (51 − 6 1) = −71 + 14 1.

Мы видим, что выражается линейно через переменные 1 и 1 с целыми ко-

эффициентами.

Проверим теперь, что любой остаток в алгоритме Евклида для нахождения вы-

ражается линейно через числа и .

Действительно, = 1 + 1 1 = − 1, то есть первый остаток выразился линейно через числа и . Для второго остатка имеем

= 1 2 + 2 2 = − 1 2 = − ( − 1) 2 = (1 + 1 2) − 2 ,

то есть снова имеем линейное выражение.

Кроме того, поскольку

−1 = ∙ +1 + +1 +1 = −1 − ∙ +1,

31

общий делитель можно также находить по алгоритму Евклида, и он выражается линейно с целочисленными коэффициентами через исходные числа. Мы будем использовать обозначение Н. О. Д. ( , ) для положительного наибольшего де-

лителя целых чисел.

Взаимно простые числа

Определение. Целые числа и называются взаимно простыми, если 1 яв-

ляется их наибольшим общим делителем (при этом −1 также является их наибольшим общим делителем).

Следствие 1 из алгоритма Евклида (критерий взаимной простоты).

Целые числа и взаимно просты тогда и только тогда, когда существуют такие целые числа и , что + = 1.

+ = 1, то любой общий делитель чисел и должен быть также делите-

лем 1. Значит, и наибольший общий делитель должен быть также делителем 1 и

может быть равен только 1 или −1. Поэтому числа и взаимно просты.

Определение. Натуральное число, отличное от единицы, называется про-

стым, если оно делится (нацело) только на себя и на единицу.

Замечание. Если одно простое число делится на другое простое число, то они

равны.

Следствие 2 (делимость произведения на простое число). Если произведение нескольких целых чисел делится на простое число, то хотя бы одно из них де-

лится на это простое число.

33

Доказательство. Проверим утверждение следствия для двух сомножителей.

Пусть − простое число и | . Если | , то все доказано. Рассмотрим слу-

чай, когда не является делителем .

Поскольку число – простое и общим делителем чисел и может быть только число 1 или p , то Н. О. Д. ( , ) = 1.

Отсюда следует, что существуют такие целые числа и , что

+ = 1. Умножив последнее равенство на число , получаем

+ = . Поскольку | , то из делимости обоих слагаемых левой части на число следует, что | , и все доказано.

Пусть утверждение следствия доказано для сомножителей. Проверим спра-

Основная теорема арифметики

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

ности такого разложения. Возможность и единственность разложения устанав-

ливается в следующей теореме, которую обычно называют основной теоремой арифметики.

Теорема (основная теорема арифметики). Всякое натуральное число , от-

личное от единицы, представимо в виде произведения простых сомножите-

лей. Это представление единственно с точностью до перестановки простых сомножителей (произведение может содержать один сомножитель).

Доказательство. Пусть . Доказательство будем вести индукцией по .

Если = 2 , то теорема верна и в разложении имеется один простой сомножи-

тель. Пусть утверждение доказано для натуральных чисел, не меньших, чем 2,

34

но меньших , то есть 2 ≤ < . Докажем справедливость утверждения тео-

ремы для случая = . Если – простое число, то все доказано:

произведение в этом случае состоит из одного сомножителя и

представление единственно в силу того, что простое число, делящее другое простое число, равно ему.

Если – не простое число, то = = ∙ , причем справедливы неравенства

1 < < , 1 < < . По предположению индукции числа и можно пред-

ставить в виде произведения простых чисел и тем самым представить число в

нужном виде.

Единственность. Пусть имеется два разложения числа на простые сомножи-

Индукция по числу .

База индукции. Если = 1, то доказываемое утверждение примет вид

простое число 1. Поэтому одно из чисел произведения 1 ∙ … ∙ делится на простое число 1 и, значит, ему равно. Перенумеруем сомножители в правой части равенства так, чтобы это число стало первым в произведении. Тогда можно считать, что 1 = 1. Сократив равенство на сомножитель 1, имеем следующее.

Если = 2, то 1 = 2 , что невозможно.

Для > 2 будем иметь: 1 = 2 ∙ … ∙ . Поскольку 2, … , – простые числа, это также невозможно.

35

Значит = 1, то есть сомножители 2, … , в равенстве отсутствуют.

Индукционный шаг. Пусть единственность разложения установлена для всех случаев, когда число m сомножителей в правой части равенства меньше или равно числу . Докажем единственность для +1 сомножителя в левой части равенства. Из равенства следует, что какое-то из чисел произведения

1 ∙ … ∙ делится на 1. Перенумеровав, если нужно числа 1, … , , будем считать, что это число 1.

Поскольку оба числа 1 и 1 – простые, то 1 = 1, и мы имеем равенство

1 ∙ … ∙ +1 = 1 ∙ 2 ∙ … ∙ .

Сократив его на множитель 1, получим: 2 ∙ … ∙ +1 = 2 ∙ … ∙ . Число сомножителей в левой части уменьшилось и можно применить предположение индукции. По предположению индукции получаем, что +1= , а левая и пра-

вая часть равенства 2 ∙ … ∙ +1 = 2 ∙ … ∙ отличаются только перестановкой сомножителей.

Следствие. Любое натуральное число , отличное от единицы, можно един-

Такая запись называется каноническим разложением числа .

Решение задач на делимость

Задача 1. Пусть – натуральное число, большее 2. Докажите, что между чис-

лами и ! содержится, по крайней мере, одно простое число. Покажите, что отсюда следует бесконечность множества простых чисел.

Решение. По условию задачи > 2, поэтому целое число = ! − 1 больше 1.

Если оно простое, то, поскольку

∙ (( − 1)! − 1) > 1 ! − > 1 ! − 1 > при > 2,

число = ! − 1 находится между числами и !, и все доказано.

36

Если число = ! − 1 не простое, то оно имеет, по меньшей мере, один про-

стой делитель , для которого < ! − 1 < !. Если допустить, что при этом ≤ , то – делитель произведения 1 ∙ 2 ∙ … ∙ и делитель числа = ! − 1. Поэтому – делитель их разности ! − , что невозможно, поскольку

! − = 1. Следовательно, > и < !.

Если бы простых чисел было конечное число, то все они были бы меньше само-

го большого простого числа , что противоречит первому утверждению за-

дачи: существует хотя бы одно простое число, больше чем .

Задача 2. Докажите, что число ( − 1)! не делится на число только в том случае, когда − простое или = 4.

Решение.

1.Если − простое, то числа и ( − 1)! взаимно просты. Поэтому ( − 1)!

не делится на число .

2.Пусть теперь составное число. Возможны следующие случаи.

а. Число не является степенью простого числа. Тогда в разложении имеется, по крайней мере, два разных простых сомножителя.

Поэтому = , где числа и взаимно просты, 1 < , < . Числа и различны и находятся среди чисел {2, … − 1} . Следовательно, они являются сомножителями в произведении ( − 1)! . Значит, ( − 1)! де-

лится на число = .

б.Число есть степень простого числа: = , где − простое, причем> . Поскольку ≠ −1 , числа , −1 меньше числа и оба находятся среди чисел {2, … − 1}. Тогда число ( − 1)! делится на ∙−1 = , как и в предыдущем пункте.

в. Число есть квадрат простого числа, отличного от двух, = 2, ≠ 2.

В этом случае 2 < 2 = и , 2 {2, … − 1} . Поэтому ( − 1)! де-

лится на ∙ 2 = 2 .

37

Рассмотренные выше случаи показывают, что в случае составного числа

, отличного от 4, число ( − 1)! делится на число .

г. Остался случай = 22 , для которого утверждение задачи верно, по-

скольку число ( − 1)! = 3! не делится на число = 4.

Задача 3. Докажите, что число 11 − 1 делится на 10. При каких значениях число 11 − 1 делится на 100?

Решение. По формуле суммы геометрической прогрессии имеем

Выясним, при каких значениях число 11 − 1 делится на 100. Для этого заме-

тим, что, раскрыв скобки в выражении ( + 1) = ( + 1) ∙ … ∙ ( + 1), получим

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

емые содержат множитель 2, то есть ( + 1) = 1 + + 2 , где , если . Применим это к числу

11 − 1:

11 − 1 = (10 + 1) − 1 = 1 + 10 + 102 − 1 = 10 + 102 .

Отсюда видно, что делимость числа 11 − 1 на 100 равносильна делимости на

10 числа .

Ответ: число 11 − 1 делится на 100 тогда и только тогда, когда делится на

10.

Задача 4. Докажите, что среди чисел вида 4 + 3, имеется бесконечно много простых чисел.

Решение. Заметим сначала, что

38

остаток от деления простого числа, не равного 2, на 4 есть либо 1,

либо 3;

произведение чисел вида 4 + 1 снова даст число такого же вида; для

этого достаточно перемножить (4 + 1) и(4 + 1):

(4 + 1) (4 + 1) = 16 + 4 + 4 + 1 = 4(4 + + ) + 1.

Поэтому в разложении числа вида 4 + 3 на простые сомножители обязательно встретится число такого же вида 4 + 3. Например, число 15 имеет вид 4 + 3,

а именно 15 = 4 ∙ 3 + 3, в его разложении сомножитель 3 также имеет вид

4 ∙ 0 + 3.

Предположим теперь, что простых чисел вида 4 + 3, конечное число.

Перечислим их:

проверить, что число можно записать в виде 4 + 3, . Поэтому в его разложении на простые сомножители имеется хотя бы одно простое число та-

кого же вида 4 + 3. Значит, число должно делиться на одно из чисел, пере-

численных в списке .

Но это невозможно, поскольку первое слагаемое в записи числа делится на любое из чисел списка , а второе слагаемое, то есть 2, не делится ни на одно из этих чисел.

Задача 5. Найдите все простые числа , для которых числа + 10 и + 14 —

простые.

Решение. Если не делится на 3, то одно из чисел + 10 = + 1 + 9 или

+ 14 = + 2 + 12 делится на 3 (из трех последовательных чисел ,

+ 1 и + 2 ровно одно число делится на 3). Поэтому + 10 и + 14 не яв-

39

ляются простыми.

Значит, делится на 3. Поскольку число – простое, то = 3.

Задача 6. Остаток от деления некоторого натурального числа равен 3, а остаток от деления этого же числа на 15 равен 1. Найти остаток от деления этого числа на 30.

Ошибочное решение. Обозначим число, о котором идет речь в условии задачи символом . С учетом условия задачи можно написать = 6 + 3,

= 15 + 1, , . Тогда 4 = 60 + 4, а 5 = 30 + 15. Вычтем из числа

5 число 4 и получим = 30( − 2 ) + 11. Отсюда делаем вывод, что оста-

ток от деления числа на 30 есть 11.

Ответ, к которому мы пришли, все же нельзя считать правильным. Действи-

тельно, поскольку = 6 + 3, = 15 + 1, , , то 6 + 3 = 15 + 1 или

6 + 3 − 15 = 1. Последнее равенство невозможно ни для каких целых чисел

и (левая часть равенства делится на 3, а правая не делится).

Таким образом, чисел , о которых идет речь в задаче, не существует. Правиль-

ным был бы ответ: чисел, о которых идет речь в задаче не существует, поэтому у них нет никакого остатка при делении на 30.

Задача 7. Остаток от деления некоторого натурального числа равен 3, а остаток от деления этого же числа на 15 равен 6. Найти остаток от деления этого числа на 30.

Решение. Обозначим число, о котором идет речь в условии задачи символом .

С учетом условия задачи можно написать

= 6 + 3, = 15 + 6, , . Тогда 6 + 3 = 15 + 6 2 + 1 = 5 + 2 = 5 2+1. Числа, соответствующие та-

кому условию, существуют, например:

= 1 = 3, число равно 21;

= 3 = 8, число равно 51;

при четном числе число = 5 2+1 не является целым.

40