АГ ПЗ 1-35 (полный вариант). Практическое занятие 1 Решето Эратосфена

• Название: Практическое занятие 1 Решето Эратосфена
• Анкор: АГ ПЗ 1-35 (полный вариант).pdf
• Дата: 23.02.2018
• Размер: 2.3 Mb.
• Имя файла: АГ ПЗ 1-35 (полный вариант).pdf
• Тип: Занятие; #15834
• страница: 5 из 44

Список №2
1. Задачи на доказательство.
2. Решение простейших линейных диофантовых уравнений 1-й степе- ни с двумя неизвестными.
п.3. Примеры
Пример 1.
Составить таблицы сложения и умножения для классов вычетов по модулю 10.
Решение. Выпишем все классы вычетов по модулю 10:
10
Z
{0, 1,2,...,9}

Пусть {0,1,2,...,9} – полная система наименьших неотрицательных вычетов по модулю 10, и a,b {0,1,2,...,9}

– какие-то наименьшие не-
Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 10
отрицательные вычеты по модулю 10. По правилу сложения классов вычетов a b a b
  
. Если a b 10
 
, то число a b

является наи- меньшим неотрицательным вычетом в классе a b

. Если же a b 10
 
, то наименьшим неотрицательным вычетом в классе a b

будет число a b 10
 
и a b 10 a b
 
 
, так как a b a b 10 (mod10)
   
. Таким образом, при сложении классов выче- тов будем руководствоваться правилом: a b,
a b 10
a b a b 10, a b 10
 
 

  
 
 

Аналогично, при умножении классов, a b ab r
 

, где ab r (mod10)

, и r – наименьший неотрицательный вычет числа ab по модулю 10. Например,
7 8 15 15 10 5, 15 5 (mod10)
 




,
7 8 56 6, 56 6 (mod10)
 


,
Замечание.
Для удобства записи мы не ставим в таблицах черточку над числом в обозначении класса вычета.
Ответ:
0 1 2 3 4 5 6 7 8 9 0 0 1 2 3 4 5 6 7 8 9 1 1 2 3 4 5 6 7 8 9 0 2 2 3 4 5 6 7 8 9 0 1 3 3 4 5 6 7 8 9 0 1 2 4 4 5 6 7 8 9 0 1 2 3 5 5 6 7 8 9 0 1 2 3 4 6 6 7 8 9 0 1 2 3 4 5 7 7 8 9 0 1 2 3 4 5 6 8 8 9 0 1 2 3 4 5 6 7 9 9 0 1 2 3 4 5 6 7 8


Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 11 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 8 9 2 0 2 4 6 8 0 2 4 6 8 3 0 3 6 9 2 5 8 1 4 7 4 0 4 8 2 6 0 4 8 2 6 5 0 5 0 5 0 5 0 5 0 5 6 0 6 2 8 4 0 6 2 8 4 7 0 7 4 1 8 5 2 9 6 3 8 0 8 6 4 2 0 8 6 4 2 9 0 9 8 7 6 5 4 3 2 1

Пример 2.
Составить таблицу умножения для примитивных классов вычетов по модулю 10.
Решение. Составим приведенную систему вычетов по модулю 10. Для этого, определяем какие из чисел:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 взаимно простые с модулем 10 и выписываем их:
1, 3, 7, 9.
Следовательно, множество примитивных классов вычетов по модулю
10 имеет 4 элемента:
*
10
Z
{1, 3, 7, 9}

Это множество образует группу относительно умножения. Таблицу умножения можно составить пользуясь таблицей умножения для кольца классов вычетов
10
Z . Смотрите предыдущий пример.
Ответ:
1 3 7 9 1 1 3 7 9 3 3 9 1 7 7 7 1 9 3 9 9 7 3 1

Замечание.
Так как операции сложения и умножения классов вычетов являются коммутативными, то это отражается в таблицах. Числа,
Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 12
стоящие в таблицах симметрично главной диагонали (слева направо) являются равными. Это можно использовать при их заполнении.
Пример 3.
Для каждого класса вычетов по модулю 10 найти противо- положный ему класс вычетов.
Решение. Используем определение противоположного элемента. В нашем случае, если a 0

и a b 0
 
, то по определению: a b
  . Из таблицы сложения классов вычетов по модулю 10 находим все проти- воположные классы вычетов. Впрочем, легко заметить, что a b 10 (mod10)
 
, откуда следует, что b 10 a (mod10)


и a b 10 a
  
 . Таким же образом доказывается формула для нахож- дения противоположного класса вычетов по любому модулю m: a m a
   .
Ответ: 0 0, 1 9, 2 8, 3 7, 4 6, 5 5, 6 4
              ,
7 3, 8 2, 9 1
      .
