Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 51
Текст из файла (страница 51)
1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12, 13,14,1Б,16,17,18,!9, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, ЗЗ, 34, ЗБ, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, Б1, 52, 53, Б4, ББ, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100 Далее отмечаем все числа, кратные простому числу 7. 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 11,12, 13,14,15,16, 17,18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, ЗЗ, 34, 35, 36, 37, ЗВ, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, Б2, 53, 54, 55, 5Б, 57, БВ, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 9Б, 96, 97, 98, 99, 100 ° УПРАЖНЕНИЯ 1.
Постройте решето Эратосфена для положительных 200. 2. Используйте решето Эратосфена и калькулятор для множители числа 1726. 3. Используйте решето Эратосфена и калькулятор для множители числа 481. 4. Используйте решето Эратосфена и калькулятор для множители числа 2502. 5. Используйте решето Эратосфена и калькулятор для множители числа 1739. 6.
Используйте решето Эратосфена и калькулятор для множители числа 391. 7. Используйте решето Эратосфена и калькулятор для множители числа 3901. целых чисел, меньших разложения на простые разложения на простые разложения на простые разложения на простые разложения на простые разложения на простые Поскольку 7 — наибольшее простое число, квадрат которого меньше или равен 100, по теореме 3.41 продолжать процесс нет необходимости.
Числа, большие 1 и не отмеченные жирным шрифтом, представляют собой простые числа, которые не превышают 100. 300 Г71АИА 7. Теория чисел 7.2. МЕТОД ВЫДЕЛЕНИЯ МНОЖИТЕЛЕЙ ФЕРМА Следущая теорема является основой алгоритма разложения на простые множители, названного методом выделения множителей Ферма. Метод используется для определения того, является ли число простым. ТЕОРЕМА 7.1. Целое нечетное число и > 1 не является простым тогда и только тогда, когда существуют неотрицательные целые числа р и д такие, что и = р — д~, и при этом р — д > 1.
Очевидно, если и можно представить как разность квадратов двух неотрицательных целых чисел, скажем, и = рз — дз, тогда и = (р — д)(р+д). Поскольку р — д > 1, то также р+ д > 1; и и не является простым числом. Обратно, если и = тз, где т > а > 1, тогда и можно представить как ((т+з)/2)з — Ит — з)/2)з. Поскольку и нечетное, т и а также являются нечетными и, следовательно, т+и и т — з — четные числа.
Положив р = (т+и)/2 и д = (т — з)/2, находим, что р и д — целые неотрицательные числа и р — д = з > 1. При и = 1 положим р=1, а д=0. Применение этого метода состоит в попытке найти целые числа р и д такие, что и = рз — дз или, что эквивалентно, рз = и + дз, или дз = рз — и. Если используется первое уравнение, полагаем д = 1,2,... до тех пор, пока и + дз не станет полным квадратом.
Если до значения д = (и — 1)/2 полный квадрат не достигнут, рассмотрим ситуацию, когда д = (и — 1)/2, что дает и+да = Ии+1)/2)з и приводит к разложению и на множители и 1. Поскольку д имеет вид (т — з)/2, где т и а — делители и, то очевидно, что д не может превысить (и — 1)/2. Следовательно, если до значения д = (и — 1)/2 полный квадрат не достигнут, число и является простым. При использовании второго уравнения, т.е. дз = рз — и, берем в качестве т наименьшее целое число такое, что тиз > и, и последовательно полагаем, р = т, ти+1,... до тех пор, пока рз — и не станет полным квадратом. Как и прежде, д не может превысить (и — 1)/2, так что если до значения р = (и+ 1)/2 полный квадрат не получен, число и является простым. Преимущество использования второго соотношения состоит в том, что проверке на полный квадрат подлежит меньшее количество чисел.
Например, рассмотрим применение записи рз = и+да для проверки, является ли простым число и = 527. Рассмотрим д = 1, 2,..., (и — 1)/2. 527+ 1 = 528 527+ 4 = 531 527+ 9 = 536 527 + 16 = 543 527+25 = 552 527+ 36 = 563 527+ 49 = 576 = (24)з РАЗДЕЛ 7.3, Алгориглмы деления и алгоритм Евклида 301 Итак, и = 527 является составным, и его делители легко вычисляются: 527 (24)з 7г = (24 — 7)(24 + 7) = = 17 31. Решение вопроса о том, является ли число п простым, не всегда требует проверки всех значений д от 1 до (гг — 1)/2. ° УПРАЖНЕНИЯ Воспользовавшись методом выделения множителей Ферма, определите, являются ли следующие числа простыми.
1. 1001 2. 1349 3. 4851 4. 1079 5. 8051 6. 567 7. 7931 7.3. АЛГОРИТМЫ ДЕЛЕНИЯ И АЛГОРИТМ ЕВКЛИДА Ранее была доказана теорема, названная алгоритмом деления. Теорема гласила, что для положительных целых чисел а и Ь существуют единственные неотрицательные числа д и т такие, что 0 < т < Ь и а = Ьд+г. Это утверждение не является алгоритмом, но алгоритмы для нахождения д и т существуют. Если числа а и Ь велики, число д можно "угадать".
Если умножить Ь на д и результат слишком велик, следует д заменить на д — 1 и повторять процесс, пока не получим 6д < а, после чего положить т = а — Ьд. Однако, если Ьд < а, но а — Ьд > 6, то следует заменить д на д+ 1 и повторять процесс, пока не получим а — Ьд < Ь, после чего положить т = а — Ьд. Более системно метод описывается следующим образом: 1. Положить д = 1 и т = а — Ьд. 2. Если т > Ь, положить д = д + 1 и г = а — Ьд.
3. Продолжать процесс, пока г < Ь. Изложенное представляет собой алгоритм нахождения наибольшего общего делителя больших чисел, названный алгоритмом Евклида. Нахождение наибольшего общего делителя необходимо при сложении дробей, а также при решении уравнений в целых числах. ТЕОРЕМА 7.2. (Апгоритм Евклида) Допустим, что а и Ь вЂ” положительные целые числа, и последовательное применение алгоритма деления приводит к последовательности следующего вида; 302 ГПЛВА 7. теория чисел а = Ьдо+ то Ь = тог71 + Т1 ть = ть4.1чь+2 + ть.гз 0 < тьез < тье1 Существует ть = О.
Пусть з — первое целое число такое, что т, = О. Тогда т, 1 = НОД(а,Ь), если з > О, и Ь = НОД(а, Ь), если з = О. ДОКАЗАТЕЛЬСТВО. Пусть 5 = (го, т,,...). Если то = О, тогда результат очевиден, поэтому предположим, что то > О. Согласно принципу полного упорядочения множество 5 содержит наименьшее положительное целое число, скажем, г,.
Но 0 < Т,4.1 < го и поэтому т,+1 = О. Положим з =1+ 1. По теореме 3.33, НОД(а,Ь) = НОД(Ь,то) = НОД(то,т1) = ° ° ° = НОД(т 1,г ), но поскольку г,, = О, НОД(т, 1, г,) = т, 1, так что НОД(а,6) = г, ПРИМЕР 7.3. Используя алгоритм Евклида для нахождения НОД(203,91), дей- ствуем следующим образом. Сначала делим 203 на 91 нацело и получаем 203 = 91 2+ 21; а=Ь до+то Теперь делим 91 на остаток 21 нацело: 91 = 21 4+7; 6 = го 91 + г1. Разделяя 21 на 7 нацело, получаем 21=7 3+О; То = Т1 Я2 + Т2. Итак, з = 2 и НОД(203,91) = НОД(91,21) = НОД(21,7) = 7 = т, 1 — — т1. П то = Т1я2 + т2 Т1 = Т293 + Тз Т2 = ТЗГ44 + Т4 0 < то < Ь О < т1 < то 0<та <т1 0 < гз < Т2 0 < г4 < тз РАЗДЕЛ 7.3.
Алгоритмы деления и алгоритм Евклида 303 ПРИМЕР 7.4. Найти НОД(99, 205). Действуя вышеуказанным образом, делим 205 на 99 нацело, получая 205 = 99 2 + 7. Теперь делим 99 нацело на остаток 7, получая 99=7 14+1. Далее делим 7 на 1 и получаем 7=1 7+О.
Таким образом, НОД(99,205) = 1. Алгоритм Евклида позволяет находить такие значения и и и, что НОД(а, Ь) = г,, пи+ иЬ = НОД(а, Ь). Используя обозначения теоремы 7.2, запишем г, 2 —— тс-с.9с+гс Отсюда гс = тс-2 — тс-с с7с. Аналогично, тс с = тс-з — гс-2 с7с-с. Подстановка в предыдушее уравнение дает тс = тс 2 — (тс-3 — тс-2. с7с с) . с7с. Аналогичным образом можно выразить гс 2 через т, з и т, 4 и, подставив в предыдушее уравнение, исключить т, 2. Продолжая в том же духе, можно исключить все т, и вернуться обратно к а и Ь, получив НОД(а, Ь) в виде на+ иЬ. ПРИМЕР 7.5. Выразить НОД(85,34) в виде 85и+ 34и. Для использования алгоритма Евклида сначала разделим 85 на 34 нацело; 85 = 34 2+ 17. Разделяя 34 на 17 нацело, получаем 34=17 1+О.
Таким образом, НОД(85, 34) = 17 и НОД(85, 34) = 17 = (85)(1) + (34)( — 2). П ПРИМЕР 7.6. Выразить НОД(252,580) в виде 252сс+ 580и. Делим 580 на 252 нацело, получая 580 = 252 2 + 76; а = Ь с7о+ то. Теперь делим 252 нацело на 76: 252 = 76. 3+ 24; Ь=го с72+гс. Продолжая процесс, получаем 76 = 24. 3+4; то — тс 'Ч2+т2 304 Глдвл 7. теория чисел 24=4 6+О; т1 = тг дз + тз. Обратная подстановка дает 4 = 76 — 24. 3 = = 76 — [252 — 76 3] 3 = = 76 10+252 ( — 3) = = [580 — 252. 2[.
10+ 252 ( — 3) = 580 10+252 ( — 23), где т, выделены подчеркиванием. ПРИМЕР 7.7. Выразить НОД(252, 576) в виде 252и+ 576и. Сначала разделим 576 на 252 нацело: 576 = 252 . 2 + 72. Теперь разделим 252 нацело на 72: 252 = 72. 3+ 36. После обратной подстановки получаем 36 = 252 — 72. 3 = = 252 — [576 — 252 2[ 3 = = (7)(252) + (-3)(576). В примере 7.3 показано, что НОД(91,203) = 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
