Великая теорема Ферма: история и обзор подходов к доказательству
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
В этом параграфе напомним основные факты о делимости целых чисел и сравнимости по модулю.
Если a, b Z , b 0, то говорят, что b делит a или a кратно b, если a = bq для некоторого q Z. В этом случае пишут a M b или b | a .
Примеры: 1. 156 M 52, т.к. 148 = 523.
2. -143 52, т.к. -143 = 52(-3) + 13, т.е. -143 даёт остаток 13 при делении на 52.
Упомянем важнейшие свойства делимости нацело:
10. Если a | b и c | d , то ac | bd. В частности, верно a | bc, ac | |bc|, |ac| | bc , (a) | (b) при любой независимой друг от друга расстановке знаков у чисел a и b.
20. Если a | b1 , … , a | bk , то a | (b1c1+ …+bkck ) для любых целых чисел c1 , … , ck .
30. Если a 0, b | a, то |b| |a|. В частности у каждого ненулевого целого числа лишь конечное число делителей.
Пусть a1 , … , an - целые числа, одновременно не равные нулю. Их общим делителем называется любое целое число d, делящее все указанные числа. Наибольший среди всех общих делителей не равных одновременно нулю целых чисел a1 , … , an называется наибольшим общим делителем этих чисел и обозначается через НОД(a1 , … , an) или (a1 , … , an).
Примеры: НОД(0, 8) = 8, (12, 18) = 6, НОД(7, 9) = 1, (12, 40, 28) = 4, НОД(0, 0) не определён.
Общим кратным ненулевых целых чисел a1 , … , an называется любое целое число, делящееся одновременно на каждое из указанных чисел. Наименьшее положительное кратное этих чисел называется их наименьшим общим кратным и обозначаемое символом НОК[a1 , … , an] или просто через [a1 ,… , an].
Примеры: НОК[0, 2] не определено, [24, 16] = 48, НОК[4, 6] = 24, НОК[8, 6, 30] = 120.
В дальнейшем, имея дело с НОД(a1 , … , an) всегда будем молчаливо предполагать, что целые числа a1 , … , an одновременно не равны нулю, а имея дело с НОК[a1 , … , an] - что целые числа все a1 , … , an ненулевые.
Напомним важнейшие свойства наибольшего общего делителя и наименьшего общего кратного:
10. НОД(a1 , … , an) и НОК[a1 , … , an] определёны однозначно.
0. Для произвольной перестановки (i1 , … , in) символов 1, … , n справедливы равенства
НОД(a1 , … , an) = НОД(), НОК[a1 , … , an] = НОК[].
30. Справедливы равенства
НОД(a1 , … , an) = НОД(a1 , … , an), НОК[a1 , … , an] = НОК[a1 , … , an] при любых знаках в правых частях.
40. Если a | b, то НОД(a, b) = |a|, НОК[a, b] = |b|.
50. Для произвольного t Z справедливы равенства
НОД(a, b) = НОД(a, b - at) = НОД(a - bt, b).
60. Любой общий делитель d целых чисел а1 , … , an делит их наибольший общий делитель НОД(a1 , … , an), любое общее кратное K целых чисел а1 , … , an делится на их наименьшее общее кратное НОК[а1 , … , an].
110. Справедливо равенство НОК[a, b] = .
Замечание. Обобщение НОК[a1 , … , аn] = доказанной формулы на случай любого числа сомножителей неверно. Например,
НОК[2, 4, 6] = 12 = 24.
0. Справедливы формулы
(a1 , … , an) = ((a1 , … , an-1), an), [a1 , … , an] = [[a1 , … , an-1], an],
из которых следует, в частности, что вычисление НОД(a1 , … , an) и НОК[a1 , … , аn] сводится к последовательному вычислению аналогичных величин для двух чисел:
(a1 , … , an) = (((…((a1 , a2), a3), … ), an-1), an).
[a1 , … , an] = [[[…[[a1 , a2], a3], … ], an-1], an].
140. Для любого ненулевого с Z верны формулы
НОД(ca1 , … , can) = |c|НОД(a1 , … , an),
НОК[ca1 , … , can] = |c|НОК[a1 , … , an].
Как известно, НОД(a, b) удобно вычислять с помощью алгоритма Евклида.
Примеры: 1. Вычислить НОД(244, 356).
Таким образом, НОД(244, 356) = 4 - последнему ненулевому остатку в алгоритме Евклида.
2. Вычислить НОД(244, 356, 96).
Имеем НОД(244, 356, 96) = ((244, 356), 96) = (4, 96) = 4.
3. Вычислить НОК[35, 50, 20].
Имеем НОК[35, 50, 20] = [[35, 20], 50] = = [140, 50] = = 700, т.к. НОД(35, 20) = 5НОД(7, 4) = 51 = 5 и [140, 50] = 10[14, 5] = = 1070 = 700.
Целые числа a1 , … , an называются взаимно простыми (в совокупности), если НОД(a1 , … , an) = 1. Они называются попарно взаимно простыми в случае, когда НОД(ai , aj) = 1 (1 i < j n).
Примеры: 1. Числа 6, 4, 3 взаимно просты в совокупности, но не попарно.
2. Ч