Пример 4.
Найти все делители нуля в кольце классов вычетов по мо- дулю 10.
Решение. Из определения делителей нуля следует, что два ненулевых класса вычетов a, b будут делителями нуля, если a b 0
 
. Осталось внимательно рассмотреть таблицу умножения классов вычетов по мо- дулю 10: 2 5 0, 4 5 0, 6 5 0, 8 5 0
 
 
 
  .
Ответ: 2, 4, 5, 6, 8 .
Замечание.
Из определения делителей нуля в нашем случае следует, что a b ab 0
 

или ab 0 (mod m)

. Если бы число а было взаимно просто с модулем m, в сравнении то на него можно было бы сокра- тить: b 0 (mod m)

. Но это означает, что b 0

, что противоречит оп- ределению делителя нуля. Следовательно, если класс вычетов a
по модулю m является делителем нуля, то D(a,m) 1
 , т.е. число а не вза- имно простое с модулем m. Легко доказать и обратное утверждение: если
D(a,m) 1
 , то класс вычетов a
по модулю m является делителем нуля. Отсюда следует, что делителями нуля являются те и только те классы вычетов, которые не являются примитивными, т.е. не являют-

Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 13 ся взаимно простыми с модулем.
Пример 5.
Найти все обратимые классы вычетов по модулю 10 и об- ратные им классы вычетов.
Решение. Обратимыми классами вычетов являются только примитив- ные классы вычетов и только они. Поэтому, по модулю 10 обратимы- ми классами вычетов являются классы 1, 3, 7, 9 . Если класс вычетов a
является обратимым, то обратный ему класс вычетов
 
1
a

удовле- творяет равенству
 
1
a a
1



, т.е. является решением линейного уравнения a x 1
  или сравнения ax 1(mod m)

Из таблицы примера 2 находим:
 
 
 
 
1 1
1 1
1 1, 3 7, 7 3, 9 9








Этот же результат мы получим, если будем решать сравнения:
1 x 1 (mod10), 3x 1 (mod10), 7x 1 (mod10)
 


,
9x 1 (mod10)

Ответ:
 
 
 
 
1 1
1 1
1 1, 3 7, 7 3, 9 9








Пример 6.
В кольце классов вычетов по модулю 10 решить линейное уравнение
3 x 5
 
Решение. Линейное уравнение a x b
 
в кольце классов вычетов по модулю m равносильно решению сравнения ax b (mod m)

. Но дан- ное уравнение можно решить с помощью таблицы умножения классов вычетов по модулю 10 (смотрите пример 1). По таблице находим:
3 5 5
 
Ответ: x 5

Пример 7.
Определить, разрешимо ли сравнение, и если да, то сколь- ко решений оно имеет: а) 12x 15(mod14)

; б) 12x 15(mod35)

; в) 12x 15(mod9)

Решение. Сравнение ax b (mod m)

разрешимо тогда и только тогда, когда
D(a,m) | b . Если сравнение разрешимо, то оно имеет
D D(a,m)

решений.
Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 14
а)
D(12,14) 2 | 15
  . Сравнение 12x 15(mod14)

не имеет решений. б)
D(12,35) 1
 . Сравнение 12x 15(mod35)

разрешимо и имеет един- ственное решение. в)
D(12,9) 3
 . Сравнение 12x 15(mod9)

разрешимо и имеет 3 реше- ния.
Ответ: а) не разрешимо; б) имеет единственное решение; в) имеет 3 решения.
Пример 8.
Решить сравнение
5x 3(mod 7)

методом перебора.
Решение. Так как
D(5,7) 1
 , то сравнение имеет единственное реше- ние. Последовательно подставляем в сравнение вместо неизвестной х числа 0, 1, 2, 3, 4, 5, 6, пока не получим верное сравнение:
5 0 3(mod 7), 5 1 3(mod 7), 5 2 3(mod 7)
 
 
 


Ответ: x 2 (mod 7)

Пример 9.
Решить сравнение
5x 3(mod17)

с помощью теоремы Эй- лера.
Решение. Так как коэффициент при неизвестной – число 5 взаимно простое с модулем 17, то сравнение имеет единственное решение, и для его нахождения можно применить формулу:
(m) 1
(17) 1
x a b (mod m) 5 3 (mod17)







Так как
(17) 16


, то
15
x 5 3 (mod17)


. Найдем наименьший неотри- цательный вычет числа
15 5 по модулю 17:
4 4
5 625 17 36 13 5
13 (mod17)
4 (mod17)



 

 
,
3 3
5 125 17 7 6 5
6 (mod17)


  

Отсюда находим
15 4 3 3
3 5
(5 ) 5
( 4) 125 (mod17) ( 64) 6 (mod17)

  

 

Так как, 64 17 ( 4) 4
 
   , то
