Государственное
бюджетное профессиональное
образовательное
учреждение
«Колледж автоматизации
и информационных технологий № 20»
РАБОЧАЯ ПРОГРАММА
Общеобразовательной учебной
дисциплины
«Основы теории чисел»
Специальность:
10.02.03 информационная безопасность
автоматических систем
уровень подготовки: базовый
Москва
2016
ОДОБРЕНО
|
|
на заседании ПЦК "Информационная
безопасность автоматических систем"
Протокол № _ от «__» 20__ г.
Председатель
____________ /Бавыкин В.В./
|
Программа учебной
дисциплины разработана в соответствии с требованиями ФГОС по специальности:
10.02.03 информационная
безопасность автоматических систем и учебным планом ГБПОУ
КАИТ № 20
|
УТВЕРЖДАЮ
Руководитель учебного структурного подразделения «1М»
_____________________________/Мельников С. П./
«_____» ________________________20__ г.
СОГЛАСОВАНО
Зав. учебно-методическим отделением
_____________________________/______________/
«_____» ________________________20__ г.
Разработчик
(автор): Филиппова Зоя Михайловна, преподаватель,
высшая квалификационная категория_________________________________
Ф.И.О., должность, квалификационная категория
_____________________________________________________________________________________________
Рецензент:
Внешний: _______________________________________________
(Ф.И.О., место работы, должность, квалификационная
категория (ученая степень, звание)
СОДЕРЖАНИЕ
|
стр.
|
1. Паспорт рабочей
программы общеобразовательной учебной дисциплины
|
4
|
2. Структура и
содержание общеобразовательной учебной дисциплины
|
10
|
3. Условия
реализации рабочей программы общеобразовательной учебной дисциплины
|
15
|
4. Контроль и
оценка результатов освоения общеобразовательной учебной дисциплины
|
19
|
1. ПАСПОРТ РАБОЧЕЙ ПРОГРАММЫ ОБЩЕОБРАЗОВАТЕЛЬНОЙ УЧЕБНОЙ ДИСЦИПЛИНЫ «ОСНОВЫ ТЕОРИИ ЧИСЕЛ»
1.1. Область применения программы: реализация
среднего профессионального образования в пределах ППСЗ по специальности:
10.02.03 информационная безопасность
автоматических систем
в
соответствии c примерной программой по учебной дисциплине
«ОСНОВЫ ТЕОРИИ ЧИСЕЛ», с учетом профиля получаемого профессионального
образования.
1.2. Место дисциплины в
структуре образовательной программы.
Дисциплина “Основы теории чисел” относится к базовой
части Федерального государственного образовательного стандарта среднего
профессионального образования (ФГОС ПО) по направлению 10.02.03
информационная безопасность автоматических систем, являясь частью
блока “Алгебра и теория чисел”.
Дисциплина “Основы теории чисел” базируется на знаниях,
полученных в рамках школьного курса математики.
В ходе изучения дисциплины “Основы теории чисел” студенты
должны освоить основные понятия и методы теории чисел. Освоение дисциплины
предусматривает приобретение навыков работы с соответствующими учебниками,
учебными пособиями и монографиями.
1.3 Цели
и задачи учебной дисциплины – требования к результатам освоения дисциплины:
Рабочая программа учебной дисциплины «Основы теории чисел»
ориентирована на достижение следующих целей:
· овладение студентами математическим аппаратом теории чисел,
фундаментальными теоретическими положениями этой науки;
· воспитание и развитие их математической культуры;
· осознание ими прикладного характера математики в целом и теории чисел в
частности.
Курс теории чисел должен решать следующие задачи:
·
вооружать студентов фундаментальными
теоретическими знаниями по теории чисел;
·
давать достаточный терминологический и
понятийный запас, необходимый для самостоятельного изучения специальной
литературы;
·
учить навыкам формулировки разнообразных
теоретических и практических задач на языке теории чисел;
·
предлагать строгие формальные
доказательства основных результатов, развивая культуру мышления студентов;
·
демонстрировать наглядность большинства
идей излагаемой теории, открывающую дорогу многим приложениям;
·
демонстрировать применение теории чисел
для решения разнообразных практических задач;
·
пополнить алгоритмический запас студентов,
позволяющий им решать типовые задачи;
·
обеспечить разнообразный материал для
самостоятельной работы.
В результате изучения дисциплины “Теория чисел” у студентов формируются
навыки в следующих основных видах деятельности, предусмотренные стандартом
профессионального образования:
научно-исследовательская и научно-изыскательская:
·
применение основных понятий, идей и
методов фундаментальных математических дисциплин для решения базовых задач;
·
решение математических проблем,
соответствующих направленности (профилю) образования, возникающих при
проведении научных и прикладных исследований;
·
подготовка обзоров, аннотаций, составление
рефератов и библиографии по тематике проводимых исследований;
· участие в работе семинаров, конференций и симпозиумов, оформление и
подготовка публикаций по результатам проводимых научно-исследовательских работ.
производственно-технологическая:
· использование математических методов обработки информации, полученной в
результате экспериментальных исследований или производственной деятельности;
· применение численных методов решения базовых математических задач и
классических задач естествознания в практической деятельности;
· сбор и обработка данных с использованием современных методов анализа
информации и вычислительной техники.
· Компетенции обучающегося, формируемые в результате освоения данной
образовательной программы.
· В результате освоения ОП выпускник должен обладать следующими
компетенциями:
· овладение умениями использовать полученные знания по основам теории
чисел при шифровании и дешифровании сообщений; оценивать достоверность
естественнонаучной информации;
· освоение знаний о фундаментальных теоремах по основам теории чисел,
лежащих в основе науки о криптографиях; наиболее важных открытиях в теории
чисел, оказавших определяющее влияние на развитие передачи секретных текстов;
методах научного познания шифрования информации;
· развитие познавательных интересов, интеллектуальных и творческих
способностей в процессе приобретения знаний и умений по основам теории чисел с
использованием различных источников информации и современных информационных
технологий;
· воспитание убежденности в возможности шифрования информации по теремам
из теории чисел; использования достижений теории чисел на благо развития
человеческой цивилизации; необходимости сотрудничества в процессе совместного
выполнения задач, готовности к морально-этической оценке использования научных
достижений, чувства ответственности за защиту информации;
· использование приобретенных знаний и умений для решения практических
задач повседневной жизни, обеспечения безопасности информации, рационального
использования возможностей науки теории чисел для криптографических целей.
·
1.4. Перечень планируемых результатов обучения
по дисциплине: Студент, изучивший дисциплину,
должен
· ЗНАТЬ
· основные теоретико-числовые понятия;
· основные результаты о делимости целых чисел и теории сравнений;
· основные алгоритмы решения стандартных задач.
· УМЕТЬ
· применять теорему о делении с остатком и свойства делимости к решению
различных арифметических задач;
· применять алгоритм Евклида для нахождения наибольшего общего делителя
целых чисел, его линейного разложения и наименьшего общего кратного;
· используя “решето” Эратосфена, составлять таблицы простых чисел и
решать задачи на применение основной теоремы арифметики и свойств простых
чисел.
· находить разложение заданного рационального числа в конечную цепную
дробь и разложение заданного иррационального числа в бесконечную цепную дробь,
вычислять подходящие дроби и применять свойства подходящих дробей при решении
задач;
· применять определение и свойства сравнений по заданному модулю при
составлении полной и приведённой систем вычетов;
· вычислять значения функции Эйлера и остатки арифметических выражений
от деления на заданное число, используя свойства сравнений и теоремы Эйлера
и Ферма.
· решать различными способами линейные сравнения первой степени с одним
неизвестным.
· применять для решения задач алгоритмы нахождения показателя и
первообразного корня по заданному модулю. Уметь решать двучленные сравнения,
используя таблицы индексов.
· применять обобщённый признак делимости Паскаля для конструирования
конкретных признаков делимости.
· проверять правильность выполнения простейших арифметических действий с
помощью сравнений.
· ВЛАДЕТЬ
· В результате освоения дисциплины обучающийся должен овладеть
общеучебными компетенциями по 4 блокам:
· самоорганизация - организовывать собственную
деятельность, выбирать типовые методы и способы выполнения профессиональных
задач, принимать решения в стандартных и нестандартных ситуациях;
· самообучение - осуществлять поиск и использование
информации, необходимой для эффективного выполнения профессиональных задач,
заниматься самообразованием;
· информационный блок - использовать
информационно-коммуникационные технологии в профессиональной деятельности;
· коммуникативный блок – быть способным
эффективно работать в коллективе и команде, брать на себя ответственность за
результат выполнения заданий.
1.4. Профильная составляющая (направленность) дисциплины.
· В программе по основам теории чисел профильную составляющую представляют
все разделы.
· Профильное изучение дисциплины осуществляется:
· путем отбора дидактических единиц программы по теории чисел, знание
которых будет необходимо при освоении ППСЗ ФГОС и в будущей профессиональной
деятельности;
· осуществлением межпредметных связей дисциплины с общетехническими и
специальными дисциплинами ППСЗ ФГОС;
· организацией внеаудиторной самостоятельной работы, направленной на
расширение и углубление знаний, которые будут необходимы при осуществлении
профессиональной деятельности.
1.5. Количество часов, отведенное на освоение программы
общеобразовательной дисциплины:
· максимальная учебная нагрузка – 119 часов,
· в том числе:
· обязательная аудиторная учебная нагрузка обучающегося – 79 часов;
· самостоятельная работа обучающегося – 40 часов.
·
2. СТРУКТУРА И ПРИМЕРНОЕ СОДЕРЖАНИЕ УЧЕБНОЙ дИСЦИПЛИНЫ
2.1. Объем учебной дисциплины и виды учебной
работы
Вид учебной работы
|
Объем часов
|
Максимальная
учебная нагрузка (всего)
|
119
|
Обязательная аудиторная учебная нагрузка (всего)
|
79
|
в том числе:
|
|
практические и лабораторные занятия
|
41
|
контрольная работа
|
4
|
Самостоятельная работа обучающегося (всего)
|
40
|
в том числе:
|
|
1. Решение задач по
темам
2.
Подготовка к практическим
и лабораторным работам. Отчеты.
3. Подготовка сообщений (презентаций).
|
|
Итоговая
аттестация в
форме экзамена.
|
16
|
|
«ОСНОВЫ ТЕОРИИ ЧИСЕЛ»
3.1. Требования к минимальному
материально-техническому обеспечению реализации общеобразовательной дисциплины
Реализация программы дисциплины требует наличия учебного кабинета.
Оборудование учебного кабинета:
·
посадочные
места по количеству обучающихся;
·
рабочее
место преподавателя;
·
рабочая
доска;
·
комплект
наглядных пособий по дисциплине (плакаты, таблицы, слайды, видеофильмы);
·
комплект
учебно-методической документации;
·
учебные
дидактические материалы.
Технические средства обучения:
·
компьютер;
·
colorDisplay;
·
видеоплеер;
·
видеопроектор;
·
музыкальный
центр;
·
акустическая
система;
·
компьютерный
класс:
·
микропроцессор
не ниже PentiumIV,
·
объём
ПЗУ не меньше 2-3 ГБ,
·
объем
ОЗУ не меньше 512 МБ
·
операционная
система WindowsXP / 7
·
текстовым
редактором Word – 2003
·
среды
программирования TurboPascal или Delphi.
слайд-проектор.
3.2.Учебно-методический комплекс учебной дисциплины,
систематизированный по компонентам
1.
Нормативные документы и
методическое обеспечение реализации дисциплины.
2. Сборники
задач по теории чисел.
3.
Комплекты типовых заданий,
тестов, вопросов по теории чисел.
3.3. Информационно-коммуникационное обеспечение
обучения
Перечень рекомендуемых учебных изданий,
Интернет-ресурсов, дополнительной литературы
Основные источники:
1.
Бухштаб А.А. Теория
чисел. – СПб: Издательство “Лань”, 2008.
2.
Валицкас А.И.
Конспект лекций по теории чисел: Теория делимости в кольце целых чисел. –
Тобольск: изд-во ТГПИ, 2002.
3.
Виноградов И.М.
Основы теории чисел. – СПб.: Издательство “Лань”, 2007.
4.
Куликов Л.Я.,
Москаленко А.И., Фомин А.А. Сборник задач по алгебре и теории чисел. – М.:
Просвещение, 2008.
5.
Нестеренко Ю.В.
Теория чисел. – М.: Издательский центр “Академия”, 2008.
6.
Шнеперман Л.Б.
Сборник задач по алгебре и теории чисел. – СПб: Издательство “Лань”, 2008.
Дополнительные
источники:
7.
Боревич З.И.,
Шафаревич И.Р. Теория чисел – М.: Наука, 1985.
8.
Валицкас А.И.,
Евсюкова Е.В., Шаипова А.Я., Шебанова Л.П. Разноуровневые задания по курсу: “Алгебра
и теория чисел”: Учебно-методическое пособие для студентов
физико-математических факультетов пединститутов. – Тобольск: изд-во ТГПИ, 1998.
9.
Варпаховский Ф.Л.,
Солодовников А.С., Стеллецкий И.В. Алгебра – М.: Просвещение, 1978.
10.
Воробьев Н.Н.
Признаки делимости – М.: Наука, 1980.
11.
Воробьев Н.Н. Числа
Фибоначчи – М.: Наука, 1978.
12.
Воронин С.М. Простые
числа – М.: Знание, 1978.
13.
Галочкин А.И., Нестеренко
Ю.В., Шидловский А.Б. Введение в теорию чисел. – М.: Изд. МГУ, 1984.
14.
Гекке Э. Лекции по
теории алгебраических чисел. – Москва-Ленинград, 1940.
15.
Грибанов В.У., Титов
П.И. Сборник упражнений по теории чисел. – М.: Просвещение, 1964.
16.
Казачек Н.А., Перлатов
Г.Н., Виленкин Н.Я., Бородин А.И. Алгебра и теория чисел. Части I, II, III. –
М.: Просвещение, 1974.
17.
Карацуба А.А. Основы
аналитической теории чисел. – М.: Наука, 1975.
18.
Кострикин А.И.
Введение в алгебру (в 3-х ТТ.). – М.: ФИЗМАТЛИТ, 2000.
19.
Кудреватов Г.А.
Сборник задач по теории чисел. – М.: Просвещение, 1970.
20.
Куликов Л.Я. Алгебра
и теория чисел. – М.: Высшая школа, 1979.
21.
Ляпин Е.С., Евсеев
А.Е. Алгебра и теория чисел. Части I, II – М.: Просвещение, 1978.
22.
Михелович Ш.Х. Теория
чисел. – М.: Просвещение, 1967.
23.
Постников М.М.
Введение в теорию алгебраических чисел. –М.: Наука, 1982.
24.
Постников М.М.
Введение в аналитическую теорию чисел. – М.: Наука, 1971.
25.
Прахар К.
Распределение простых чисел. – М.: Мир, 1967.
26.
Сирота Е.Р., Евсюкова
Е.В. Готовимся к государственному экзамену. Алгебра и теория чисел. – Тобольск:
Изд-во ТГПИ, 1995.
27.
Степанов С.А.
Сравнения. – М.: Знание, 1975.
28.
Хинчин А.Я. Цепные
дроби. – М.: Едиториал УРСС, 2004.
29.
Эльнатанов Б.А.
Развитие метода решета. – Душанбе, 1984.
Электронные образовательные ресурсы
1.
Теория чисел // Википедия:
свободная энциклопедия. – Электрон. дан. – Режим доступа: http://ru.wikipedia.org/wiki/Теория_чисел
4. Контроль и оценка результатов освоения учебной Дисциплины
Контроль
и оценка результатов освоения дисциплины
осуществляется преподавателем в процессе проведения практичесrb занятий, тематического
контроля, тестирования, а также выполнения обучающимися индивидуальных заданий,
презентаций.
Результаты
обучения
(освоенные
умения, усвоенные знания)
|
Формируемые
общеучебные и общие компетенции
|
Формы
и методы контроля и оценки результатов обучения
|
Обучающиеся должны
уметь:
У1: уверенно пользоваться
теоремами, определениями, свойствами при решении задач;
У2: сформировать умение составлять алгоритмы, приводящие к решению поставленных задач и
делать выводы;
У3: сформировать
умение решать задачи по теории чисел;
У4: применять
полученные знания для шифрования и дешифрования серетных сообщений,
передаваемых по открытым каналам связи;
У5: сформировать
собственную позицию по отношению к шифрованию и дешифрованию информации,
получаемой из разных источников;
знать:
З1: смысл понятий
по теории чисел: терема, определение, алгоритм,
лемма, свойства, программа, языки программирования;
З2: смысл величин
по теории чисел: НОД, НОК, факторизация, сравнение,
квадратичный вычет, квадратичный невычет, факториал, смвол Лежандра, функция
Эйлера, дискретный логарифм,шифрование, дешифрование, матричный процессор,
Схема RSA, криптологические протоколы;
З3: смысл основных
теорем и алгоритмов теории чисел: Малая теорема
Ферма, Теорема Эйлера, алгоритм Евклида, Китайсая теорема об остатках,
теорема Чебышева;
З4: роль теории чисел в программировании и криптографии.
|
Общеучебные компетенции
1.Самоорганизация
Организовывать собственную деятельность,
выбирать типовые методы и способы выполнения профессиональных задач,
принимать решения в стандартных и нестандартных ситуациях.
2.Самообучение
Осуществлять поиск и использование
информации, необходимой для эффективного выполнения профессиональных задач,
заниматься самообразованием.
3.Информационный блок
Использовать информационно-коммуникационные
технологии в профессиональной деятельности.
4.Коммуникативный блок
Способность эффективно работать в коллективе
и команде, брать на себя ответственность за результат выполнения заданий.
Общие компетенции, включающие в себя
способность:
ОК 1. Понимать
сущность и социальную значимость своей будущей профессии, проявлять к ней
устойчивый интерес.
ОК 2. Организовывать собственную
деятельность, выбирать типовые методы и способы выполнения профессиональных
задач, оценивать их эффективность и качество.
ОК 3. Принимать решения в стандартных и
нестандартных ситуациях и нести за них ответственность.
ОК 4. Осуществлять поиск и использование
информации, необходимой для эффективного выполнения профессиональных задач,
профессионального и личного развития.
ОК 5. Использовать
информационно-коммуникационные технологии в профессиональной деятельности.
ОК 6. Работать в коллективе и команде,
эффективно общаться с коллегами, руководством, потребителями.
ОК 7. Брать на себя ответственность за
работу членов команды (подчиненных), результат выполнения заданий.
ОК 8. Самостоятельно определять задачи
профессионального и личностного развития, заниматься самообразованием,
осознанно планировать повышение квалификации.
ОК 9. Ориентироваться в условиях частой
смены технологий в профессиональной деятельности.
|
Текущий
контроль:
Экспертная оценка результатов деятельности
студентов при выполнении и защите практических и лабораторных работ, тематического
контроля, тестировании, внеаудиторной самостоятельной работы, устной проверке
знаний на учебных занятиях, защите презентаций
и др. видов текущего контроля.
Промежуточный
контроль:
Контрольная
работа
Итоговый
контроль:
экзамен
|
ПРИЛОЖЕНИЕ 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.
2.
Найти все x
= 5a×7b×11g со свойством j (x)
= 2310000.
Решение. Если a¹ 0, b¹ 0, g¹ 0,
то j (5a×7b×11g) = j(5a)×j(7b)×j(11g) = = 5a–1×4×7b–1×6×11g–1×10 = 24×3×5a×7b–1×11g–1.
С другой стороны, 2310000 = 24×3×54×7×11. Из равенства 24×3×5a×7b–1×11g–1 = = 24×3×54×7×11 находим (используя единственность
канонического разложения), что a =
4, b = 2, g = 2,
т.е. x = 54×72×112.
Исследуем теперь случаи, когда некоторые из
показателей a, b, gнулевые.
Из предыдущих вычислений видно, что 3, 7,11 участвуют в каноническом
разложении числа 2310000 = 24×3×54×7×11, так что b¹ 0,
g¹ 0. Если a = 0, то j(x)
= = j (7b×11g) = j(7b)×j(11g) = 7b–1×6×11g–1×10 = 22×3×5×7b–1×11g–1и равенство j(x)
= = 2310000 = 24×3×54×7×11невозможно.
Таким образом, найденное выше решение единственно.
Ответ: x = 54×72×112.
2.
Найти
количество натуральных чисел x со свойствами:
x<
450 и НОД(x, 450) = 15.
Решение. Любое число xс указанными в условии свойствами имеет вид x
= = 15×y,
где 1£y<
30 (т.к. 15 £x<
450). При этом условие НОД(x,
450) = 15означает, что НОД(y,
) = 1, т.е. НОД(y, 30) = 1. Таким образом, задача сводится к отысканию
всех чисел yсо свойствами 1£y<
30и НОД(y,
30) = 1. Таких чисел j(30) = j(2×3×5) = j(2)×j(3)×j(5) = 1×2×4 = 8.
Ответ: 8 чисел.
3.
Решить
сравнение: а) тремя способами 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 6 (mod 7), 5×1
= 5 6 (mod 7), 5×2 = 10 º 3 6 (mod 7), 5×3 = 15 º 1 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º(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.
Поскольку 5j(7)º 1 (mod 7), то умножая обе части сравнения 5×xº 6 (mod
7)на 5j(7)–1, получим xº5j(7)–1×5×xº5j(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),
которое и будем решать.
Разлагаем дробь в
конечную цепную дробь:
Таким образом, = [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
|
Таким образом, 101×47 – 113×42
= 1 и значит, 101×47 º 1 (mod 113), так что решением рассматриваемого сравнения 101×х º 17 (mod113) будет xº 47×17 = = 799 º 8 (mod 113).
Ответ: x
º8 (mod 113).
4.
Решить
сравнение с помощью индексов: 40×х
10º 3 (mod 17).
Решение. Упростим сравнение: 6×х 10º 3 (mod 17)и поскольку НОД(3, 17) = 1, последнее
сравнение равносильно (после сокращения на 3) сравнению 2×х 10º 1 (mod 17), которое и будем решать.
Переходя к индексам по модулю j(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).
5.
Найти остаток
от деления (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.
6.
Найти длину
периода и длину предпериода при обращении обыкновенной дроби в десятичную.
Решение.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 1 (mod 21), 10 2 = 100 º–5 1 (mod 21), 10 3º 10×(–5) º
–8 1 (mod 21), 10 4º (–5) 2º4 1 (mod 21), 10 5ºº 10×4 º–2 1 (mod 21), 10 6º 10×(–2) º1
(mod 21).
Таким образом, (длина периода) = 6.
Ответ: длина предпериода равна 3, а длина
периода – 6.
Вариант 0
1.
Найти НОД
трёх чисел: 2226, 3213, 6489.
2.
Решить уравнение: j (7 х) = 294.
3.
Решить сравнение: а)
тремя способами 7×х º 6 (mod 9),
б) методом цепных дробей 88×х º 324 (mod404).
4.
Решить сравнение с
помощью индексов: 25×х 7º –7 (mod 31).
5.
Найти остаток от
деления 11 802 на 1000.
6.
Найти длину периода и
длину предпериода при обращении обыкновенной дроби в десятичную.
Вариант 1
1.
Найти НОД
трёх чисел: 3445, 4225, 5915.
2.
Найти все x
= 5a×7b×11со
свойством j (x) = 42000.
3.
Решить сравнение: а)
тремя способами 3×х º 1 (mod 11),
б) методом цепных дробей 365×х º 50 (mod 395).
4.
Решить сравнение с
помощью индексов: 8×х9º –17 (mod 41).
5.
Найти остаток от
деления 19 2402 на 100.
6.
Найти длину периода и
длину предпериода при обращении обыкновенной дроби в десятичную.
Вариант 2
3.
Найти НОД
трёх чисел: 1073, 3683, 34481.
4.
Найти количество
натуральных чисел xсо свойствами:
x<
975 и НОД(x,
975) = 13.
5.
Решить сравнение: а)
тремя способами 18×х º 12 (mod 30),
б) методом цепных дробей 91×х º 143 (mod 222).
6.
Решить сравнение с
помощью индексов: 7×х13
+ 23 º 0 (mod 47).
7.
Найти остаток от
деления 1967 1968 на 11.
8.
Найти длину периода и
длину предпериода при обращении обыкновенной дроби в десятичную.
Вариант 3
1.
Найти НОД
трёх чисел: 1012, 1474, 4598.
2.
Решить уравнение: j (11 х) = 13310.
3.
Решить сравнение: а)
тремя способами 39×х º 5 (mod 11),
б) методом цепных дробей 27×х º 25 (mod 119).
4.
Решить сравнение с
помощью индексов: 9×х11
+ 1 º 0 (mod 43).
5.
Найти остаток от
деления 109 345 на 14.
6.
Найти длину периода и
длину предпериода при обращении обыкновенной дроби в десятичную.
Вариант 4
1.
Найти НОД
трёх чисел: 988, 2014, 42598.
2.
Найти все x
= 5a×7×11g со свойством j (x) = 330000.
3.
Решить сравнение: а)
тремя способами 37×х º 16 (mod 11),
б) методом цепных дробей 82×х º 14 (mod 202).
4.
Решить сравнение с
помощью индексов: 19×х5
+ 13 º 0 (mod 53).
5.
Найти остаток от
деления 293 275 на 48.
6.
Найти длину периода и
длину предпериода при обращении обыкновенной дроби в десятичную.
Вариант 5
1.
Найти НОД
трёх чисел: 7975, 2585, 13915.
2.
Найти количество
натуральных чисел, не превосходящих 120 и не взаимно простых с
числом 30.
3.
Решить сравнение: а)
тремя способами 62×х º 5 (mod 13),
б) методом цепных дробей 243×х º 271 (mod 317).
4.
Решить с помощью
индексов: 32 хº 15
(mod 37).
6. Найти остаток от деления: 117 53 на 11.
7.
Найти длину периода и
длину предпериода при обращении обыкновенной дроби в десятичную.
Вариант 6
1.
Найти НОД
трёх чисел: 874, 1518, 20142.
2.
Решить уравнение j(15x) = 9000.
3.
Решить сравнение: а)
тремя способами 11×х º 15 (mod 24),
б) методом цепных дробей 92×х º 20 (mod 284).
4.
Решить сравнение с
помощью индексов: х2º 54 (mod 67).
5.
Найти остаток от
деления 5 80 + 7 100 на 13.
6.
Найти длину периода и
длину предпериода при обращении обыкновенной дроби в десятичную.
Вариант 7
1.
Найти НОД
трёх чисел: 9911, 952, 2227.
2.
Найти все x
= 5a×7bсо
свойством j(x) = 147000.
3.
Решить сравнение: а)
тремя способами 6×х º 8 (mod 10),
б) методом цепных дробей 221×х º 111 (mod 360).
4.
Решить сравнение с
помощью индексов: х2º 37 (mod 41).
5.
Найти остаток от
деления 2 100 + 3 100 на 5.
6.
Найти длину периода и
длину предпериода при обращении обыкновенной дроби в десятичную.
Вариант 8
1.
Найти НОД
трёх чисел: 1253, 406, 252.
2.
Найти количество
натуральных чисел xсо свойствами:
x<
2476и НОД(x,
2476) = 619.
3.
Решить сравнение: а)
тремя способами 8×х º 14 (mod 18),
б) методом цепных дробей 113×х º 89 (mod 311).
4.
Найти сравнение с
помощью индексов: х2º 58 (mod 61).
5.
Найти остаток от
деления 11 1841 на 7.
6.
Найти длину периода и
длину предпериода при обращении обыкновенной дроби в десятичную.
Вариант 9
1.
Найти НОД
трёх чисел: 2743, 3587, 6963.
2.
Найти количество
натуральных чисел не превосходящих 2272 и взаимно простых с числом 568
.
3.
Решить сравнение: а)
тремя способами 10×х º 4 (mod 14),
б) методом цепных дробей 95×х º 59 (mod 308).
4.
Решить сравнение с
помощью индексов: х15º 38 (mod 59).
5.
Найти остаток от
деления 23 2342 на 14.
6.
Найти длину периода и
длину предпериода при обращении обыкновенной дроби в десятичную.
ПРИЛОЖЕНИЕ 1
Контрольная работа по ТЕОРИИ
ЧИСЕЛ
вариант-ОБРАЗЕЦ
3.
Найти НОД
трёх чисел: 19074, 13566, 8211.
Решение. Используем свойство (19074, 13566, 8211) =
((19074, 13566), 8211).
Сначала находим НОД(19074, 13566) = 102, а затем НОД(102,
8211) = 51.
Таким образом, НОД(19074, 13566, 8211)
= 51.
Ответ: НОД(19074, 13566, 8211)
= 51.
4.
Найти все x
= 5a×7b×11g со свойством j (x)
= 2310000.
Решение. Если a¹ 0, b¹ 0, g¹ 0,
то j (5a×7b×11g) = j(5a)×j(7b)×j(11g) = = 5a–1×4×7b–1×6×11g–1×10 = 24×3×5a×7b–1×11g–1.
С другой стороны, 2310000 = 24×3×54×7×11. Из равенства 24×3×5a×7b–1×11g–1 = = 24×3×54×7×11 находим (используя единственность
канонического разложения), что a =
4, b = 2, g = 2,
т.е. x = 54×72×112.
Исследуем теперь случаи, когда некоторые из
показателей a, b, gнулевые.
Из предыдущих вычислений видно, что 3, 7,11 участвуют в каноническом
разложении числа 2310000 = 24×3×54×7×11, так что b¹ 0,
g¹ 0. Если a = 0, то j(x)
= = j (7b×11g) = j(7b)×j(11g) = 7b–1×6×11g–1×10 = 22×3×5×7b–1×11g–1и равенство j(x)
= = 2310000 = 24×3×54×7×11невозможно.
Таким образом, найденное выше решение единственно.
Ответ: x = 54×72×112.
9.
Найти
количество натуральных чисел x со свойствами:
x<
450 и НОД(x, 450) = 15.
Решение. Любое число xс указанными в условии свойствами имеет вид x
= = 15×y,
где 1£y<
30 (т.к. 15 £x<
450). При этом условие НОД(x,
450) = 15означает, что НОД(y,
) = 1, т.е. НОД(y, 30) = 1. Таким образом, задача сводится к отысканию
всех чисел yсо свойствами 1£y<
30и НОД(y,
30) = 1. Таких чисел j(30) = j(2×3×5) = j(2)×j(3)×j(5) = 1×2×4 = 8.
Ответ: 8 чисел.
7.
Решить
сравнение: а) тремя способами 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 6 (mod 7), 5×1
= 5 6 (mod 7), 5×2 = 10 º 3 6 (mod 7), 5×3 = 15 º 1 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º(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.
Поскольку 5j(7)º 1 (mod 7), то умножая обе части сравнения 5×xº 6 (mod
7)на 5j(7)–1, получим xº5j(7)–1×5×xº5j(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),
которое и будем решать.
Разлагаем дробь в
конечную цепную дробь:
Таким образом, = [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
|
Таким образом, 101×47 – 113×42
= 1 и значит, 101×47 º 1 (mod 113), так что решением рассматриваемого сравнения 101×х º 17 (mod113) будет xº 47×17 = = 799 º 8 (mod 113).
Ответ: x
º8 (mod 113).
8.
Решить
сравнение с помощью индексов: 40×х
10º 3 (mod 17).
Решение. Упростим сравнение: 6×х 10º 3 (mod 17)и поскольку НОД(3, 17) = 1, последнее
сравнение равносильно (после сокращения на 3) сравнению 2×х 10º 1 (mod 17), которое и будем решать.
Переходя к индексам по модулю j(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).
9.
Найти остаток
от деления (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.
10.
Найти длину
периода и длину предпериода при обращении обыкновенной дроби в десятичную.
Решение.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 1 (mod 21), 10 2 = 100 º–5 1 (mod 21), 10 3º 10×(–5) º
–8 1 (mod 21), 10 4º (–5) 2º4 1 (mod 21), 10 5ºº 10×4 º–2 1 (mod 21), 10 6º 10×(–2) º1
(mod 21).
Таким образом, (длина периода) = 6.
Ответ: длина предпериода равна 3, а длина
периода – 6.
Вариант 0
7.
Найти НОД
трёх чисел: 2226, 3213, 6489.
8.
Решить уравнение: j (7 х) = 294.
9.
Решить сравнение: а)
тремя способами 7×х º 6 (mod 9),
б) методом цепных дробей 88×х º 324 (mod404).
10.Решить сравнение с помощью индексов: 25×х 7º –7 (mod 31).
11.Найти остаток от деления 11 802 на 1000.
12.Найти длину периода и длину предпериода при обращении обыкновенной
дроби в десятичную.
Вариант 1
7.
Найти НОД
трёх чисел: 3445, 4225, 5915.
8.
Найти все x
= 5a×7b×11со
свойством j (x) = 42000.
9.
Решить сравнение: а)
тремя способами 3×х º 1 (mod 11),
б) методом цепных дробей 365×х º 50 (mod 395).
10.Решить сравнение с помощью индексов: 8×х9º –17 (mod 41).
11.Найти остаток от деления 19 2402 на 100.
12.Найти длину периода и длину предпериода при обращении обыкновенной
дроби в десятичную.
Вариант 2
10.
Найти НОД
трёх чисел: 1073, 3683, 34481.
11.
Найти количество
натуральных чисел xсо свойствами:
x<
975 и НОД(x,
975) = 13.
12.
Решить сравнение: а)
тремя способами 18×х º 12 (mod 30),
б) методом цепных дробей 91×х º 143 (mod 222).
13.
Решить сравнение с
помощью индексов: 7×х13
+ 23 º 0 (mod 47).
14.
Найти остаток от
деления 1967 1968 на 11.
15.
Найти длину периода и
длину предпериода при обращении обыкновенной дроби в десятичную.
Вариант 3
8.
Найти НОД
трёх чисел: 1012, 1474, 4598.
9.
Решить уравнение: j (11 х) = 13310.
10.Решить сравнение: а) тремя способами 39×х º 5 (mod 11),
б) методом цепных дробей 27×х º 25 (mod 119).
11.Решить сравнение с помощью индексов: 9×х11 + 1 º 0 (mod 43).
12.Найти остаток от деления 109 345 на 14.
13.Найти длину периода и длину предпериода при обращении обыкновенной
дроби в десятичную.
Вариант 4
7.
Найти НОД
трёх чисел: 988, 2014, 42598.
8.
Найти все x
= 5a×7×11g со свойством j (x) = 330000.
9.
Решить сравнение: а)
тремя способами 37×х º 16 (mod 11),
б) методом цепных дробей 82×х º 14 (mod 202).
10.Решить сравнение с помощью индексов: 19×х5 + 13 º 0 (mod 53).
11.Найти остаток от деления 293 275 на 48.
12.Найти длину периода и длину предпериода при обращении обыкновенной
дроби в десятичную.
Вариант 5
5.
Найти НОД
трёх чисел: 7975, 2585, 13915.
6.
Найти количество
натуральных чисел, не превосходящих 120 и не взаимно простых с
числом 30.
7.
Решить сравнение: а)
тремя способами 62×х º 5 (mod 13),
б) методом цепных дробей 243×х º 271 (mod 317).
8.
Решить с помощью
индексов: 32 хº 15
(mod 37).
6. Найти остаток от деления: 117 53 на 11.
14.Найти длину периода и длину предпериода при обращении обыкновенной
дроби в десятичную.
Вариант 6
7.
Найти НОД
трёх чисел: 874, 1518, 20142.
8.
Решить уравнение j(15x) = 9000.
9.
Решить сравнение: а)
тремя способами 11×х º 15 (mod 24),
б) методом цепных дробей 92×х º 20 (mod 284).
10.Решить сравнение с помощью индексов: х2º 54 (mod 67).
11.Найти остаток от деления 5 80 + 7 100
на 13.
12.Найти длину периода и длину предпериода при обращении обыкновенной
дроби в десятичную.
Вариант 7
7.
Найти НОД
трёх чисел: 9911, 952, 2227.
8.
Найти все x
= 5a×7bсо
свойством j(x) = 147000.
9.
Решить сравнение: а)
тремя способами 6×х º 8 (mod 10),
б) методом цепных дробей 221×х º 111 (mod 360).
10.Решить сравнение с помощью индексов: х2º 37 (mod 41).
11.Найти остаток от деления 2 100 + 3 100
на 5.
12.Найти длину периода и длину предпериода при обращении обыкновенной
дроби в десятичную.
Вариант 8
7.
Найти НОД
трёх чисел: 1253, 406, 252.
8.
Найти количество
натуральных чисел xсо свойствами:
x<
2476и НОД(x,
2476) = 619.
9.
Решить сравнение: а)
тремя способами 8×х º 14 (mod 18),
б) методом цепных дробей 113×х º 89 (mod 311).
10.Найти сравнение с помощью индексов: х2º 58 (mod 61).
11.Найти остаток от деления 11 1841 на 7.
12.Найти длину периода и длину предпериода при обращении обыкновенной
дроби в десятичную.
Вариант 9
7.
Найти НОД
трёх чисел: 2743, 3587, 6963.
8.
Найти количество
натуральных чисел не превосходящих 2272 и взаимно простых с числом 568
.
9.
Решить сравнение: а)
тремя способами 10×х º 4 (mod 14),
б) методом цепных дробей 95×х º 59 (mod 308).
10.Решить сравнение с помощью индексов: х15º 38 (mod 59).
11.Найти остаток от деления 23 2342 на 14.
12.Найти длину периода и длину предпериода при обращении обыкновенной
дроби в десятичную.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.