АГ ПЗ 1-35 (полный вариант). Практическое занятие 1 Решето Эратосфена
 Скачать 2.3 Mb.
|
|
Теорема. (О наименьшем неотрицательном вычете.) Наименьший не- отрицательный вычет числа а по модулю m равен остатку от деления числа а на модуль m, и обозначается a r (mod m) . Замечание. Если модуль фиксированный, то наименьший неотрица- тельный вычет числа а по модулю m будем обозначать a r . Таким образом, из последней теоремы следует, что для любого целого числа а, существует единственный его наименьший неотрицательный вычет a r , следовательно, a a r (mod m) и a a r Теорема. (Свойства классов вычетов.) Пусть m 1 – произвольное фиксированное натуральное число. Тогда 1) Любые два класса вычетов по модулю m либо совпадают, либо не пересекаются. 2) Каждое целое число попадает в один и только один класс вычетов по модулю m. 3) Существует ровно m классов вычетов по модулю m: 0, 1, ..., m 1 , где числа 0,1,...,m 1 являются наименьшими неотрицательными вычетами в своих классах вычетов. 4) Объединение всех классов вычетов по модулю m совпадает с мно- жеством целых чисел: Z 0 1 ... m 1 . Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 3, с.17 6 Замечание. Множество всех классов вычетов по модулю m обознача- ется m Z . Из теоремы следует, что m Z {0, 1, ..., m 1} Теорема. Все числа любого класса вычетов по модулю m образуют бесконечную (в обе стороны) арифметическую прогрессию с разно- стью прогрессии m. Все члены этой прогрессии можно описать фор- мулой: t 0 a a t m, t Z , где 0 a – наименьший неотрицательный вычет. п.1.6. Полная и приведенная система вычетов Определение. Множество чисел, взятых в точности по одному из ка- ждого класса вычетов по модулю m, называется полной системой вы- четов по модулю m. Определение. Любой вычет числа а по модулю m называется пред- ставителем класса вычетов a Замечание. Обычно, из каждого класса вычетов в качестве его пред- ставителя берется наименьший неотрицательный вычет. В результате, полная система вычетов по модулю m имеет вид {0,1,...,m 1} . Определение. Вычет b числа а по модулю m называется абсолютно наименьшим вычетом, если он по абсолютной величине не превосхо- дит половины модуля, т.е. если m | b | 2 Определение. Полная система вычетов по модулю m называется пол- ной системой абсолютно наименьших вычетов, если каждый вычет в этой системе по абсолютной величине не превосходит половины мо- дуля. Теорема. Если a b (mod m) , то D(a,m) D(b,m) Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 3, с.17 7 Другими словами, все числа из одного класса вычетов по модулю m имеют с модулем m одинаковый наибольший общий делитель. Определение. Класс вычетов a числа а по модулю m называется примитивным, если числа а и m взаимно простые, т.е. D(a,m) 1 . Определение. Множество чисел, взятых в точности по одному из ка- ждого примитивного класса вычетов, называется приведенной систе- мой вычетов по модулю m. Замечание. Если из каждого примитивного класса вычетов по моду- лю m взять в качестве его представителя наименьший неотрицатель- ный вычет, то в случае простого модуля, т.е. когда m p – простое число, приведенная система вычетов будет иметь вид: {1, 2, ..., p 1} . В случае произвольного модуля приведенную систему вычетов обо- значают 1 2 t {a ,a ,...,a } , где t – число примитивных классов вычетов. Множество всех примитивных классов вычетов по модулю m обозна- чается * m Z . Таким образом, по определению * m 1 2 t Z {a ,a ,...,a } , где t – число примитивных классов вычетов по модулю m. п.1.7. Теоремы Эйлера и Ферма Определение. Количество чисел в последовательности 0,1,...,m 1 взаимно простых с числом m называется функцией Эйлера и обозна- чается (m) Замечание. Из последнего определения следует, что число примитив- ных классов вычетов по модулю m равно (m) , и приведенная систе- ма вычетов по модулю m содержит t (m) чисел. В частности, если m p – простое число, то (p) p 1 . Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 3, с.17 8 Теорема. (Свойства функции Эйлера.) 1) Свойство мультипликативности. Если m и n – взаимно простые на- туральные числа, то (m n) (m) (n) 2) (1) 1 3) Если р – простое число, то для любого натурального числа n n n n 1 (p ) p p Замечание. Свойства функции Эйлера позволяют вычислять ее зна- чения для любого натурального числа. Пусть имеется каноническое разложение натурального числа n в произведение простых множите- лей: 1 2 m 1 2 m n p p ...p Тогда 1 2 m 1 2 m (n) (p ) (p )... (p ) 1 1 2 2 m m 1 1 1 1 1 2 2 m m (p p )(p p )...(p p ) 1 2 m 1 1 1 n 1 1 ... 1 p p p Теорема. (Теорема Эйлера.) Пусть m 1 – произвольное натуральное число. Тогда для любого целого числа а взаимно простого с m верно сравнение (m) a 1 (mod m) Теорема. (Малая теорема Ферма) Пусть р – простое число. Тогда для любого целого числа а верно сравнение p a a (mod p) п.2. Список задач Список №1 1. Определить, сравнимы ли данные числа по данному модулю. 2. Найти сумму, разность и произведение двух данных сравнений. 3. Умножить данное сравнение на данное число. 4. Сократить данное сравнение на общий множитель. 5. Найти наименьший неотрицательный вычет данного числа по дан- ному модулю. 6. Найти наименьший по абсолютной величине вычет данного числа Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 3, с.17 9 по данному модулю. 7. Выписать полную систему вычетов по данному модулю. 8. Выписать полную систему наименьших по абсолютной величине вычетов по данному модулю. 9. Вычислить значение функции Эйлера для данного натурального числа. 10. Выписать приведенную систему вычетов по данному модулю. 11. Выписать приведенную систему наименьших по абсолютной ве- личине вычетов по данному модулю. 12. Выписать множество всех классов вычетов по данному модулю. 13. Выписать множество всех примитивных классов вычетов по дан- ному модулю. 14. Найти остаток от деления одного целого числа на другой с помо- щью действий со сравнениями. 15. Найти последнюю цифру данного числа. Список №2 1. Найти две последние цифры данной натуральной степени целого числа. 2. Задачи на доказательство и задачи повышенного уровня сложности. п.3. Примеры Пример 1. Сравнимы ли числа 226 и 167 по модулю 15? Решение. Найдем разность данных чисел: 226 167 59 Так как 59 не делится на 15, то данные числа не сравнимы друг с дру- гом по модулю 15. Ответ: нет. Пример 2. Найти сумму, разность и произведение сравнений 5 1(mod 6), 83 5(mod 6) Решение. 1) 5 83 1 5(mod 6) или 88 4(mod 6) 2) 5 83 1 5(mod 6) или 78 6(mod 6) 3) 5 83 ( 1) 5(mod 6) или 415 5(mod 6) Ответ: 88 4(mod 6) , 78 6(mod 6) , 415 5(mod 6) Пример 3. Умножить сравнение 3 1(mod 4) на 6. Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 3, с.17 10 Решение. 3 6 ( 1) 6(mod 4) Ответ: 18 6(mod 4) Пример 4. Сократить 88 4(mod 6) на общий множитель. Решение. Все три части сравнения можно сократить на общий множи- тель 2: 88 4(mod 6) 44 2(mod3) Так как числа 2 и 3 взаимно простые, то последнее сравнение можно сократить на 2: 44 2(mod3) 22 1(mod3) Ответ: 22 1(mod3) Пример 5. Найти наименьший неотрицательный вычет числа 5439 по модулю 15. Решение. Разделим данное число 5439 на 15 с остатком: 5439 15 362 9 и 9 15 Следовательно, 15 | 5439 9 и 5439 9(mod15) . Так как вычет 9 меньше модуля 15, то 9 – наименьший неотрицательный вычет числа 5439 по модулю 15. Ответ: 5439 9(mod15) Пример 6. Найти наименьший по абсолютной величине вычет числа 5439 по модулю 15. Решение. 5439 9(mod15) , но 15 9 2 . Следовательно, 9 не является наименьшим по абсолютной величине вычетом. Вычтем из правой части сравнения 5439 9(mod15) модуль 15: 5439 9(mod15) 5439 9 15(mod15) 5439 6(mod15) Вычет (–6) числа 5439 по абсолютной величине равен 15 | 6 | 6 2 , следовательно, наименьшим по абсолютной величине вычетом числа 5439 по модулю 15 является число –6. Ответ: 5439 6(mod15) Пример 7. Выписать полную систему вычетов по модулю 15. Ответ: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}. Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 3, с.17 11 Пример 8. Выписать полную систему наименьших по абсолютной ве- личине вычетов по модулю 15. Решение. 8 8 15(mod15) 8 7(mod15) . Прибавляя по 1 к обеим частям сравнения, получаем: 9 6(mod15),...,14 1(mod15) Ответ: {–7, –6, –5, –4, –3, –2, –1, 0, 1, 2, 3, 4, 5, 6, 7}. Пример 9. Выписать полную систему наименьших по абсолютной ве- личине вычетов по модулю 8. Решение. Выписываем полную систему вычетов по модулю 8: {0, 1, 2, 3, 4, 5, 6, 7}. Имеем, 4 4(mod8) , 5 3(mod8) , 6 2(mod8) , 7 1(mod8) Ответ: { –3, –2, –1, 0, 1, 2, 3, 4}. Пример 10. Выписать приведенную систему вычетов по модулю 15. Решение. Из чисел: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 взаимно простыми с модулем 15 являются числа 1, 2, 4, 7, 8, 11, 13, 14. Ответ: {1, 2, 4, 7, 8, 11, 13, 14}. Пример 11. Выписать все классы вычетов по модулю 6. Ответ: {0, 1, 2, 3, 4, 5}. Пример 12. Выписать все примитивные классы вычетов по модулю 6. Ответ: {1, 5} . Пример 13. Найти остаток от деления числа 2010 7 на 11. Решение. Так как число 7 взаимно просто с модулем 11, то по теореме Эйлера (11) 7 1(mod11) . Так как 11 – простое число, то (11) 11 1 10 , следовательно, 10 7 1(mod11) . Воспользуемся свой- ством степеней: 2010 10 201 7 (7 ) Переходя от равенства к сравнению по модулю 11, получаем: 2010 10 201 7 (7 ) (mod11) 1(mod11) Ответ: 1. Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 3, с.17 12 Пример 14. Найти последнюю цифру числа 2010 7 Решение. Последняя цифра числа сравнима с его остатком при деле- нии его на 10, поэтому она равна его наименьшему неотрицательному вычету по модулю 10: 2010 7 r (mod10) Так как числа 7 и 10 взаимно простые, то, применяя теорему Эйлера, получаем (10) 7 1(mod10) Вычисляем значение функции Эйлера (10) : (10) (2 5) (2) (5) (2 1)(5 1) 4 . Таким образом, 4 7 1(mod10) По свойству степеней, 2010 4 502 2 4 502 2 7 7 (7 ) 7 . Переходя в этом равенстве к сравнению по модулю 10, получаем: 2010 4 502 2 7 (7 ) 7 (mod10) 49(mod10) 9(mod10) Ответ: 9. Пример 15. Ваш знакомый родился 14 сентября 1993 года. Зная, что 14 сентября 2010 года является вторником, найдите день недели дня рождения вашего знакомого. Решение. Вычислим, сколько дней прошло с дня рождения 14 сентяб- ря 1993 года по 13 сентября 2010 года. День 14 сентября 1993 года считаем 0-м днем, тогда 14 сентября 1994 года – это 365-й день, так как 1994-й год был не високосный. Обозначим через n число дней считая с 15 сентября 1993 года по 14 сентября 2010 года включитель- но. Тогда день рождения 14 сентября 2010 года будет n -м днем. Вы- числяем число n: n 365 17 4 , где 4 – по одному дню в високосные годы. Найдем наименьший неот- рицательный вычет числа n по модулю 7. Так как число 364 делится на 7, то 365 1(mod 7) . Далее, 17 3(mod 7) , откуда следует: n 365 17 4(mod 7) 3 4(mod 7) 0(mod 7) Следовательно, 14 сентября 2010 года и 14 сентября 1993 года явля- ются одинаковыми днями недели. Так как 14 сентября 2010 года – вторник, то 14 сентября 2010 года тоже вторник. Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 3, с.17 13 Ответ: день рождения был вторником. Пример 16. Докажите, что числа 2010 15 и 21 несравнимы друг с дру- гом по модулю 35. Решение. Допустим противное. Пусть 2010 15 21(mod35) , тогда по свойствам сравнения 2010 D(15 ,35) D(21,35) 7 . Так как 2010 5 | D(15 ,35) , то отсюда следует, что 5 | 7 . Получили противоречие, так как 5 не делит 7. Следовательно, наше предположение неверное и данные числа несравнимы по модулю 35, ч.т.д. п.4. Задачи Задачи для аудиторного решения 3 1. Среди чисел 123, 211, 134, 214, 303, 21 найдите все пары чисел, сравнимых между собой по модулю 5. 2. Среди чисел 135, 226, 106, 181, 225, 167, 452 найдите все пары чи- сел, сравнимых между собой по модулю 15. 3. Какие из чисел 137, 343, 633 сравнимы с числом 13 по модулю 31? 4. Найти сумму, разность и произведение сравнений 15 8(mod 7), 83 6(mod 7) 5. Умножьте сравнение 5 21(mod16) на 6. 6. Сократите все части сравнения 16 80(mod96) на общий множи- тель. Верно ли сравнение 8 40(mod96) ? 7. Проведите все возможные сокращения в сравнении 224 14(mod30) 8. Найдите наименьший неотрицательный вычет данных чисел по данному модулю: а) 127, 110, 203 по модулю 11; б) 136, 151, 210 по модулю 15; в) 406, 1596, 35671 по модулю 12. 9. Найдите наименьший по абсолютной величине вычет данных чисел по данному модулю: а) 99, 138, 202 по модулю 11; б) 299, 602, 300 по модулю 30; в) 2013, 34973 по модулю 36. 10. Найдите полную и приведенную систему вычетов по модулю: а) 8; б) 9; в) 10; г) 11. 11. Найдите полную и приведенную систему наименьших по абсо- лютной величине вычетов по модулю: а) 8; б) 9; в) 10; г) 11. 12. Вычислите значение функции Эйлера от чисел: 13, 169, 1001, 45000. 13. Найдите число примитивных классов вычетов по модулю: а) 30; Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 3, с.17 14 б) 100. 14. В последовательности чисел 1, 2, …, 2700 найдите количество чи- сел взаимно простых с числом 2700. 15. Найдите остаток от деления: а) числа 49 13 на 48; б) числа 200 200 3 7 на 101; в) числа 65 65 7 11 на 80. 16. Найдите последнюю цифру чисел 281 17 , 321 19 , 161 132 . 17. Докажите, что число 120 37 1 делится на 700. Задачи повышенного уровня сложности 3 18. Докажите, что любые m последовательных натуральных чисел об- разуют полную систему вычетов по модулю m. 19. Докажите свойства сравнений. 20. Докажите закон сокращения в сравнениях. 21. Докажите признаки делимости. 22. Докажите, что наименьший неотрицательный вычет числа а по модулю m равен остатку от деления числа а на модуль m. 23. Число 0 и все натуральные числа выписаны одно за другим без за- пятых и пробелов в ряд: 012345678910111213… . Какая цифра сто- ит на 2010-й позиции? 24. Найдите две последние цифры чисел 281 17 , 321 19 , 161 132 . 25. Докажите, что 243 15 10(mod30) 26. Зная, что 12 июня 2010 года суббота, найдите день недели Дня не- зависимости России в 2020-м году. 27. Докажите, что из любых 100 целых чисел можно выбрать 15 таких чисел, что для любых двух из них их разность делится на 7. 28. Докажите, что если два целых числа не делятся на 3, то и сумма их квадратов тоже не делится на 3. 29. Докажите, что числа вида n 9m 4, m N нельзя представить в виде 3 3 3 n a b c , a,b,c N . Домашнее задание 3. Сравнения по модулю 1. Среди чисел 146, 1201, 182, 241 найдите все пары чисел, сравнимых между собой по модулю 12. 2. Найти сумму, разность и произведение сравнений 25 3(mod11), 50 5(mod11) . Умножьте первое сравнение на 2, а второе на –3. 3. Произведите правильные сокращения в сравнениях 45 9(mod18) и Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 3, с.17 15 30 6(mod8) 4. Найдите наименьший неотрицательный вычет числа 987 по модулю 24. 5. Найдите наименьший по абсолютной величине вычет числа 98 по модулю 17. 6. Выпишите полную и приведенную систему вычетов по модулю 4. 7. Выпишите полную и приведенную систему наименьших по абсо- лютной величине вычетов по модулю 4. 8. Найдите число примитивных классов вычетов по модулю 1000. 9. Найдите остаток от деления числа 12 73 на 7. 10. Найдите последнюю цифру числа 5 2 2 1 Самостоятельная работа 3 Вариант 1. 1. Определение сравнения по модулю. 2. Выпишите полную систему вычетов по модулю 7. 3. Найдите наименьший неотрицательный вычет числа 222 по модулю 7. Вариант 2. 1. Определение вычета данного числа по данному модулю. 2. Выпишите приведенную систему вычетов по модулю 7. 3. Найдите наименьший по абсолютной величине вычет числа 335 по модулю 7. Вариант 3. 1. Определение класса вычетов данного числа по данному модулю. 2. Выпишите полную систему наименьших по абсолютной величине вычетов по модулю 7. 3. Найдите остаток от деления числа 2010 3 на 7. Вариант 4. 1. Определение наименьшего неотрицательного вычета данного числа по данному модулю. 2. Выпишите приведенную систему наименьших по абсолютной вели- чине вычетов по модулю 8. 3. Найдите последнюю цифру числа 2010 3 |