15 5
( 64) 6 (mod17) 4 6 (mod17) 7 (mod17)
 

 

Подставляя в решение найденный наименьший неотрицательный вы- чет, получаем:
15
x 5 3 (mod17) 7 3 (mod17) 4 (mod17)


 

Ответ: x 4 (mod17)


Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 15
Пример 10.
Решить сравнение
35x 83(mod107)

с помощью алго- ритма Евклида.
Решение. С помощью алгоритма Евклида находим НОД коэффициен- та при неизвестном и модуля.
107 35 3 2

 
,
35 2 17 1
  
,
2 1 2
  .
Последний ненулевой остаток равен 1, и D(35,107) 1
 . Следователь- но, данное сравнение имеет единственное решение. Сначала, мы най- дем линейное представление найденного НОД, т.е. найдем такие чис- ла х, у, для которых выполняется равенство:
107x 35y 1

 .
Из алгоритма Евклида выражаем остатки:
2 107 35 3



,
1 35 2 17

 
Подставим во второе равенство первое:
1 35 2 17 35 (107 35 3) 17 107 ( 17) 35 52

 


  

 


Переходим в последнем равенстве к сравнению по модулю 107:
35 52 1 (mod107)


Теперь умножим исходное сравнение 35x 83(mod107)

на 52:
52 35x 52 83(mod107)



, откуда, с учетом предыдущего сравнения, получаем: x 52 83(mod107) 4316(mod107)



Осталось найти наименьший неотрицательный вычет числа 4316 по модулю 107. Делим 4316 на 107 с остатком:
4316 107 40 36



Следовательно, 4316 36 (mod107)

и x 36(mod107)

Ответ: x 36(mod107)

Пример 11.
Решить сравнение 35x 45(mod 65)

Решение. Так как
D(35,65) 5D(7,13) 5 | 45


, то сравнение имеет 5 решений по модулю 65. Сокращаем сравнение на 5:
35 45 65
x
(mod
)
5 5
5

Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 16
Упрощаем получившееся сравнение:
7x 9 (mod13)
( 6)x ( 4) (mod13)

 
 
, так как
7 6 (mod13), 9 4 (mod13)
 
 
Сокращая сравнение
( 6)x ( 4) (mod13)

 
на –2, получаем:
3x 2 (mod13)

Получившееся сравнение легко решить методом перебора: x 5 (mod13)

Обозначим
0
x
5
 . Тогда по формуле решений:
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

, находим:
65
x 5
k (mod 65), k 0,1,2,3,4 5
 

Подставляя значения k, получаем: x 5 (mod 65), x 5 13 (mod 65) 18 (mod 65)

 

, x 5 13 2 (mod 65) 31 (mod65)
  

, x 5 13 3 (mod 65) 44 (mod65)
  

, x 5 13 4 (mod 65) 57 (mod65)
  

Ответ: x 5 (mod 65), x 18 (mod 65), x 31 (mod 65)



, x 44 (mod 65), x 57 (mod 65)


Пример 12.
Решить в целых числах уравнение с двумя неизвестными
6x 11y 3

 .
Решение. Перейдем в уравнении к сравнению по модулю 11 и решим его:
6x 11y 3 (mod11)
6x 3 (mod11)
2x 1 (mod11)






, откуда находим x 6 (mod11)

. Все числа из последнего класса выче- тов можно записать в виде x 6 11t, t Z
 
 . Подставим это выражение в исходное уравнение:
6(6 11t) 11y 3 11y
33 66t y
3 6t


 
  
    .
Таким образом, все решения исходного уравнения имеют вид:

Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 17 x 6 11t y
3 6t
 

   

, где t – пробегает все множество целых чисел. Можно до- казать, что если t – пробегает все множество целых чисел, то соответ- ствующие пары чисел
(x, y) (6 11t, 3 6t)
 
 
пробегают все множество решений данного уравнения.
Ответ: x 6 11t
, t Z
y
3 6t
 


   

п.4. Задачи
Задачи для аудиторного решения 4
1. Составьте таблицы сложения и умножения для классов вычетов по модулю: а) 2; б) 8; в) 12.
2. Составьте таблицу умножения для примитивных классов вычетов по модулю: а) 2; б) 8; в) 12.
3. Для каждого класса вычетов по модулю 12 найдите противополож- ный ему класс вычетов.
4. Найдите все делители нуля в кольце классов вычетов по модулю 12.
5. Найдите все обратимые классы вычетов по модулю 12 и обратные им классы вычетов.
6. С помощью таблицы умножения примитивных классов вычетов по модулю 8 найдите для каждого примитивного класса вычетов об- ратный ему класс вычетов.
7. В кольце классов вычетов по модулю 12 решите линейное уравне- ние
5 x 2
 
8. В группе примитивных классов вычетов по модулю 12 решите уравнение
7 x 5
 
