АГ ПЗ 1-35 (полный вариант). Практическое занятие 1 Решето Эратосфена
 Скачать 2.3 Mb.
|
|
п.5. Вопросы и задачи для самоконтроля 3 Обозначения 1. Обозначение сравнения двух целых чисел по заданному модулю. Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 3, с.17 16 2. Обозначение класса вычетов данного числа по известному фикси- рованному модулю. 3. Обозначение наименьшего неотрицательного вычета данного числа по данному модулю. 4. Обозначение множества всех классов вычетов по данному модулю. 5. Обозначение множества всех примитивных классов вычетов по данному модулю. 6. Обозначение функции Эйлера. Определения 1. Определение сравнения по модулю. 2. Определение вычета числа по данному модулю. 3. Определение класса вычетов данного числа по данному модулю. 4. Определение наименьшего неотрицательного вычета данного числа по данному модулю. 5. Определение полной системы вычетов по данному модулю. 6. Определение наименьшего по абсолютной величине вычета данно- го числа по данному модулю. 7. Определение полной системы наименьших по абсолютной величи- не вычетов по данному модулю. 8. Определение примитивного класса вычетов данного числа по дан- ному модулю. 9. Определение приведенной системы вычетов по данному модулю. 10. Определение приведенной системы наименьших по абсолютной величине вычетов по данному модулю. 11. Определение функции Эйлера. Теоремы 1. Свойства сравнений. 2. Теорема о действиях со сравнениями и ее следствие о свойствах действий со сравнениями. 3. Теорема о сокращении в сравнениях. 4. Закон сокращений в сравнениях. 5. Признаки делимости. 6. Теорема о наименьшем неотрицательном вычете. 7. Теорема о равенстве классов вычетов. 8. Свойства классов вычетов. 9. Свойства функции Эйлера. 10. Теорема Эйлера. Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 3, с.17 17 11. Малая теорема Ферма. Тест 3 1. Какие из чисел 14, 51, 101 сравнимы с числом 3 по модулю 7? 2. По какому наименьшему модулю сравнимы друг с другом числа 209 и 1108? 3. Произведите сокращение в сравнении 84 21(mod9) 4. Найдите наименьший неотрицательный вычет числа 1234 по моду- лю 11. 5. Найдите наименьший по абсолютной величине вычет числа 2345 по модулю 17. 6. Выпишите полную систему вычетов по модулю 8. 7. Выпишите приведенную систему вычетов по модулю 8. 8. Выпишите полную систему наименьших по абсолютной величине вычетов по модулю 10. 9. Выпишите приведенную систему наименьших по абсолютной вели- чине вычетов по модулю 10. 10. Выпишите пять чисел из класса вычетов числа 2941 по модулю 17. 11. Докажите, что класс вычетов числа 1019 по модулю 18 является примитивным классом вычетов. 12. Найдите число примитивных классов вычетов по модулю 999. 13. Вычислите значение функции Эйлера от числа 1011. 14. Найдите остаток от деления числа 2010 2 на 5. 15. Найдите последнюю цифру числа 2010 2 16. Допустим, что Новый Год пришелся на понедельник. На какой день недели приходится в этом же году праздник 9-е мая? Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 1 Практическое занятие 4 Сравнения 1-й степени Краткое содержание: действия с классами вычетов, понятие группы, группа классов вычетов, таблица Кэли, понятие кольца и поля, кольцо классов вычетов, поле классов вычетов, реше- ние линейных уравнений в кольце классов вычетов, сравнения 1-й степени и методы их ре- шений. п.1. Теория п.1.1. Действия с классами вычетов Пусть m 1 – произвольное натуральное число, m a, b Z – два произ- вольных класса вычетов по модулю m. Определим сложение и умно- жение классов вычетов по следующим правилам: a b a b, a b a b Определение. Класс вычетов a b по модулю m называется суммой классов вычетов a и b по модулю m. Класс вычетов ab по модулю m называется произведением классов вычетов a и b по модулю m. Замечание. Из определений следует, что для сложения классов выче- тов достаточно из каждого слагаемого выбрать по одному представи- телю и сложить их. Полученная сумма представителей будет предста- вителем класса суммы. Аналогично для умножения классов. Можно доказать, что результат сложения и умножения классов вычетов по заданному модулю не зависит от выбора представителей этих классов. Так как число классов вычетов по модулю конечно, то для множе- ства m Z можно составлять таблицы сложения и умножения. Такие таблицы называются таблицами Кэли. Смотрите ниже, в пункте 3, примеры. Теорема. Множество примитивных классов вычетов замкнуто отно- сительно умножения, т.е. произведение двух примитивных классов вычетов есть примитивный класс вычетов: * m a,b Z , * m a b a b Z Последняя теорема позволяет составлять таблицу умножения для множества * m Z . Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 2 п.1.2. Понятие группы Пусть дано произвольное множество G. Что из себя представляют элементы множества G нас пока не будет интересовать. Это могут быть числа, функции, многочлены, векторы, классы вычетов или что- то другое, это неважно. Важно, что на множестве G определено сло- жение его элементов или умножение. Определение. Говорят, что на множестве G определена операция сложения (умножения), если для любых двух его элементов a,b G определен элемент a b G ( ab G ), который называется суммой (произведением) элементов а и b. Замечание. Если сумма a b (произведение ab ) любых элементов а и b множества G также является его элементом, то в этом случае гово- рят, что множество G замкнуто относительно операции сложения (умножения) его элементов. Если мы сами определяем на некотором множестве правило сложения или умножения, то мы должны позабо- титься о том, чтобы данное множество было замкнутым относительно определяемых операций. Определение. Пусть на множестве G определена операция сложения. Если существует такой элемент G , который обладает свойством: a G, a a a , тогда элемент называется нулевым элементом или просто нулем, и часто обозначается цифрой 0. Определение. Пусть на множестве G определена операция умноже- ния. Если существует такой элемент e G , который обладает свойст- вом: a G, ae ea a , тогда элемент е называется единичным элементом или просто едини- цей, и часто обозначается цифрой 1. Определение. Пусть на множестве G определена операция сложения и существует нулевой элемент 0 G . Пусть a G – какой-нибудь элемент множества G. Если существует элемент b G , для которого выполняется равенство: a b b a 0 , Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 3 тогда элемент b называется противоположным элементу а, и обозна- чается a Таким образом, по определению противоположного элемента a ( a) ( a) a 0 . Заметим, что из определения противоположного элемента следует, что элемент а является противоположным элементу a , т.е. a ( a) . Определение. Пусть на множестве G определена операция умноже- ния и существует единичный элемент e G . Пусть a G – какой- нибудь элемент множества G. Если существует элемент b G , для которого выполняется равенство: ab ba e , тогда элемент b называется обратным элементу а, и обозначается 1 a При этом сам элемент а называется обратимым элементом. Таким образом, по определению обратного элемента 1 1 a a a a e . Заметим, что из определения обратного элемента следует, что элемент а является обратным элементу 1 a , т.е. 1 1 a (a ) Определение. Операция сложения (умножения), определенная на множестве G, называется ассоциативной (подчиняется закону ассо- циативности), если для любых трех его элементов a,b,c G верно ра- венство (a b) c a (b c) ( (ab)c a(bc) ). Определение. Операция сложения (умножения), определенная на множестве G, называется коммутативной (подчиняется закону комму- тативности), если для любых двух его элементов a,b G верно равен- ство a b b a ( ab ba ). Определение. Множество G называется группой относительно опера- ции сложения, если на этом множестве определена операция сложе- ния, которая удовлетворяет следующим трем условиям, которые на- Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 4 зываются аксиомами группы: 1) сложение подчиняется закону ассоциативности; 2) в множестве G есть нулевой элемент G ; 3) для любого элемента a G в множестве G есть противоположный ему элемент a G Определение. Множество G называется группой относительно опера- ции умножения, если на этом множестве определена операция умно- жения, которая удовлетворяет следующим трем аксиомам: 1) умножения подчиняется закону ассоциативности; 2) в множестве G есть единичный элемент e G ; 3) любой элемент a G является обратимым в множестве G, то есть существует обратный ему элемент 1 a G . Определение. Группа G относительно операции сложения или умно- жения называется абелевой или коммутативной, если групповая опе- рация (т.е. сложение или умножение) подчиняется закону коммута- тивности. п.1.3. Понятие кольца и поля Определение. Множество А, на котором определены две алгебраиче- ские операции – сложение и умножение, называется кольцом, если относительно сложения множество А является абелевой группой, и выполняется условие (закон дистрибутивности умножения относи- тельно сложения): x, y,z A, x(y z) xy xz, (y z)x yx zx Определение. Если в кольце А существует единичный элемент от- личный от нулевого элемента, то кольцо А называется кольцом с еди- ницей. Определение. Если умножение в кольце А подчиняется закону ком- мутативности, то кольцо А называется коммутативным кольцом. Определение. Если в кольце А для некоторых его ненулевых элемен- тов a,b A, a 0 b верно равенство ab 0 , то элемент а называется левым делителем нуля, а элемент b – правым делителем нуля. Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 5 Замечание. В коммутативном кольце нет смысла различать левый и правый делители нуля, так как ab ba , поэтому говорят просто о де- лителях нуля. Определение. Если в кольце нет делителей нуля, тогда оно называет- ся кольцом без делителей нуля. Определение. Коммутативное кольцо с единицей и без делителей ну- ля называется областью целостности или просто областью. Определение. Коммутативное кольцо с единицей называется полем, если любой его ненулевой элемент является обратимым в этом коль- це. Другими словами, полем называется множество K, на котором опре- делены операции сложения и умножения, относительно которых множество K является коммутативным кольцом с единицей 1 K , причем 1 0 , где 0 K – нулевой элемент, и x K, x 0 существу- ет 1 x K . Теорема.__В_поле_нет_делителей_нуля._п.1.4._Кольцо_и_поле_классов_вычетов_Теорема.'>Теорема. В поле нет делителей нуля. п.1.4. Кольцо и поле классов вычетов Теорема. Множество классов вычетов по любому модулю является коммутативным кольцом с единицей. Теорема. Множество примитивных классов вычетов относительно их умножения является коммутативной группой. Таким образом, m Z – кольцо классов вычетов по модулю m, * m Z – группа примитивных классов вычетов по модулю m. Теорема. Кольцо классов вычетов по простому модулю является по- лем. Пусть р – простое число, тогда p Z {0, 1,...,p 1} – поле классов вы- четов по простому модулю р. Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 6 Теорема. Класс вычетов a по модулю m является обратимым элемен- том в кольце классов вычетов m Z тогда и только тогда, когда класс вычетов a является примитивным классом вычетов по данному моду- лю m. Теорема. В поле классов вычетов по простому модулю линейное уравнение a x b имеет единственное решение 1 x (a) b . Теорема. В кольце классов вычетов по произвольному модулю m ли- нейное уравнение a x b разрешимо тогда и только тогда, когда D | b , где D D(a,m) . Если это уравнение разрешимо, то оно имеет D решений. Если 0 x – какое-нибудь решение данного уравнения, то ос- тальные D 1 решений можно найти по формуле 0 m x x k D , где число k пробегает числа 1, 2, …, D – 1. Замечание. Уравнение a x b в кольце классов вычетов по модулю m равносильно сравнению ax b (mod m) . Поэтому последние теоре- мы можно сформулировать на языке сравнений. Эти теоремы состав- ляют теорию сравнений 1-й степени, смотрите следующий пункт. п.1.5. Сравнения 1-й степени Определение. Пусть m 1 – произвольное натуральное число, а и b – произвольные целые числа. Сравнение ax b (mod m) , где х – неизвестное целое число, называется сравнением первой сте- пени с одним неизвестным. Замечание. Пусть r – произвольный класс вычетов по модулю m, то- гда, по определению, r {x Z | x r (mod m)} , т.е. это множество описывается как множество всех целых чисел х, удовлетворяющих сравнению x r (mod m) Далее, так как Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 7 x r (mod m) m | x r x r tm , где t Z , то x r (mod m) x r tm, t Z . В дальнейшем, именно так мы и будем записывать классы вычетов по заданному модулю. Очевидно, что если целое число 0 x удовлетворяет сравнению ax b (mod m) , т.е. 0 ax b (mod m) , то и любое число 0 x x tm, t Z из класса вычетов 0 x x (mod m) также будет удов- летворять этому сравнению: 0 a(x tm) b (mod m) Отсюда следует вывод, что решением сравнения является не отдель- ное число 0 x , а класс вычетов по данному модулю 0 x x (mod m) , что позволяет ввести следующее определение. Определение. Решением сравнения ax b (mod m) называется класс вычетов 0 x x (mod m) , удовлетворяющий данному сравнению. Теорема. Сравнение ax 1 (mod m) разрешимо тогда и только тогда, когда D(a,m) 1 . Если это сравнение разрешимо, то оно имеет един- ственное решение 0 x x (mod m) Теорема. Если D(a,m) 1 , то для любого целого числа b сравнение ax b (mod m) имеет единственное решение 0 x b x (mod m) , где 0 x x (mod m) – решение сравнения ax 1 (mod m) Теорема. Сравнение ax b (mod m) разрешимо тогда и только тогда, когда D | b , где D D(a,m) . Если сравнение разрешимо, то оно имеет точно D решений: 0 m x x k (mod m), k 0,1,...,D 1 D , где 0 m x x (mod ) D – решение сравнения a b m x (mod ) D D D Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 8 п.1.6. Методы решения сравнений 1-й степени Как следует из теорем предыдущего пункта, достаточно научиться решать сравнения вида ax 1 (mod m), D(a,m) 1 . В основном применяется один из следующих трех методов. 1-й метод. Применяется в случаях, когда модуль m является неболь- шим натуральным числом. По сути, это метод перебора. Так как ре- шением сравнения является один из классов вычетов по модулю m, то выписываем стандартную полную систему вычетов по этому модулю {0,1,...,m 1} и последовательно подставляем в сравнение ax 1 (mod m) вместо не- известной х числа 0, 1, …, m 1 . Так как сравнение разрешимо и име- ет единственное решение, то только одно из этих чисел будет удовле- творять сравнению. Таким образом, решением сравнения будет класс вычетов 0 x x (mod m) , где 0 x одно из чисел множества {0,1,...,m 1} , для которого сравнение 0 ax 1 (mod m) оказывается верным. 2-й метод. Используем теорему Эйлера (m) a 1 (mod m) Умножим обе части сравнения ax 1 (mod m) на число равное (m) 1 a : (m) 1 (m) 1 a ax a (mod m) , отсюда, в силу теоремы Эйлера, получаем решение сравнения: (m) 1 x a (mod m) Замечание. Формально решение сравнения найдено, но принято на- ходить в классе вычетов наименьший неотрицательный вычет (m) 1 a r (mod m), r {0,1,...,m 1} , и записывать ответ в виде x r (mod m) 3-й метод. Используется алгоритм Евклида, с помощью которого можно найти линейное представление НОД. Исходное сравнение ax 1 (mod m) равносильно уравнению ax tm 1 с двумя неизвестными х и t. Так как D(a,m) 1 , то существуют такие целые числа 0 x x и 0 t t , что 0 0 ax mt 1 . Метод вычисления этих чисел описан ранее в ПЗ 1. Тогда класс вычетов 0 x x (mod m) будет искомым. Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 9 п.2. Список задач Список №1 1. Составить таблицы сложения и умножения для классов вычетов по заданному модулю m. 2. Составить таблицу умножения для примитивных классов вычетов по заданному модулю m. 3. С помощью таблицы сложения классов вычетов по заданному мо- дулю найти для каждого класса вычетов противоположный ему класс вычетов. 4. С помощью таблицы умножения классов вычетов по заданному мо- дулю найти все делители нуля. 5. С помощью таблицы умножения классов вычетов по заданному мо- дулю найти все обратимые классы вычетов, и найти обратные им классы вычетов. 6. С помощью таблицы умножения примитивных классов вычетов по заданному модулю найти для каждого примитивного класса выче- тов обратный ему класс вычетов. 7. Решить линейное уравнение в кольце классов вычетов по заданному модулю. 8. Определить, разрешимо ли данное сравнение 1-й степени, и если разрешимо, то сколько решений оно имеет. 9. Решить данное сравнение 1-й степени методом перебора. 10. Решить данное сравнение 1-й степени с помощью теоремы Эйлера. 11. Решить данное сравнение 1-й степени с помощью алгоритма Евк- лида. |