АГ ПЗ 1-35 (полный вариант). Практическое занятие 1 Решето Эратосфена
 Скачать 2.3 Mb.
|
|
Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 1, с.8 1 Практическое занятие 1 Решето Эратосфена Краткое содержание: понятие делимости и его свойства, простые и составные числа, решето Эратосфена, основная теорема арифметики. п.1. Теория п.1.1. Понятие делимости целых чисел и его свойства Множество целых чисел будем обозначать прописной буквой Z, мно- жество натуральных чисел – буквой N. Сами целые числа будем обо- значать малыми (строчными) буквами латинского алфавита. Определение. Говорят, что целое число a 0 делит целое число b (целое число b делится на целое число a 0 ), если существует целое число с, такое, что b ac . Число а называется делителем числа b, а число b называется кратным числа а. Обозначение: a | b . Таким образом, по определению, для любых двух целых чисел a 0 и b, df a | b c Z : b ac Замечание. В записи a | b молчаливо будем предполагать, что числа а и b являются целыми, и число a 0 . Если число а не делит число b, то будем писать a | b . Теорема. (Свойства делимости целых чисел.) 1) Свойство рефлексивности. Для любого целого числа a 0 , a | a . 2) Свойство транзитивности. Если целые числа а, b и с таковы, что a | b и b | c , то a | c . 3) x Z, x 0, ax | bx a | b 4) Если a | b , то x Z, a | bx 5) Если a | n и a | m , то x, y Z, a | xn ym 6) Если a | n и b | m , то ab | nm . 7) Если a | b и b | a , то a b Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 1, с.8 2 Следствие. 1) Если a 0 , то a | 0 . 2) Если a | b , то a | ( b) . 3) Если a | n и a | m , то a | n m . 4) Если a |1, то a 1 п.1.2. Простые и составные числа Из определения делимости целых чисел следует, что любое целое число n 1 имеет, по крайней мере, два положительных делителя, это число 1 и само число n. Определение. Пусть n 1 . Числа 1 и n называются тривиальными (несобственными) делителями числа n. Все остальные положительные делители числа n, если они существуют, называются собственными делителями числа n. Другими словами, если 1 a n и a | n , то число а называется собст- венным делителем числа n. Определение. Натуральное число p 1 называется простым числом, если оно не имеет собственных делителей. В противном случае, целое число p 1 называется составным. Теорема. (О наименьшем собственном делителе.) Наименьший собст- венный делитель составного числа является простым числом. Теорема. (Об оценке наименьшего собственного делителя.) Пусть n 1 – составное число и р – его наименьший собственный делитель. Тогда 2 p n . Другими словами, любое составное число n кратно простому числу p n . На этом свойстве составных чисел основан алгоритм состав- ления таблиц простых чисел, который называется решетом Эратосфе- на. Имея, например, под рукой таблицу простых чисел из промежутка от 2 до 100, легко получить каноническое разложение любого нату- рального числа из промежутка от 2 до 10000. Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 1, с.8 3 п.1.3. Решето Эратосфена Пусть дано целое число n 1 . 1-й шаг. Выписываем по возрастанию последовательность всех целых чисел от 2 до n. Будем называть эту последовательность целых чисел списком №1: 2, 3, 4, 5, …, n. 2-й шаг. Выписываем по возрастанию последовательность всех про- стых чисел, начиная с простого числа 2 до простого числа р, для кото- рого выполняется неравенство 2 p n . Будем называть эту последова- тельность простых чисел списком №2: 2, 3, 5, 7, …, р, где 2 p n , и если q – простое число, которое следует за простым чис- лом р, то 2 q n . 3-й шаг. Вычеркнем из списка №1 все числа кратные числу 2, кроме самого числа 2. Далее, вычеркнем из списка №1 все числа кратные числу 3, кроме самого числа 3. Следующее простое число в списке №2 стоит простое число 5. Вычеркнем из списка №1 все числа кратные числу 5, кроме самого числа 5. Продолжаем этот процесс до тех пор, пока не вычеркнем из списка №1 все числа, кратные простым числам из списка №2, кроме них самих. В результате такого вычеркивания, формируется список №3, состоя- щий из невычеркнутых из списка №1 чисел. Теорема. Список №3 состоит из всех простых чисел из промежутка от 2 до n, и только из них. п.1.4. Основная теорема арифметики Теорема. (Евклид) Простых чисел бесконечно много. Теорема. (Основная теорема арифметики.) Любое натуральное число, отличное от 1, можно представить в виде произведения простых мно- жителей и притом единственным способом, если не учитывать поря- док сомножителей. Следствие. Любое натуральное число n 1 можно единственным способом записать в виде 1 2 m 1 2 m n p p ...p , Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 1, с.8 4 где 1 2 m p p ... p – простые числа, 1 2 m , ,..., N . Определение. Равенство 1 2 m 1 2 m n p p ...p называется каноническим разложением числа n в произведение простых множителей. п.2. Список задач Список №1 1. Используя решето Эратосфена, составить таблицу простых чисел не превышающих заданного числа. 2. Найти все простые числа из заданного промежутка. 3. Найти все простые делители данного натурального числа. 4. Найти каноническое разложение данного натурального числа. Список №2 1. Задачи на доказательство. п.3. Примеры Пример 1. Составить таблицу простых чисел, не превышающих числа 50. Решение. Составляем список №1, причем из этого списка сразу ис- ключаем все четные числа, кроме числа 2: {2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49}. Составляем список №2. Он состоит из простых чисел, не превосходя- щих 50 , т.е. не больше 7: {2, 3, 5, 7}. Составляем список №3. Все четные числа кроме числа 2 из списка №1 уже исключены. Вычеркиваем из списка №1 все числа кратные числу 3, кроме самого числа 3. Заметим, что если число в списке №1 кратно 3, то следующее число кратное 3 стоит в этом списке через две пози- ции: {2,3,5,7, 9,11,13, 15,17,19, 21,23,25, 27 ,29,31, 33, 35,37, 39,41,43, 45,47,49} Вычеркиваем из списка №1 все числа кратные числу 5, кроме самого числа 5. Заметим, что если число в списке №1 кратно 5, то следующее число кратное 5 стоит в этом списке через четыре позиции: Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 1, с.8 5 {2,3,5,7, 9,11,13, 15,17,19, 21,23, 25, 27 ,29,31, 33, 35,37, 39,41,43, 45,47,49} Вычеркиваем из списка №1 все числа кратные числу 7, кроме самого числа 7. Заметим, что если число в списке №1 кратно 7, то следующее число кратное 7 стоит в этом списке через шесть позиций: {2,3,5,7, 9,11,13, 15,17,19, 21,23, 25, 27 ,29,31, 33, 35,37, 39,41,43, 45,47, 49} Выписываем оставшиеся, невычеркнутые числа и получаем список №3. Ответ: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}. Пример 2. Найти все простые числа из промежутка [2520, 2530] . Решение. Так как 50 2530 51 , то нам понадобится таблица про- стых чисел, не превышающих числа 50, которую мы получили в пре- дыдущем примере. Выписываем все нечетные числа из заданного промежутка: 2521, 2523, 2525, 2527, 2529. Находим ближайшее к числу 2521 нечетное число делящееся на три – 2523. Следовательно, следующее нечетное число делящееся на три стоит в списке через две позиции. Это число 2529. Вычеркиваем их: 2521, 2523,2525,2527, 2529 . Число 2525 единственное в списке, делящееся на 5. Вычеркиваем его: 2521, 2523, 2525,2527, 2529 . Находим, ближайшее к числу 2521 нечетное число делящееся на 7. Это число 2527. Вычеркиваем его: 2521, 2523, 2525, 2527 , 2529 . Остается число 2521. Убеждаемся, что это число не делится ни на од- но из простых чисел, не превосходящих числа 50, следовательно чис- ло 2521 простое. Ответ: 2521. Пример 3. Найти все простые делители числа 18354. Решение. Разделим данное число на 2: 18354 2 9177 Делим полученное число 9177 на 3: 9177 3 3059 Очевидно, что число 3059 не делится на 5. Проверяем его делимость Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 1, с.8 6 на 7: 3059 7 437 Так как 20 437 21 , то нужно проверить делимость числа 437 на простые числа не превосходящие числа 20, т.е. на числа 11, 13, 17, 19. Выясняем, что 437 делится на 19: 437 19 23 Так как 23 простое число, то процесс разложения на простые множи- тели закончен. В процессе работы удобно заполнять следующую таб- лицу: 18354 2 9177 3 3059 7 437 19 23 23 Ответ: 18354 2 3 7 19 23 Пример 4. Разложить на простые множители число 24 2 1 . Решение. Разложим выражение 24 2 1 как разность квадратов: 24 12 12 2 1 (2 1)(2 1) . Разложим 12 2 1 как разность квадратов, а 12 (2 1) как сумму кубов: 12 6 6 12 4 8 4 2 1 (2 1)(2 1), 2 1 (2 1)(2 2 1) . Получаем: 24 2 2 1 63 65 17 241 7 3 5 13 17 241 Так как 15 241 16 , и число 241 не делится на простые числа не превосходящие 15, то оно простое. Ответ: 24 2 2 1 3 5 7 13 17 241 п.4. Задачи Задачи для аудиторного решения 1 1. Составьте таблицу простых чисел не больших 100. 2. Составьте таблицы простых чисел на промежутках: а) [100; 200]; б) [200; 300]; в) [300; 500]. 3. Найдите все простые числа на промежутках: а) [880, 890]; б) [1900, 1910]; в) [4030, 4130]. 4. Найдите каноническое разложение в произведение простых множи- Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 1, с.8 7 телей числа: а) 15! б) 82 798 848; в) 81 057 226 635 000. Задачи повышенного уровня сложности 1 5. Для каких натуральных чисел их наибольший собственный дели- тель является простым числом? 6. Сколькими нулями оканчивается число: а) 25!; б) 200! ? 7. Найдите все целые решения уравнения 2 2 x 19 y . Домашнее задание 1. Решето Эратосфена 1. Составьте таблицу простых чисел на промежутке [1; 1000]. 2. Найдите все простые числа на промежутках: а) [1910, 1920]; б) [4130, 4230]. 3. Докажите теорему о свойствах делимости. Самостоятельная работа 1 Вариант 1. 1. Определение делимости на множестве целых чисел. 2. Найдите все простые числа на промежутке [110, 120]. Вариант 2. 1. Определение собственного делителя целого числа. 2. Найдите все простые числа на промежутке [420, 430]. Вариант 3. 1. Определение простого числа. 2. Найдите все простые числа на промежутке [1230, 1240]. Вариант 4. 1. Определение составного числа. 2. Найдите все простые числа на промежутке [2140, 2150]. п.5. Вопросы и задачи для самоконтроля 1 Обозначения 1. Обозначение множества натуральных чисел. 2. Обозначение множества целых чисел. 3. Обозначение делимости. Определения 1. Определение делимости. 2. Определение тривиальных (несобственных) делителей целого чис- Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 1, с.8 8 ла. 3. Определение собственного делителя целого числа. 4. Определение простого числа. 5. Определение составного числа. Теоремы 1. Теорема о свойства делимости и ее следствие. 2. Теорема о наименьшем собственном делителе. 3. Теорема об оценке наименьшего собственного делителя. 4. Теорема Евклида о бесконечности простых чисел. 5. Основная теорема арифметики. Тест 1 1. Выпишите все простые числа из первой десятки натуральных чисел. 2. Выпишите первые 10 простых чисел. 3. Выпишите все простые числа из первой сотни натуральных чисел. 4. Найдите все простые числа из промежутка [300, 310]. 5. Найдите все простые числа из промежутка [1500, 1510]. 6. Найдите каноническое разложение числа 720 в произведение про- стых множителей. 7. Найдите каноническое разложение числа 10! в произведение про- стых множителей. 8. Найдите наименьшее составное число большее 10, имеющее един- ственный простой делитель. 9. Докажите свойство транзитивности делимости целых чисел. 10. Найдите число нулей на конце числа 100! 11. Докажите, что наибольший простой делитель числа n! не превос- ходит n. Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 2, с.10 1 Практическое занятие 2 Алгоритм Евклида Краткое содержание: НОД, НОК и их свойства, алгоритм деления с остатком, алгоритм Евк- лида, взаимно простые числа. п.1. Теория п.1.1. Наибольший общий делитель, алгоритм деления с остатком и алгоритм Евклида Теорема.'>Определение. Пусть а и b два целых числа, одновременно не равных нулю. Наибольшим общим делителем чисел а и b называется нату- ральное число D, удовлетворяющее следующим двум условиям: 1) D | a и D | b ; 2) если d целое число, такое, что d | a и d | b , то d D Обозначение: D D(a,b) н.о.д.(a,b) Замечание. НОД большего количества чисел определяется аналогич- но. Можно доказать, что 1 2 n 1 2 n D(a ,a ,...,a ) D(a ,D(a ,...,a )) Справедлива и более общая формула: 1 2 n 1 k k 1 n D(a ,a ,...,a ) D(D(a ,...,a ),D(a ,...,a )) , k {1,2,...,n 1} . Теорема. (Свойства НОД) 1) D(a,b) D(b,a) 2) Если a | b , то D(a,b) a . 3) Для любого целого числа n, D(a,b) D(a nb,b) Теорема. (Алгоритм деления с остатком.) Для любых целых чисел а, b 0 , существует единственная пара целых чисел (q, r), удовлетво- ряющих двум условиям: a bq r и 0 r b Определение. В обозначениях предыдущей теоремы, число q называ- ется неполным частным, а r – остатком от деления числа а на число b. Если остаток r 0 , то q называется частным от деления числа а на число b. Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 2, с.10 2 Следующая последовательность делений с остатком называется алгоритмом Евклида. Пусть а, b 0 – произвольные целые числа. Выполним деление с остатком числа а на число b: 1 1 a bq r , где 1 0 r b . Пусть остаток 1 r 0 . Выполним деление с остатком числа b на остаток 1 r : 1 2 2 b r q r , где 2 1 0 r r . Пусть остаток 2 r 0 . Выполним деление с остатком предыдущего ос- татка 1 r на остаток 2 r : 1 2 3 3 r r q r , где 3 2 0 r r . Если остаток 3 r 0 , то делим 2 r на 3 r : 2 3 4 4 r r q r , где 4 3 0 r r . Процесс деления не может продолжаться бесконечно, так как после каждого шага остаток уменьшается, но остается при этом целым неот- рицательным числом. Следовательно, через конечное число шагов этот процесс заканчивается получением нулевого остатка: n 1 n n 1 r r q Теорема. Наибольший общий делитель двух целых чисел равен по- следнему ненулевому остатку в алгоритме Евклида, т.е. n D(a,b) r . п.1.2. Свойство линейной представимости НОД Теорема. (Свойство линейной представимости НОД) Пусть а, b 0 – произвольные целые числа и D – их наибольший об- щий делитель. Тогда существуют целые числа х и у, такие, что D ax by Определение. Числа х и у в линейном представлении НОД называют- ся коэффициентами линейного представления. Теорема. Пусть а, b 0 – произвольные целые числа и n D r – их наибольший общий делитель, вычисленный с помощью алгоритма Евклида, где n r – последний ненулевой остаток. Пусть 1 2 n q ,q ,...,q – Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 2, с.10 3 все неполные частные алгоритма Евклида деления числа а на число b. Тогда n n D ax b y , числа n x и n y могут быть последовательно вычислены по следую- щим рекуррентным формулам: 0 1 k k 2 k 1 k x 0, x 1, x x x q , 0 1 1 k k 2 k 1 k y 1, y q , y y y q , k 2,3,...,n На практике удобно последовательно заполнять клетки следующей таблицы: 1 2 n 0 1 2 n 0 1 2 n q q ... q x x x ... x y y y ... y п.1.3. Наименьшее общее кратное и его свойства Определение. Пусть а и b два целых числа, отличных от нуля. Наи- меньшим общим кратным чисел а и b называется натуральное число K, удовлетворяющее следующим двум условиям: 1) a | K и b | K ; 2) если k целое число, такое, что a | k и b | k , то K k . Замечание. НОК большего количества чисел определяется аналогич- но. Можно доказать, что 1 2 n 1 2 n K(a ,a ,...,a ) K(a ,K(a ,...,a )) Справедлива и более общая формула: 1 2 n 1 k k 1 n K(a ,a ,...,a ) K(K(a ,...,a ),K(a ,...,a )) , k {1,2,...,n 1} . Теорема. (Связь НОД и НОК.) Пусть а и b два произвольных нату- ральных числа. Тогда ab D(a,b) K(a,b) Теорема. (О вынесении общего множителя за знак НОД и НОК.) Об- Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 2, с.10 4 щий множитель двух целых чисел можно выносить за знаки их НОД и НОК, т.е. если m ac, n bc , то D(m,n) D(ac,bc) cD(a,b) , K(m,n) K(ac,bc) cK(a,b) |