Рабочая программа учебной дисциплины Основы теории чисел

Автор публикации:

Дата публикации:

Краткое описание: ...

Государственное бюджетное профессиональное

образовательное учреждение

«Колледж автоматизации

и информационных технологий № 20»















РАБОЧАЯ ПРОГРАММА



Общеобразовательной учебной дисциплины

«Основы теории чисел»

Специальность:

10.02.03 информационная безопасность автоматических систем

уровень подготовки: базовый













Москва

2016



ОДОБРЕНО


на заседании ПЦК "Информационная безопасность автоматических систем"


Протокол № _ от «__» 20__ г.


Председатель

____________ /Бавыкин В.В./

Программа учебной дисциплины разработана в соответствии с требованиями ФГОС по специальности:

10.02.03 информационная безопасность автоматических систем и учебным планом ГБПОУ КАИТ № 20



УТВЕРЖДАЮ


Руководитель учебного структурного подразделения «1М»


_____________________________/Мельников С. П./


«_____» ________________________20__ г.



СОГЛАСОВАНО


Зав. учебно-методическим отделением


_____________________________/______________/


«_____» ________________________20__ г.



Разработчик (автор): Филиппова Зоя Михайловна, преподаватель,

высшая квалификационная категория_________________________________

Ф.И.О., должность, квалификационная категория

_____________________________________________________________________________________________





Рецензент:

Внешний: _______________________________________________

(Ф.И.О., место работы, должность, квалификационная категория (ученая степень, звание)








[link] ПРИЛОЖЕНИЕ 1


Контрольная работа по ТЕОРИИ ЧИСЕЛ



вариант-ОБРАЗЕЦ


  1. Найти НОД трёх чисел: 19074, 13566, 8211.


Решение. Используем свойство (19074, 13566, 8211) = ((19074, 13566), 8211).

Сначала находим НОД(19074, 13566) = 102, а затем НОД(102, 8211) = 51.












Таким образом, НОД(19074, 13566, 8211) = 51.


Ответ: НОД(19074, 13566, 8211) = 51.


  1. Найти все x = 5711 со свойством  (x) = 2310000.


Решение. Если  0,  0,  0, то  (5711) = (5)(7)(11) = = 5–147–1611–110 = 24357–111–1.

С другой стороны, 2310000 = 24354711. Из равенства 24357–111–1 = = 24354711 находим (используя единственность канонического разложения), что  = 4,  = 2,  = 2, т.е. x = 5472112.

Исследуем теперь случаи, когда некоторые из показателей , , нулевые. Из предыдущих вычислений видно, что 3, 7,11 участвуют в каноническом разложении числа 2310000 = 24354711, так что  0,  0. Если  = 0, то (x) = =  (711) = (7)(11) = 7–1611–110 = 22357–111–1и равенство (x) = = 2310000 = 24354711невозможно.

Таким образом, найденное выше решение единственно.


Ответ: x = 5472112.


  1. Найти количество натуральных чисел x со свойствами:

x< 450 и НОД(x, 450) = 15.

Решение. Любое число xс указанными в условии свойствами имеет вид x = = 15y, где 1y< 30 (т.к. 15 x< 450). При этом условие НОД(x, 450) = 15означает, что НОД(y, [pic] ) = 1, т.е. НОД(y, 30) = 1. Таким образом, задача сводится к отысканию всех чисел yсо свойствами 1y< 30и НОД(y, 30) = 1. Таких чисел (30) = (235) = (2)(3)(5) = 124 = 8.


Ответ: 8 чисел.


  1. Решить сравнение: а) тремя способами 10х  12 (mod 14),

б) методом цепных дробей 101х  130 (mod113).


Решение.а)Метод подбора.Сравнение 10х  12 (mod 14)имеет два класса решений по модулю 7, т.к. НОД(10, 14) = 2 | 12. При этом исходное сравнение равносильно 5x 6 (mod 7), в котором НОД(5, 7) = 1, так что это сравнение имеет единственный класс решений по модулю 7.

Последовательно подставляя в сравнение 5x 6 (mod 7)значения x = 0, 1, 2, 3, 4, 5, 6, находим 50 = 0 [pic] 6 (mod 7), 51 = 5 [pic] 6 (mod 7), 52 = 10 3 [pic] 6 (mod 7), 53 = 15 1 [pic] 6 (mod 7), 54 = 20  6 (mod 7). Таким образом, решением сравнения 5x 6 (mod 7)будет класс x 4 (mod 7), а решениями исходного сравнения – классы x 4+07 = 4 (mod 14), x 4+17 = 11 (mod 14).

Ответ: x 4 (mod 14), x 11 (mod 14).


Искусственный приём.Так же как и выше, вначале решаем сравнение 5x 6 (mod 7). Для этого будем искать xв виде x [pic] (mod 7), где tвыбирается так, чтобы дробь принимала целое значение. Перебирая t = 0, 1, 2, находим t = 2и x 4 (mod 7).Выписываем решения исходного решения: x 4+07 = 4(mod 14), x 4+17 = 11 (mod 14).


