Главная » Просмотр файлов » Дж. Андерсон - Дискретная математика и комбинаторика (2004)

Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 51

Файл №1127091 Дж. Андерсон - Дискретная математика и комбинаторика (2004) (Дж. Андерсон - Дискретная математика и комбинаторика (2004)) 51 страницаДж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091) страница 512019-05-11СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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.

Характеристики

Тип файла
DJVU-файл
Размер
7,96 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6384
Авторов
на СтудИзбе
308
Средний доход
с одного платного файла
Обучение Подробнее