9. Определите, разрешимо ли сравнение, и если да, то сколько реше- ний оно имеет: а) 3x 25(mod 42)

; б) 13x 15(mod36)

; в)
20x 64(mod396)

10. Решите следующие сравнения методом перебора: а)
5x 3(mod8)

; б) 4x 3(mod9)

; в) 8x 10(mod11)

11. Следующие сравнения решите с помощью теоремы Эйлера: а)
2x 13(mod 21)

; б) 5x 44(mod51)

12. Следующие сравнения решите с помощью алгоритма Евклида: а)
102x 133(mod319)

; б) 235x 613(mod 661)

Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 18 13. Решите сравнения: а)
16x 2 (mod18)

; б)
42x
24 (mod 78)
 
; в)
33x 192 (mod 237)

Задачи повышенного уровня сложности 4
14. Доказать, что сложение и умножение классов вычетов по заданно- му модулю не зависит от выбора их представителей.
15. Объясните, почему множество всех целых неотрицательных чисел не является группой ни относительно сложения, ни относительно умножения.
16. Докажите, что множество всех целых чисел является областью.
17. Докажите, что кольцо классов вычетов по простому модулю явля- ется полем.
18. Докажите, что в любом поле нет делителей нуля.
19. Определить, является ли множество все целых чисел кратных 3 замкнутым относительно сложения и умножения, и образует ли оно группу, кольцо или поле.
20. Решите в целых числах уравнение: а) 5x 7y 1

 ; б) 15x 17y 11

 ; в) 105x 173y 101


Домашнее задание 4. Сравнения 1-й степени
1. Составьте таблицы сложения и умножения для классов вычетов по модулю 9.
2. Используя таблицу сложения классов вычетов по модулю 9, найди- те для каждого класса вычетов противоположный ему класс выче- тов.
3. Используя таблицу умножения классов вычетов по модулю 9, най- дите все делители нуля.
4. Составьте таблицу умножения для примитивных классов вычетов по модулю 9 и, используя эту таблицу, найдите для каждого при- митивного класса вычетов обратный ему класс вычетов.
5. Решите сравнение 10x 9 (mod19)

тремя различными способами.
6. Решите сравнение 30x 27 (mod57)

Самостоятельная работа 4
Вариант 1.
1. Определение суммы классов вычетов по заданному модулю m.
2. Составьте таблицу сложения для кольца
4
Z .

Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 19 3. Решите сравнение
4x 1 (mod5)

Вариант 2.
1. Определение произведения классов вычетов по заданному модулю m.
2. Составьте таблицу умножения для кольца
4
Z .
3. Решите сравнение 4x 5 (mod 7)

Вариант 3.
1. Определение сравнения 1-й степени с одним неизвестным по задан- ному модулю m.
2. Составьте таблицу умножения для группы
*
4
Z .
3. Решите сравнение 4x 5 (mod17)

Вариант 4.
1. Определение решения сравнения 1-й степени с одним неизвестным по заданному модулю m.
2. Составьте таблицу умножения для группы
*
5
Z .
3. Решите сравнение 5x 1 (mod36)

п.5. Вопросы и задачи для самоконтроля 4
Обозначения
1. Обозначение нулевого элемента относительно операции сложения.
2. Обозначение единичного элемента относительно операции умно- жения.
3. Обозначение противоположного элемента.
4. Обозначение обратного элемента.
Определения
1. Определение суммы классов вычетов по заданному модулю.
2. Определение произведения классов вычетов по заданному модулю.
3. Определение операции сложения на произвольном множестве.
4. Определение операции умножения на произвольном множестве.
5. Определение множества замкнутого относительно операции сложе- ния.
6. Определение множества замкнутого относительно операции умно- жения.
7. Определение нулевого элемента относительно сложения.
8. Определение единичного элемента относительно умножения.
9. Определение противоположного элемента.
Головизин В.В. ПЗ по курсу «Алгебра и геометрия», УдГУ, Ижевск – 2010, ПЗ 4, с.21 20 10. Определение обратимого элемента.
11. Определение обратного элемента.
12. Определение закона ассоциативности сложения.
13. Определение закона ассоциативности умножения.
14. Определение группы относительно сложения.
15. Определение группы относительно умножения.
16. Определение закона коммутативности сложения.
17. Определение закона коммутативности умножения.
18. Определение абелевой (коммутативной) группы.
19. Определение кольца.
20. Определение кольца с единицей.
21. Определение коммутативного кольца.
22. Определение левого (правого) делителя нуля.
23. Определение кольца без делителей нуля.
24. Определение области (области целостности).
25. Определение поля.
26. Определение сравнения 1-й степени с одним неизвестным.
27. Определение решения сравнения 1-й степени с одним неизвест- ным.