Ответ: x 4 (mod 14), x 11 (mod 14).


Метод Эйлера.Сравнение 10х  12 (mod 14)имеет два класса решений по модулю 7, т.к. НОД(10, 14) = 2 | 12. При этом исходное сравнение равносильно 5x 6 (mod 7), в котором НОД(5, 7) = 1, так что это сравнение имеет единственный класс решений по модулю 7.

Поскольку 5(7) 1 (mod 7), то умножая обе части сравнения 5x 6 (mod 7)на 5(7)–1, получим x5(7)–15x5(7)–16  56–16 525256  442  22 = 4 (mod 7). Таким образом, решением сравнения 5x 6 (mod 7)будет класс x 4 (mod 7), а решениями исходного сравнения – классы x 4+07 = 4 (mod 14), x 4+17 = 11 (mod 14).


Ответ: x 4 (mod 14), x 11 (mod 14).


б)Метод цепных дробей.Сравнение 101х  130 (mod113) имеет единственный класс решений, т.к НОД(101, 113) = 1 | 130. При этом исходное сравнение равносильно 101х  17 (mod113), которое и будем решать.

Разлагаем дробь [pic] в конечную цепную дробь:

Таким образом, [pic] = [1; 8, 2, 2, 2] – конечная цепная дробь порядка 4. Вычислим её значение, составив таблицу:


i

–1

0

1

2

3

4

ai

–

1

8

2

2

2

Pi

1

1

9

19

47

113

Qi

0

1

8

17

42

101


[pic]

Таким образом, 10147 – 11342 = 1 и значит, 10147  1 (mod 113), так что решением рассматриваемого сравнения 101х  17 (mod113) будет x 4717 = = 799  8 (mod 113).


Ответ: x 8 (mod 113).


  1. Решить сравнение с помощью индексов: 40х 10 3 (mod 17).


Решение. Упростим сравнение: 6х 10 3 (mod 17)и поскольку НОД(3, 17) = 1, последнее сравнение равносильно (после сокращения на 3) сравнению 2х 10 1 (mod 17), которое и будем решать.

Переходя к индексам по модулю (17) = 16, получимind(2) + 10ind(x) ind(1) (mod 16) или (вычисляяind(2) с помощью таблиц индексов)10ind(x) ind(1) – ind(2) 0 – 14  2 (mod 16).

Сравнение 10ind(x) 2 (mod 16)имеет два класса решений по модулю 16, т.к. НОД(10, 16) = 2 | 2.Это сравнение равносильно сравнению 5y 1 (mod 8), которое имеет единственный класс решений y 5 (mod 8). Значит сравнение 10ind(x) 2 (mod 16)имеет следующие решения: ind(x1)  5+08 = 5 (mod 16), ind(x2) 5+18 = 13 (mod 16).

По таблице антииндексов находим соответствующие решения x 5 (mod 17)и x 12 (mod 17).


Ответ: x 5 (mod 17) и x 12 (mod 17).


  1. Найти остаток от деления (15728 + 19 30)7 на 57.


Решение.1. Находим остаток от деления 15728 на 57:

15728  53 –4 (mod 57).

2. Находим остаток от деления 19 30на 57: 19 30 = (19 2) 15 = = 361 15 19 15 = (19 2)719  19 719  (19 2) 4 19 4 (19 2) 2 19 2 19 (mod 57).

3. Имеем (15728 + 19 30)7 (–4 + 19) 7 = 15 7 (mod 57).

4. Вычислим 15 7 = (15 2) 315  54 315  (–3) 315 = – 2715 = = –405  –6  51 (mod 57):


Ответ: остаток равен 51.


  1. Найти длину периода и длину предпериода при обращении обыкновенной дроби [pic] в десятичную.


Решение.1.Находим каноническое разложение знаменателя: 10500 = 105100 = = 2 25 337 = 2 25 321.

2. Находим длину предпериода: (длина предпериода) = max{2, 3} = 3.

3. Находим длину периода P21(10): 101 = 10 [pic] 1 (mod 21), 10 2 = 100 –5 [pic] 1 (mod 21), 10 3 10(–5)  –8 [pic] 1 (mod 21), 10 4 (–5) 24 [pic] 1 (mod 21), 10 5 104 –2 [pic] 1 (mod 21), 10 6 10(–2) 1 (mod 21).

Таким образом, (длина периода) = 6.


Ответ: длина предпериода равна 3, а длина периода – 6.




6.Вариант 0


  1. Найти НОД трёх чисел: 2226, 3213, 6489.

  2. Решить уравнение:  (7 х) = 294.

  3. Решить сравнение: а) тремя способами 7х  6 (mod 9),

б) методом цепных дробей 88х  324 (mod404).

  1. Решить сравнение с помощью индексов: 25х 7 –7 (mod 31).

  2. Найти остаток от деления 11 802 на 1000.

  3. Найти длину периода и длину предпериода при обращении обыкновенной дроби [pic] в десятичную.



