Делимость чисел. Делимость_чисел. Федеральное государственное бюджетное образовательное учреждение высшего образования орловский государственный университет имени И. С. Тургенева панюшкин св, Козичева Л. М. Делимость чисел в курсе алгебры
 Скачать 0.9 Mb.
|
|
* . Докажите, что число 0 1 2 3 a a a a M , тогда и только тогда 1) делится на 99, когда число 0 1 2 3 a a a a делится на 99; 2) делится на 101, когда число 0 1 2 Решение 1) Представим число М в виде ). ( 99 100 0 1 2 3 2 3 0 1 2 3 a a a a a a a a a a M а) Пусть число М делится на 99. Тогда по утверждению число 2 3 0 1 2 3 99 a a M a a a a также делится наб) Если ) ( 99 0 1 2 3 a a a a , то и число 2 3 0 1 2 3 99 ) ( a a a a a a M по утверждению делится на 99. 2) Представим М в виде ). ( 101 100 2 3 0 1 2 3 0 1 2 3 a a a a a a a a a a M а) Пусть М делится на 101. Тогда по утверждению 1, число 2 3 2 3 0 1 101 М делится на 101, а это возможно, если 0 2 3 0 1 a a a a б) Если , 0 101 2 3 0 1 a a a a то и число ) ( 101 2 3 0 1 2 3 a a a a a a M делится на 101. Значит, 0 1 2 3 a a a a - 25 - Задача 3.6 * . Докажите, что число 0 1 2 a a a тогда и только тогда делится на 8, когда число 2 0 1 2 a a a делится на 4. Используя эту задачу, сформулируйте еще один признак делимости на 8. 5. Простые и составные числа. Каждое натуральное число а, большее 1, имеет, по крайней мере, два делителя и а. Число а называется простым, если у него нет других делителей, и составным, если они есть. Число 1 не является непростым, не составным. Вот первые 10 простых чисел 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Составные числа можно разложить в произведение простых чисел. Простые числа, по определению, не разлагаются в произведение меньших чисел. Методическое указание о разложении на простые множители. Пусть нам дано составное число а. Мы можем разложить его в произведение двух множителей, меньших а. Если среди них есть хотя бы один непростой, то мы можем и его разложить в произведение двух множителей. Если среди них опять будут составные, они опять разлагаются на множители и т.д. Пример 1. 4 48 12 6 2 2 2 2 3 3 2 2 2 2 6 2 2 2 12 4 48 - 26 - Этот процесс не может продолжаться бесконечно, т. к. каждый сомножитель меньше самого числа. В нашей схеме на каждом этаже числа меньше, по крайней мере, вдвое, чем на предыдущем этаже. В результате мы придем к разложению на простые множители. А теперь докажем строго теорему о разложении числа на простые множители, которую часто называют основной теоремой арифметики. Теорема 1. Каждое натуральное число большее 1 можно разложить в произведение простых чисел. Два разложения натурального числа на простые множители могут различаться друг от друга только порядком следования множителей. Доказательство Докажем возможность разложения. Пусть а – составное число. Тогда его наименьший делитель, отличный от единицы, есть число простое. Обозначим его 1 r , тогда 1 a r a где Если простое, то теорема доказана. Если же составное, то оно имеет наименьший простой делитель : 2 r , 2 2 1 a r a и тогда ) ( 2 2 1 2 2 Если простое, то теорема доказана. Если же составное, то применяем к нему те же рассуждения, что и к числу Этот процесс не может быть бесконечным. Действительно, числа , , 2 убывают, оставаясь целыми положительными. Атак как количество этих чисел не больше, чем а, то после повторения наших рассуждений некоторое число раз n ( a n ) получим, наконец, разложение , 1 2 1 n n r r r r a в котором последний множитель будет простым числом. Таким образом, будет получено разложение числа а на простые множители. Докажем теперь единственность разложения. Предположим, что возможно , по крайней мере, два разложения числа а на простые множители n r r r a 2 1 и k q q q a 2 1 - 27 - Тогда будем иметь 2 1 2 1 n k r r r q q q (*) Из этого равенства следует, что произведение , ) ( 1 а если произведение простых чисел делится на простое число 1 q , то, по крайней мере, один из сомножителей равен числу Пусть, например, 1 1 q r Сократим равенство (*) на 1 Получим такое равенство 3 2 3 Рассуждая аналогично, получим 3 3 2 2 , q r q r и т. д. Очевидно, что и число сомножителей в левой и правой частях равенства (*) одинаково, те. В противном случае, после некоторого числа сокращений водной из частей равенства (*) получили бы один, а в другой части – произведение нескольких простых чисел, чего быть не может. Ч. т. д. Методическое указание. Перед доказательством основной теоремы арифметики полезно доказать следующие утверждения. Утверждение 1. Наименьший делитель составного числа, отличный от единицы, есть число простое. Утверждение 2. Если произведение ab, где аи простые числа, делится на r, то, по крайней мере, один из сомножителей равен r. Обычно равные простые множители собирают вместе и записывают разложение так 3 2 48 4 Такую запись разложения на простые множители называют канонической. В общем случае каноническое разложение числа на простые множители имеет вид m k m k k p p p p p p a m , , , , 2 1 2 1 2 1 простые числа. Чтобы начать процесс разложения данного числа а в произведение простых, нужно найти хотя бы один простой множитель. Никакого простого способа для этого не существует если про а заранее ничего неизвестно, то приходится перебирать простые числа и по очереди испытывать, делятся лиана и т. д. - 28 - Пример 2. Разложим число 2004 на простые множители. Число 2004- четное, следовательно, делится на 2, атак же делится на 4 (по признаку делимости на 4). 501 4 2004 . По признаку делимости на 3, 501 можно разделить на 3: 167 3 501 Пробуя делить 167 на 7, 11, 13, получаем, что 167 на данные числа не делятся. Далее можно не пробовать, т. к. , 167 289 17 2 те простое. Итак, 167 3 2 2004 Ответ 167 3 2 2004 Задача 4.1. Доказать, что наименьший из неравных единице делителей составного числа а не больше, чем a Решение. Из того, что , b a следует, что , bq a где q a Так как, по условию то и объяснить почему. Но b – наименьший из всех таких делителей, поэтому q b и , 2 a bq b те. Следствие. Если число 2 a не делится ни на одно простое число, не большее чем a , то оно само является простым числом. Пример 3. Установим, что 257 – простое число. Решение Для этого достаточно проверить, что оно не делится ни на одно простое число, такое, что 257 , 257 Из признаков делимости сразу следует, что 257 не делится на 2, 3, 5. Проверяем последовательно, что оно не делится на 7, 11 и 13. Этим можно и ограничиться, т. к. следующее простое число равно 17, а 257 289 17 Задача 4.2. Разложите на простые множители числа 1997, 1998, 1999, 2002, 11!= 11 10 Задача 4.3. Разложите на простые множители число 1 2 24 - 29 - Указание. Это число делится на 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1 2 4 4 6 6 12 и т.п. Задача 4.4*. Доказать, что число 4 4 k составное (натуральное число 0 k ). Указание. С помощью выделения полного квадрата и разложения по формуле разность квадратов, приходим к произведению двух множителей. Задача 4.5*. Докажите, что если р – простое число, р, то 1 2 p делится на 24. Доказательство. ). 1 )( 1 ( 1 Числа последовательные простые числа, поэтому одно из них делится на 4, а произведение – на 8. Из трех последовательных чисел ) 1 ( , ), 1 ( р р p одно делится на 3 (но это не р. Теорема 2. Множество простых чисел бесконечно. Доказательство проведем методом от противного. Допустим, что множество простых чисел конечно и что n n p p p p , , , , 1 2 1 все простые числа. Рассмотрим число Р, н единицу большее произведения всех простых чисел 1 1 2 Это число больше каждого из простых чисел , , , , 1 2 1 n n p p p p Поскольку мы предположили, что других простых чисел, кроме n n p p p p , , , , 1 2 1 нетто число P – составное. Следовательно, оно делится на некоторое простое число Однако ив произведение n n p p p p 1 входит и сомножитель Поэтому , 1 но 1 k p не Таким образом, 1 1 2 не Итак, одновременно , k k p не P и p P что невозможно- Следовательно, наше предположение о том, что существует лишь конечное множество простых чисел, было неверным, то есть множество простых чисел бесконечно. Ч. т. д. Это доказательство содержалось еще в сочинениях Евклида. Следующим вопросом, который возникает при изучении простых чисел, является вопрос о том, как из множества натуральных чисел выделить множество простых чисел, те. как составить таблицу простых чисел Этот вопрос интересовал еще математиков древности. Уже в глубокой древности занимались составлением таблиц простых чисел. Однако, данный вопрос одним из труднейших в теории чисел. Парадокс заключался в том, что в натуральном ряду есть сколь угодно большие промежутки, не содержащие простые числа. С другой стороны, встречаются простые числа, различающиеся на 2. Это - числа- близнецы. Первая попытка найти все простые числа приписывается выдающемуся астроному и математику Эратосфену, жившему в 276 – 192 г. до нашей эры. Этот способ состоит в следующем. Пусть, например, требуется составить таблицу простых чисел, не превосходящих 50. Запишем подряд все натуральные числа от 1 до 50. Зачеркнем 1, которая не является простым числом. Следующее число 2 – простое, его не зачеркиваем. Зачеркнем далее каждое второе число, после 2, таким образом, будут зачеркнуты все числа, кратные 2 (4, 6, 8, …, 48, 50). Число 3 оказалось незачеркнутым, оно – простое. Вычеркнем каждое третье число, стоящее правее 3; то. будут зачеркнуты все числа, кратные 3 (6, 9, 12, …), не пропуская и те, которые были зачеркнуты. Следующим незачеркнутым числом оказалось число 5. Оно – простое, его оставляем. Далее зачеркиваем все числа, кратные 5 (каждое пятое число. Продолжая так далее, получим незачеркнутыми лишь простые числа, а все составные будут зачеркнуты. - 31 - 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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 Процесс вычеркивания можно остановить на вычеркивании чисел, кратных (объяснить, почему. Этот метод отсеивания чисел известен как решето Эратосфена». В эпоху жизни и деятельности Эратосфена писали на папирусе, натянутом на рамку, или на восковой дощечке, и не зачеркивали, а прокалывали составные числа. Получалось нечто вроде решета, через которое просеивались составные числа. Поэтому таблицу простых чисел, составленную таким образом и назвали решетом Эратосфена». Вопрос о простых числах – один из самых интересных вопросов в математике. Поиском рекуррентных формул для нахождения всех простых чисел занимались такие ученые, как Мерсен, П. Ферма, ПЛ. Чебышев. Свой вклад в развитие данного вопроса внесли также Л. Эйлер, Гольдбах, Бертран, ИМ. Виноградов, ИМ. Первушин, ИК. Андронов и др. История простых чисел интересна и познавательна. В настоящее время существует много литературы, в которой история простых чисел освещается доступно и увлекательно. Для оживления изложения учителю полезно привлекать сведения исторического характера или предложить учащимся написать доклад по теме. - 32 - Рекомендуемая литература Депман И. Я. История арифметики- М Просвещение, 1965. Маркушевич АИ. Дополнительные вопросы арифметики целых чисел Математика в школе, 1967, №4. Мурадова Е. Простые числа. Так ли проста их история Математика Муромцева ЛИ. Дополнительные вопросы арифметики целых чисел- Орел ОГПИ, 1968. Серпинский В. Что мы знаем и чего мы не знаем о простых числах Физматгиз, 1963 Шнирельман Л. Г. Простые числа- МЛ Гостехиздат,1940. Задача 4.6. Составьте таблицу всех простых чисел, меньших 200 (воспользуйтесь методом Эратосфенова решета. Подсчитайте, сколько всего простых чисел среди чисел первой сотни, среди чисел второй сотни. 6. Наибольший общий делитель и наименьшее общее кратное двух чисел. Взаимно простые числа. Каждый делитель натурального числа а не может быть больше самого числа а поэтому число а имеет конечное число делителей, не превосходящих а. Среди делителей чисел аи могут быть одинаковые, те. общие делители. Очевидно, их число также является конечным. Например, числа 30 и 70 имеют 4 общих делителя 1, 2, 5, 10. Среди этих делителей есть наибольший в нашем случае 10), его называют наибольшим общим делителем и обозначают НОД(а, b) или Итак, наибольшим общим делителем двух натуральных чисел называется наибольшее натуральное число, на которое делится каждое изданных чисел. Понятие общего делителя двух чисел тесно связано с понятием их общего кратного. - 33 - Общим кратным двух натуральных чисел аи называется число, которое делится на каждое из этих чисел. Ясно, что произведение b a будет кратным чисел аи, а значит, и а, 3ab, 4ab, … также будут кратными этих чисел. То, каждые два натуральных числа имеют сколько угодно общих кратных, среди них нет наибольшего, но есть наименьшее. Его называют наименьшим общим кратными обозначают НОК(a,b) или Итак, наименьшим общим кратным чисел аи называется наименьшее целое положительное число, которое делится на каждое из чисел аи. Аналогично определяются наибольший общий делитель и наименьшее общее кратное нескольких натуральных чисел. При этом справедливы равенства Доказательство предложенных ниже основных свойств наибольшего общего делителя и наименьшего общего кратного может быть оставлено на самостоятельное рассмотрение учащихся. 1. Наибольший общий делитель двух чисел делится на любой их общий делитель. 2. Если N b a , умножить на , N k то их наибольший общий делитель увеличится враз. Множество общих делителей чисел a и b совпадает с множеством делителей их НОД. 4. Если каждое из чисел N b a , разделить на их общий натуральный делитель k, то их НОД разделится на k. 5. Любое общее кратное делится на их наименьшее общее кратное. 6. Если числа N b a , умножить на то их наименьшее общее кратное увеличится враз. Если каждое из чисел N b a , разделить на их общий натуральный делитель k, то их НОК разделится на k. Натуральные числа аи называют взаимно простыми, если наибольший общий делитель этих чисел равен 1, те. Например, взаимно просты числа 15 и 77. Всегда взаимно просты два соседних натуральных числа (например, 20 и 21). В самом деле, если бы оба числа делились на одно и тоже натуральное число m>1, то их разность тоже делилась на m и потому не могла бы равняться 1. Рассмотрим теорему, устанавливающую связь между НОД(а, b) и НОК(а, b). Задача 5.1. Докажите, что если d b b d a a d b a D 1 1 , , ) , ( , то числа 1 1 , b a взаимно простые. Теорема 1. Частное отделения произведения b a натуральных чисел аи на их набольший общий делитель d есть целое число, являющееся наименьшим общим кратным. ) , ( ) , ( b a D b a b a К Доказательство. Пусть М – произвольное общее кратное. , , bl M ak M b M a M Используя результаты задачи 5.1, имеем 1 ) , ( , , , , ) , ( 1 1 1 Рассмотрим отношение 1 целое число , 1 1 b k a ат. кто То. каждое общее кратное может быть выражено по последней формуле при соответствующем значении Очевидно обратное, любое число, выраженное по последней формуле, является общим кратным двух чисел. То, последняя формула дает общий вид всех общих кратных чисел аи. Наименьшее положительное из них получается при t=1. Ч. т. д. Из свойств наибольшего общего делителя и наименьшего общего кратного двух чисел вытекают следующие утверждения 1. Наименьшее общее кратное двух взаимно простых чисел равно их произведению. В самом деле, из того, что , 1 ) , ( b a D следует Вообще говоря, из того , что число а делится на b и делится нас, нельзя вывести, что число делится на bc (например, 6 60 , 4 60 , ноне делится на 24 6 4 Иначе обстоит дело, если делители взаимно просты. 2. Если числа b и с взаимно просты, причем , , c a b a то В самом деле, если , , c a b a то (объяснить, почему) ). , ( с Но для взаимно простых чисел b и с поимеем ) , ( сb b с K Значит, Наконец, докажем следующее утверждение 3) Если a и b взаимно просты, причем произведение ас делится на b, то с делится на b. В самом деле, по условию, 1 ) , ( b a D и ас Поскольку ас по утверждению) получаем ас тогда с (объяснить, почему. |