АГ ПЗ 1-35 (полный вариант). Практическое занятие 1 Решето Эратосфена
 Скачать 2.3 Mb.
|
|
Определение. Два целых числа называются взаимно простыми, если их наибольший общий делитель равен 1. Следствие. Наименьшее общее кратное двух взаимно простых нату- ральных чисел равно их произведению. п.1.4. Свойства взаимно простых чисел Теорема. (Свойства взаимно простых чисел.) 1) D(a,b) 1 x, y Z : ax by 1 ; 2) a b d D(a,b) D , 1 d d ; 3) если числа а и b взаимно просты с третьим числом n, то их произ- ведение ab также взаимно просто с числом n: D(a,n) 1 и D(b,n) 1 , то D(ab,n) 1 ; 4) если число k кратно каждому из взаимно простых чисел а и b, то оно кратно и их произведению: D(a,b) 1 и a | k, b | k , то ab | k ; 5) если a | bc и D(a,b) 1 , то a | c . Теорема. (Основное свойство простого числа.) Натуральное число р является простым тогда и только тогда, когда из того, что p | ab и p | a следует, что p | b , где а, b – произвольные целые числа. п.2. Список задач Список №1 1. Найти НОД и НОК данных чисел. 2. Найти линейное представление НОД двух данных чисел. Список №2 1. Задачи на доказательство. Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 2, с.10 5 п.3. Примеры Пример 1. Найти НОД и НОК чисел 5321 и 4998. Решение. Вычислим D(5321,4998) с помощью алгоритма Евклида. Делим число a 5321 на число b 4998 , и находим неполное частное 1 q и остаток 1 r : 5321 4998 1 323 , где 1 1 q 1, r 323 . Далее, делим число b 4998 на остаток 1 r 323 : 4998 323 15 153 , где неполное частное 2 q 15 , остаток 2 r 153 . Далее, делим остаток 1 r 323 на остаток 2 r 153 : 323 153 2 17 , где неполное частное 3 q 2 , остаток 3 r 17 . Делим остаток 2 r 153 на остаток 3 r 17 : 153 17 9 Последним ненулевым остатком является число 3 r 17 , оно и будет искомым НОД. Для вычисления НОК воспользуемся формулой: ab a 5321 K(a,b) b 4998 313 4998 D(a,b) D(a,b) 17 1564374 Ответ: D(5321,4998) 17, K(5321,4998) 1564374 Пример 2. Найти линейное представление НОД чисел 5321 и 4998. Решение. Воспользуемся таблицей 1 2 n 0 1 2 n 0 1 2 n q q ... q x x x ... x y y y ... 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 , откуда находим линейную представимость НОД Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 2, с.10 6 n n D(a,b) ax b y В нашем случае неполные частные уже найдены в предыдущем при- мере: 1 2 3 q 1, q 15, q 2 . Заполняем таблицу: 2 3 2 3 1 15 2 0 1 x x 1 1 y y Вычисляем 2 2 x 0 1 15 15, y 1 ( 1) 15 16 Заносим найденные значения в таблицу: 3 3 1 15 2 0 1 15 x 1 1 16 y Вычисляем 3 3 x 1 ( 15) 2 31, y 1 16 2 33 . Заносим в таблицу: 1 15 2 0 1 15 31 1 1 16 33 Ответ: D(5321,4998) 5321 31 4998 ( 33) Пример 3. Докажите, что любые два последовательных натуральных числа являются взаимно простыми. Доказательство. Пусть n и n 1 – два произвольных последователь- ных числа. Воспользуемся формулой: D(a,b) D(a,b a) . Тогда, D(n,n 1) D(n,1) 1 , ч.т.д. Пример 4. Сократима ли дробь 2 n 4 n 8n 15 при каком-нибудь значе- нии натурального числа n? Решение. Найдем корни квадратного трехчлена и разложим его на ли- Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 2, с.10 7 нейные множители: 2 n 8n 15 (n 3)(n 5) . Дробь можно записать в виде n 4 (n 3)(n 5) Натуральные числа n 3, n 4, n 5 являются последовательными, поэтому число n 4 взаимно простое с числами n 3 и n 5 , а пото- му дробь несократимая ни при каких натуральных числах n. Ответ: нет. Пример 5. Докажите, что если p 3 – простое число, то число 2 1 2p является составным. Доказательство. Разделим р на 3 с остатком: p 3q r, 0 r 3 . Так как р – простое и больше 3, то р не делится на 3, следовательно, остаток r 0 и r 1 или r 2 . Вычислим 2 2 2 2 1 2p 1 2(3q r) 1 18q 12qr 2r 2 2 3(6q 4qr) (1 2r ) При r 1 , 2 (1 2r ) 3 , при r 2 , 2 (1 2r ) 9 и число 2 2 2 1 2p 3(6q 4qr) (1 2r ) делится на 3, т.е. является составным, ч.т.д. Пример 6. Докажите, что при любом целом n число 2 n 1 не делится на 3. Доказательство. Разделим n на 3 с остатком: n 3q r, r {0,1,2} Тогда 2 2 2 2 n 1 (3q r) 1 3(3q 2qr) (r 1) делится на 3 тогда и только тогда, когда число 2 (r 1) делится на 3. Подставляя вместо r числа 0, 1, 2, убеждаемся, что во всех случаях число 2 (r 1) на 3 не делится, следовательно, не делится на 3 и число 2 n 1 , ч.т.д. Пример 7. При каких натуральных n числа 3n 1 и 5n 1 будут вза- имно простыми? Решение. Пусть НОД данных чисел равен d. Тогда d делит число Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 2, с.10 8 (3n 1)x (5n 1)y при любых целых х и у. Возьмем x 5, y 3 . То- гда d делит число 5(3n 1) 3(5n 1) 2 , следовательно, d 1 или d 2 , причем в последнем случае оба числа должны быть четными, т.е. число n должно быть нечетным. Ответ: при всех четных n. п.4. Задачи Задачи для аудиторного решения 2 1. Найдите НОД и НОК чисел: а) 3069 и 2637; б) 6567 и 4279; в) 29408339 и 26442001; г) 81719, 52003, 33649 и 30107. 2. Найдите линейное представление НОД чисел: а) 678 и 582; б) 703 и 697; в) 81719 и 52003; г) 33649 и 30107. Задачи повышенного уровня сложности 2 3. Найдите все пары простых чисел р и q, удовлетворяющих условию 2 2 p 2q 1 . (Смотрите пример 5.) 4. Найдите наибольшее трехзначное число х, для которого D(x,540) 36 5. При каких натуральных n будут взаимно простыми числа: а) 2n 3 и n 1 ; б) 2 n 1 и n 3 ? 6. Докажите, что если число n не делится на 2 и 3, то число 2 n 1 де- лится на 24. 7. Докажите, что при любом n число 5 n n делится на 30. 8. Докажите, что n m D(n,m) D(2 1,2 1) 2 1 . Домашнее задание 2. Алгоритм Евклида 1. Найдите НОД и НОК чисел: а) 2261 и 861; б) 3612 и 1536; в) 213166494391 и 57337099343. 2. Найдите линейное представление НОД чисел: а) 42 и 91; б) 1073 и 899. 3. Используя свойство линейной представимости НОД, докажите тео- рему о вынесении общего множителя за знак НОД. Самостоятельная работа 2 Вариант 1. 1. Определение наибольшего общего делителя двух целых чисел. 2. С помощью алгоритма Евклида найдите НОД и НОК чисел 111 и Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 2, с.10 9 93. Вариант 2. 1. Определение взаимно простых чисел. 2. С помощью алгоритма Евклида найдите НОД и НОК чисел 371 и 329. Вариант 3. 1. Определение наименьшего общего кратного двух целых чисел. 2. С помощью алгоритма Евклида найдите НОД и НОК чисел 8598 и 6702. Вариант 4. 1. Определение неполного частного и остатка от деления одного цело- го числа на другое. 2. С помощью алгоритма Евклида найдите НОД и НОК чисел 9926 и 6286. п.5. Вопросы и задачи для самоконтроля 2 Обозначения 1. Обозначение НОД и НОК. Определения 1. Определение НОД двух целых чисел. 2. Определение остатка от деления и неполного частного. 3. Определение НОК двух целых чисел. 4. Определение взаимно простых чисел. Теоремы 1. Свойства НОД. 2. Алгоритм деления с остатком. 3. Теорема о НОД в алгоритме Евклида. 4. Свойство линейной представимости НОД. 5. Рекуррентные формулы и таблица для вычисления коэффициентов линейного представления НОД. 6. Связь НОД и НОК. 7. Теорема о вынесении общего множителя за знак НОД и НОК. 8. НОК взаимно простых чисел. 9. Свойства взаимно простых чисел. 10. Основное свойство простого числа. Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 2, с.10 10 Тест 2 1. Выпишите все делители числа 24. 2. Выпишите все делители чисел 72 и 108 и найдите их НОД и НОК. 3. Найдите НОД чисел 72 и 108 с помощью алгоритма Евклида. 4. С помощью алгоритма Евклида найдите НОД и НОК чисел 1533 и 903. 5. Вычислите 1 1 943 1219 и запишите результат в виде несократимой дроби. 6. Найдите линейное представление НОД чисел 97 и 37. 7. Найдите общий знаменатель дробей 111 21120 и 1237 30720 8. Докажите, что среди трех последовательных натуральных чисел найдется в точности одно число делящееся на 3. 9. Докажите, что для всех нечетных натуральных чисел n число 2 n 1 делится на 8. 10. Крестьянка несла на базар яйца. Проезжавший всадник толкнул её, и все яйца разбились. На вопрос, сколько было яиц, она сказала: «Когда я раскладывала яйца по два, одно оказалось лишним. То же самое случилось, когда я раскладывала их по 3, по 4, по 5 и по 6. А вот когда я их разложила по 7, остатка не оказалось». Сколько яиц было у крестьянки? Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 3, с.17 1 Практическое занятие 3 Сравнения по модулю Краткое содержание: понятие сравнения по модулю, свойства сравнений, действия со сравне- ниями, признаки делимости, классы вычетов и их свойства, наименьший неотрицательный вычет, наименьший по абсолютной величине вычет, полная и приведенная система вычетов, функция Эйлера и ее свойства, теоремы Эйлера и Ферма. п.1. Теория п.1.1. Сравнение по модулю Определение. Пусть m 1 – произвольное натуральное число, а и b – произвольные целые числа. Число а называется сравнимым с числом b по модулю m, если m | a b . Обозначение: a b (mod m) Таким образом, по определению, a b (mod m) m | a b . Следствие.'>Замечание. Если число а кратно положительному числу b 1 , то этот факт можно описать двумя равносильными способами: b | a a 0 (mod b) Следствие. Равные числа сравнимы друг с другом по любому моду- лю. Теорема. (Свойства сравнений.) Сравнение целых чисел по модулю натурального числа m 1 обладает следующими свойствами: 1) свойство рефлексивности: a Z , a a (mod m) ; 2) свойство симметричности: a,b Z , если a b (mod m) , то b a (mod m) ; 3) свойство транзитивности: a,b,c Z , если a b (mod m) и b c (mod m) , то a c (mod m) Следствие. Отношение сравнимости целых чисел по модулю является отношением эквивалентности. Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 3, с.17 2 п.1.2. Действия со сравнениями Теорема. Сравнения по одному и тому же модулю можно почленно складывать, вычитать и умножать, т.е. если a b (mod m) и c d (mod m) , то a c b d (mod m) и ac bd (mod m) Следствие. (Свойства сравнений.) 1) К обеим частям сравнения можно прибавить одно и то же слагае- мое или сократить его, т.е. для любого целого числа k a b (mod m) a k b k (mod m) 2) Обе части сравнения можно умножить на одно и то же число, т.е. для любого целого числа k a b (mod m) ak bk (mod m) 3) Любое слагаемое, находящееся в одной части сравнения, можно перенести слагаемым в другую его часть с противоположным зна- ком, т.е. a k b (mod m) a b k (mod m) 4) Обе части сравнения можно возводить в одну и ту же натуральную степень, т.е. n n a b (mod m) a b (mod m) , где n N 5) К любой части сравнения можно прибавить слагаемое, кратное мо- дулю или заменить его нулем, т.е. если k 0 (mod m) , то a b (mod m) a 0 b (mod m) a k b (mod m) 6) Любое число, кратное модулю и стоящее множителем в любой час- ти сравнения, можно заменить нулем, т.е. если k 0 (mod m) , то a b ck (mod m) a b c 0 (mod m) a b (mod m) 7) Любое число, стоящее слагаемым или множителем в любой части сравнения, можно заменить любым другим числом, с которым оно сравнимо по данному модулю, т.е. если a b (mod m) , то d a c (mod m) d b c (mod m) , d ak c (mod m) d bk c (mod m) , n n d a k c (mod m) d b k c (mod m) , где n N п.1.3. Сокращения в сравнениях Теорема. Пусть k и m 1 – произвольные натуральные числа, а и b – произвольные целые числа. Тогда Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 3, с.17 3 a b (mod m) ak bk (mod mk) Теорема. (Закон сокращения в сравнениях.) Обе части сравнения можно сократить на один и тот же множитель, если он взаимно про- стой с модулем, т.е. если D(k,m) 1 , то ak bk (mod m) a b (mod m) Следствие. Если D(k,m) 1 , то a b (mod m) ak bk (mod m) п.1.4. Признаки делимости Теорема. Любое натуральное число n единственным способом можно записать в виде: 2 m 0 1 2 m m m 1 2 1 0 n a a 10 a 10 ... a 10 a a ...a a a , где k k 0,1,2,...,m : a {0,1,2,...,9} и m a 0 . Определение. Запись натурального числа в виде m m 1 2 1 0 n a a ...a a a , где k k 0,1,2,...,m : a {0,1,2,...,9} и m a 0 , называется позицион- ной формой записи числа в системе счисления с основанием равным 10 или записью числа в десятичной системе счисления, числа k a , k 0,1,2,...,m называются его цифрами. Замечание. В дальнейшем, как и прежде, при записи целых чисел мы пользуемся только десятичной системой счисления. Введем для удобства записи следующие обозначения. Пусть m m 1 2 1 0 n a a ...a a a – произвольное натуральное число. Обозначим че- рез: 0 1 m S(n) a a ... a – сумму цифр числа n; m 0 1 m S(n) a a ... ( 1) a ; 3 2 1 0 5 4 3 m S (n) a a a a a a ... a ... , где последнее слагаемое будет равно m m 1 m 2 a a a , если m 2 (mod3) или m m 1 a a , если m 1 (mod3) или Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 3, с.17 4 m m a a , если m 0 (mod3) ; t 3 2 1 0 5 4 3 m S (n) a a a a a a ... ( 1) a ... , где t равно полному или непол- ному частному от деления числа m на 3. Теорема. Пусть m m 1 2 1 0 n a a ...a a a . Тогда: 1) 0 n 0 (mod 2) a 0 (mod 2) ; 2) n 0 (mod3) S(n) 0 (mod3) ; 3) 1 0 n 0 (mod 4) a a 0 (mod 4) ; 4) 0 n 0 (mod5) a 0 (mod5) ; 5) 3 n 0 (mod 7) S (n) 0 (mod 7) 6) 2 1 0 n 0 (mod8) a a a 0 (mod8) ; 7) n 0 (mod9) S(n) 0 (mod9) ; 8) 3 n 0 (mod11) S (n) 0 (mod11) S(n) 0 (mod11) ; 9) 3 n 0 (mod13) S (n) 0 (mod13) ; 10) 1 0 n 0 (mod 25) a a 0 (mod 25) ; 11) 3 n 0 (mod37) S (n) 0 (mod37) п.1.5. Классы вычетов Определение. Любое целое число х сравнимое с данным числом а по данному модулю m называется вычетом числа а по модулю m. Таким образом, если x a (mod m) , то х – вычет числа а по модулю m. Определение. Множество всех вычетов числа а по модулю m называ- ется классом вычетов числа а по модулю m, и обозначается a Другими словами, класс вычетов числа а по модулю m a {x Z | x a (mod m)} является, по определению, множеством состоящим из всех целых чи- сел сравнимых с числом а по модулю m. Теорема. Любые два числа из класса вычетов по модулю m сравнимы Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 3, с.17 5 друг с другом по модулю m, т.е. если b,c a , то b c (mod m) Теорема. (О равенстве классов вычетов.) Пусть a и b два класса вы- четов по модулю m. Тогда a b a b (mod m) Определение. Наименьшее неотрицательное число, содержащееся в классе вычетов числа а по модулю m называется его наименьшим не- отрицательным вычетом. |