Вариант 1


  1. Найти НОД трёх чисел: 3445, 4225, 5915.

  2. Найти все x = 5711со свойством  (x) = 42000.

  3. Решить сравнение: а) тремя способами 3х  1 (mod 11),

б) методом цепных дробей 365х  50 (mod 395).

  1. Решить сравнение с помощью индексов: 8х9 –17 (mod 41).

  2. Найти остаток от деления 19 2402 на 100.

  3. Найти длину периода и длину предпериода при обращении обыкновенной дроби [pic] в десятичную.




Вариант 2


  1. Найти НОД трёх чисел: 1073, 3683, 34481.

  2. Найти количество натуральных чисел xсо свойствами:

x< 975 и НОД(x, 975) = 13.

  1. Решить сравнение: а) тремя способами 18х  12 (mod 30),

б) методом цепных дробей 91х  143 (mod 222).

  1. Решить сравнение с помощью индексов: 7х13 + 23  0 (mod 47).

  2. Найти остаток от деления 1967 1968 на 11.

  3. Найти длину периода и длину предпериода при обращении обыкновенной дроби [pic] в десятичную.






Вариант 3


  1. Найти НОД трёх чисел: 1012, 1474, 4598.

  2. Решить уравнение:  (11 х) = 13310.

  3. Решить сравнение: а) тремя способами 39х  5 (mod 11),

б) методом цепных дробей 27х  25 (mod 119).

  1. Решить сравнение с помощью индексов: 9х11 + 1  0 (mod 43).

  2. Найти остаток от деления 109 345 на 14.

  3. Найти длину периода и длину предпериода при обращении обыкновенной дроби [pic] в десятичную.



Вариант 4


  1. Найти НОД трёх чисел: 988, 2014, 42598.

  2. Найти все x = 5711 со свойством  (x) = 330000.

  3. Решить сравнение: а) тремя способами 37х  16 (mod 11),

б) методом цепных дробей 82х  14 (mod 202).

  1. Решить сравнение с помощью индексов: 19х5 + 13  0 (mod 53).

  2. Найти остаток от деления 293 275 на 48.

  3. Найти длину периода и длину предпериода при обращении обыкновенной дроби [pic] в десятичную.



Вариант 5


  1. Найти НОД трёх чисел: 7975, 2585, 13915.

  2. Найти количество натуральных чисел, не превосходящих 120 и не взаимно простых с числом 30.

  3. Решить сравнение: а) тремя способами 62х  5 (mod 13),

б) методом цепных дробей 243х  271 (mod 317).

  1. Решить с помощью индексов: 32 х 15 (mod 37).

6. Найти остаток от деления: 117 53 на 11.

  1. Найти длину периода и длину предпериода при обращении обыкновенной дроби [pic] в десятичную.






Вариант 6


  1. Найти НОД трёх чисел: 874, 1518, 20142.

  2. Решить уравнение (15x) = 9000.

  3. Решить сравнение: а) тремя способами 11х  15 (mod 24),

б) методом цепных дробей 92х  20 (mod 284).

  1. Решить сравнение с помощью индексов: х2 54 (mod 67).

  2. Найти остаток от деления 5 80 + 7 100 на 13.

  3. Найти длину периода и длину предпериода при обращении обыкновенной дроби [pic] в десятичную.



Вариант 7


  1. Найти НОД трёх чисел: 9911, 952, 2227.

  2. Найти все x = 57со свойством (x) = 147000.

  3. Решить сравнение: а) тремя способами 6х  8 (mod 10),

б) методом цепных дробей 221х  111 (mod 360).

  1. Решить сравнение с помощью индексов: х2 37 (mod 41).

  2. Найти остаток от деления 2 100 + 3 100 на 5.

  3. Найти длину периода и длину предпериода при обращении обыкновенной дроби [pic] в десятичную.



Вариант 8


  1. Найти НОД трёх чисел: 1253, 406, 252.

  2. Найти количество натуральных чисел xсо свойствами:

x< 2476и НОД(x, 2476) = 619.

  1. Решить сравнение: а) тремя способами 8х  14 (mod 18),

б) методом цепных дробей 113х  89 (mod 311).

  1. Найти сравнение с помощью индексов: х2 58 (mod 61).

  2. Найти остаток от деления 11 1841 на 7.

  3. Найти длину периода и длину предпериода при обращении обыкновенной дроби [pic] в десятичную.








Вариант 9


  1. Найти НОД трёх чисел: 2743, 3587, 6963.

  2. Найти количество натуральных чисел не превосходящих 2272 и взаимно простых с числом 568 .

  3. Решить сравнение: а) тремя способами 10х  4 (mod 14),

б) методом цепных дробей 95х  59 (mod 308).

  1. Решить сравнение с помощью индексов: х15 38 (mod 59).

  2. Найти остаток от деления 23 2342 на 14.

  3. Найти длину периода и длину предпериода при обращении обыкновенной дроби [pic] в десятичную.


9
Читать полностью »