В различных разделах математики, а также в применении математики в технике, часто встречается ситуация, когда алгебраические операции производятся не над числами, а над объектами иной природы. Например сложение матриц, умножение матриц, сложение векторов, операции над многочленами, операции над линейными преобразованиями и т.д.
Определение 1. Кольцом называется множество математических объектов, в котором определены два действия − "сложение" и "умножение", которые сопоставляют упорядоченным парам элементов их "сумму" и "произведение", являющиеся элементами того же множества. Данные действия удовлетворяют следующим требованиям:
1. a+b=b+a (коммутативность сложения).
2. (a+b)+c=a+(b+c) (ассоциативность сложения).
3. Существует нулевой элемент 0 такой, что a +0=a , при любом a .
4. Для любого a существует противоположный элемент −a такой, что a +(−a )=0.
5. (a+b)c=ac+bc (левая дистрибутивность).
5". c(a+b)=ca+cb (правая дистрибутивность).
Требования 2, 3, 4 означают, что множество математических объектов образует группу , а вместе с пунктом 1 мы имеем дело с коммутативной (абелевой) группой относительно сложения.
Как видно из определения, в общем определении кольца на умножения не накладывается никаких ограничений, кроме дистрибутивности со сложением. Однако при различных ситуациях возникает необходимость рассматривать кольца с дополнительными требованиями.
6. (ab)c=a(bc) (ассоциативность умножения).
7. ab=ba (коммутативность умножения).
8. Существование единичного элемента 1, т.е. такого a ·1=1·a=a , для любого элемента a .
9. Для любого элемента элемента a существует обратный элемент a −1 такой, что aa −1 =a −1 a= 1.
В различных кольцах 6, 7, 8, 9 могут выполняться как отдельно так и в различных комбинациях.
Кольцо называется ассоциативным, если выполняется условие 6, коммутативным, если выполнено условие 7, коммутативным и ассоциативным если выполнены условия 6 и 7. Кольцо называется кольцом с единицей, если выполнено условие 8.
Примеры колец:
1. Множество квадратных матриц.
Действительно. Выполнение пунктов 1-5, 5" очевидна. Нулевым элементом является нулевая матрица. Кроме этого выполняется пункт 6 (ассоциативность умножения), пункт 8 (единичным элементом является единичная матрица). Пункты 7 и 9 не выполняются т.к. в общем случае умножение квадратных матриц некоммутативна, а также не всегда существует обратное к квадратной матрице.
2. Множество всех комплексных чисел.
3. Множество всех действительных чисел.
4. Множество всех рациональных чисел.
5. Множество всех целых чисел.
Определение 2. Всякая система чисел, содержащая сумму, разность и произведение любых двух своих чисел, называется числовым кольцом .
Примеры 2-5 являются числовыми кольцами. Числовыми кольцами являются также все четные числа, а также все целые числа делящихся без остатка на некоторое натуральное число n. Отметим, что множество нечетных чисел не является кольцом т.к. сумма двух нечетных чисел является четным числом.
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
Вятский государственный гуманитарный университет
Математический факультет
Кафедра математического анализа и методики
преподавания математики
Выпускная квалификационная работа
на тему: Кольцо целых чисел Гаусса.
Выполнил:
студент V курса
математического факультета
Гнусов В.В.
___________________________
Научный руководитель:
старший преподаватель кафедры
алгебры и геометрии
Семенов А.Н..
___________________________
Рецензент:
кандидат физ.-мат. наук, доцент
кафедры алгебры и геометрии
Ковязина Е.М.
___________________________
Допущена к защите в ГАК
Зав. кафедрой________________ Вечтомов Е.М.
« »________________
Декан факультета___________________ Варанкина В.И.
« »________________
Киров 2005
- Введение. 2
- 3
- 4
- 1.2 ДЕЛЕНИЕ С ОСТАТКОМ. 5
- 1.3 НОД. АЛГОРИТМ ЕВКЛИДА. 6
- 9
- 12
- 17
- Заключение. 23
Введение.
Кольцо целых комплексных чисел было открыто Карлом Гауссом и названо в его честь гауссовым.
К. Гаусс пришел к мысли о возможности и необходимости расширения понятия целого числа в связи с поиском алгоритмов решения сравнений второй степени. Он перенес понятие целого числа на числа вида, где -- произвольные целые числа, а -- является корнем уравнения На данном множестве К. Гаусс впервые построил теорию делимости, аналогичную теории делимости целых чисел. Он обосновал справедливость основных свойств делимости; показал, что в кольце комплексных чисел существует только четыре обратимых элемента: ; доказал справедливость теоремы о делении с остатком, теоремы о единственности разложения на простые множители; показал какие простые натуральные числа останутся простыми и в кольце; выяснил природу простых целых комплексных чисел.
Развитая К. Гауссом теория, описанная в его труде «Арифметические исследования», явилась фундаментальным открытием для теории чисел и алгебры.
В выпускной работе были поставлены следующие цели:
1. Развить теорию делимости в кольце чисел Гаусса.
2. Выяснить природу простых гауссовых чисел.
3. Показать применение гауссовых чисел при решении обычных диофантовых задач.
ГЛАВА 1. ДЕЛИМОСТЬ В КОЛЬЦЕ ЧИСЕЛ ГАУССА.
Рассмотрим множество комплексных чисел. По аналогии с множеством действительных чисел в нем можно выделить некоторое подмножество целых чисел. Множество чисел вида, где назовем целыми комплексными числами или гауссовыми числами. Нетрудно проверить, что для этого множества выполняются аксиомы кольца. Таким образом, это множество комплексных чисел является кольцом и называется кольцом целых чисел Гаусса . Обозначим его как, так как оно является расширением кольца элементом: .
Поскольку кольцо гауссовых чисел является подмножеством комплексных чисел, то для него справедливы некоторые определения и свойства комплексных чисел. Так, например, каждому гауссовому числу соответствует вектор с началом в точке и с концом в. Следовательно, модуль гауссова числа есть. Заметим, что в рассматриваемом множестве, подмодульное выражение всегда есть число неотрицательное целое. Поэтому в некоторых случаях удобнее пользоваться нормой , то есть квадратом модуля. Таким образом. Можно выделить следующие свойства нормы. Для любых гауссовых чисел справедливо:
(1)
(2)
(3)
(4)
(5)
Справедливость данных свойств тривиальным образом проверяется с помощью модуля. Попутно заметим, что (2), (3), (5) справедливы и для любых комплексных чисел.
Кольцо гауссовых чисел -- это коммутативное кольцо без делителей 0, так как оно является подкольцом поля комплексных чисел. Отсюда следует мультипликативная сократимость кольца, то есть
1.1 ОБРАТИМЫЕ И СОЮЗНЫЕ ЭЛЕМЕНТЫ.
Посмотрим, какие гауссовы числа будут обратимыми. Нейтральным по умножению является. Если гауссово число обратимо , то, по определению, существует такое, что. Переходя к нормам, согласно свойству 3, получим. Но эти нормы натуральны, следовательно. Значит, по свойству 4, . Обратно, все элементы данного множества обратимы, поскольку. Следовательно, обратимыми будут числа с нормой равной единице, то есть, .
Как видно не все гауссовы числа будут обратимы. Поэтому интересно рассмотреть вопрос делимости. Как обычно, мы говорим, что делится на, если существует такое, что.Для любых гауссовых чисел, а также обратимых справедливы свойства.
(7)
(8)
(9)
(10)
, где (11)
(12)
Легко проверяются (8), (9), (11), (12). Справедливость (7) следует из (2), а (10) следует из (6). В силу свойства (9), элементы множества ведут себя по отношению к делимости точно так же как и, и называются союзными с. Поэтому естественно рассматривать делимость гауссовых чисел с точностью до союзности. Геометрически на комплексной плоскости союзные числа будут отличаться друг от друга поворотом на угол кратный.
1.2 ДЕЛЕНИЕ С ОСТАТКОМ.
Пусть надо поделить на, но невозможно произвести деление нацело. Мы должны получить, и при этом должно быть «мало». Тогда покажем, чту брать в качестве неполного частного при делении с остатком во множестве гауссовых чисел.
Лемма 1. О делении с остатком.
В кольце возможно деление с остатком, при котором остаток меньше делителя по норме. Точнее, для любых и найдется такое, что . В качестве можно взять ближайшее к комплексному числу гауссово число.
Доказательство.
Разделим на во множестве комплексных чисел. Это возможно, так как множество комплексных чисел является полем. Пусть. Округлим действительные числа и до целых, получим соответственно и. Положим. Тогда
.
Умножая сейчас обе части неравенства на получим, в силу мультипликативности нормы комплексных чисел, что. Таким образом, в качестве неполного частного можно взять гауссово число, которое как нетрудно видеть, является ближайшим к.
Ч.Т.Д.
1.3 НОД. АЛГОРИТМ ЕВКЛИДА.
Мы пользуемся обычным для колец определением наибольшего общего делителя. НОД"ом двух гауссовых чисел называется такой их общий делитель, который делится на любой другой их общий делитель.
Как и во множестве целых чисел, во множестве гауссовых чисел для нахождения НОД пользуются алгоритмом Евклида.
Пусть и данные гауссовы числа, причем. Разделим с остатком на. Если остаток будет отличен от 0, то разделим на этот остаток, и будем продолжать последовательное деление остатков до тех пор, пока оно будет возможно. Получим цепочку равенств:
, где
, где
, где
……………………….
, где
Эта цепочка не может продолжаться бесконечно, так как имеем убывающую последовательность норм, а нормы -- неотрицательные целые числа.
Теорема 2. О существовании НОД.
В алгоритме Евклида, примененному к числам Гаусса и последний ненулевой остаток есть НОД( ).
Доказательство.
Докажем, что в алгоритме Евклида действительно получаем НОД.
1.Рассмотрим равенства снизу вверх.
Из последнего равенства видно, что.Следовательно, как сумма чисел делящихся на. Так как и, то следующая строчка даст. И так далее. Таким образом, видно, что и. То есть это общий делитель чисел и.
Покажем, что это наибольший общий делитель, то есть делится на любой другой их общий делитель.
2. Рассмотрим равенства сверху вниз.
Пусть -- произвольный общий делитель чисел и. Тогда, как разность чисел делящихся на, действительно из первого равенства. Из второго равенства получим, что. Таким образом, представляя в каждом равенстве остаток как разность чисел делящихся на, мы из предпоследнего равенства получим, что делится на.
Ч.Т.Д.
Лемма 3. О представлении НОД.
Если НОД( , )= , то существуют такие целые гауссовы числа и , что .
Доказательство.
Рассмотрим снизу вверх цепочку равенств, полученную в алгоритме Евклида. Последовательно подставляя вместо остатков их выражения через предыдущие остатки, мы выразим через и.
Гауссово число называется простым , если его нельзя представить в виде произведения двух необратимых сомножителей. Следующее утверждение очевидно.
Утверждение 4.
При умножении простого гауссова числа на обратимое снова получается простое гауссово число.
Утверждение 5.
Если у гауссова числа взять необратимый делитель с наименьшей нормой, то он будет простым гауссовым.
Доказательство.
Пусть такой делитель является составным числом. Тогда, где и необратимые гауссовы числа. Перейдем к нормам, и согласно (3) получим, что. Так как эти нормы натуральны, то имеем, что, а в силу (12), является необратимым делителем данного числа Гаусса, что противоречит выбору.
Утверждение 6.
Если не делится на простое гауссово число , то НОД( , )=1.
Доказательство.
Действительно, простое число делится только на числа союзные с 1 или с . А так как не делится на , то на союзные с тоже не делится. Значит, их общими делителями будут только обратимые числа.
Лемма 7. Лемма Евклида.
Если произведение гауссовых чисел делится на простое гауссово число , то хотя бы один из множителей делится на .
Доказательство.
Для доказательства достаточно рассмотреть случай, когда произведение содержит только два множителя. То есть покажем, что если делится на , то либо делится на , либо делится на .
Пусть не делится на , тогда НОД(, )=1. Следовательно, существуют такие гауссовы числа и, что. Умножим обе части равенства на , получим, что, отсюда следует, что, как сумма чисел делящихся на .
1.4 ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ.
Любое ненулевое гауссово число можно представить в виде произведения простых гауссовых чисел, причем это представление единственно с точностью до союзности и порядка сомножителей.
Замечание 1.
Обратимое число имеет в своем разложении нуль простых множителей, то есть представляется самим собой.
Замечание 2.
Более точно единственность формулируется следующим образом. Если имеются два разложения на простые гауссовы множители, то есть , то и можно так перенумеровать числа , что будет союзно с , при всех от 1 до включительно.
Доказательство.
Доказательство проведем индукцией по норме.
База. Для числа с единичной нормой утверждение очевидно.
Пусть сейчас -- ненулевое необратимое гауссово число, и для всех чисел Гаусса с нормой меньшей утверждение доказано.
Покажем возможность разложения на простые множители. Для этого обозначим через необратимый делитель, имеющий наименьшую норму. Этот делитель должен быть простым числом по утверждению 5. Тогда. Таким образом, мы имеем и по индуктивному предположению представимо в виде произведения простых чисел. Значит, раскладывается в произведение этих простых и.
Покажем единственность разложения на простые множители. Для этого возьмем два произвольных таких разложения:
По лемме Евклида в произведении один из множителей должен делиться на. Можно считать, что делится на, иначе перенумеруем. Так как они простые, то, где обратимо. Сокращая обе части нашего равенства на, получим разложение на простые множители числа, по норме меньшего, чем.
По индуктивному предположению и можно перенумеровать числа так, что будет союзно с, с, …, с. Тогда и при этой нумерации союзно с при всех от 1 до включительно. Значит, разложение на простые множители единственно.
Пример однопорожденного кольца над без ОТА.
Рассмотрим. Элементами этого кольца являются числа вида, где и произвольные целые числа. Покажем, что в нем не выполняется основная теорема арифметики. Определим в этом кольце норму числа следующим образом: . Это действительно является нормой, так как нетрудно проверить, что. Пусть и. Тогда
Заметим, что.
Покажем, что в рассматриваемом кольце числа являются простыми. Действительно, пусть -- одно из них и. Тогда имеем: Так как в этом кольце нет чисел с нормой 2, то или. Обратимыми элементами будут числа с единичной нормой и только они. Значит, в произвольном разложении на множители найдется обратимый множитель, следовательно, просто.
ГЛАВА 2. ПРОСТЫЕ ЧИСЛА ГАУССА.
Чтобы понять какие гауссовы числа являются простыми, рассмотрим ряд утверждений.
Теорема 8.
Каждое простое гауссово является делителем ровно одного простого натурального.
Доказательство.
Пусть -- простое гауссово, тогда. По основной теореме арифметики натуральных чисел раскладывается в произведение простых натуральных. А по лемме Евклида хотя бы один из них делится на.
Покажем сейчас, что простое Гауссово не может делить два различных простых натуральных. Действительно, пусть и различные простые натуральные, делящиеся на. Поскольку НОД()=1, то по теореме о представлении НОД в целых числах существуют и -- целые числа такие, что. Отсюда, что противоречит простоте.
Таким образом, раскладывая каждое простое натуральное на простые гауссовы, мы переберем все простые гауссовы, причем без повторений.
Следующая теорема показывает, что каждого простого натурального «получается» не более двух простых гауссовых.
Теорема 9.
Если простое натуральное разложено в произведение трех простых гауссовых, то хотя бы один из множителей обратим.
Доказательство.
Пусть -- простое натуральное такое, что . Перейдя к нормам, получим:
.
Из этого равенства в натуральных числах следует, что хотя бы одна из норм равна 1. Следовательно, хотя бы одно из чисел -- обратимо.
Лемма 10.
Если гауссово число делится на простое натуральное, то и.
Доказательство.
Пусть , то есть . Тогда , , то есть , .
Ч.Т.Д.
Лемма 11.
Для простого натурального числа вида, существует натуральное такое, что.
Доказательство.
Теорема Вильсона гласит, что целое число является простым тогда и только тогда, когда. Но, отсюда. Раскроем и преобразуем факториал:
Отсюда получаем, что, т.е. .
Таким образом, мы получили, что , где = .
Сейчас мы готовы описать все простые гауссовы числа.
Теорема 12.
Все простые гауссовы можно разбить на три группы:
1). Простые натуральные вида, являются простыми гауссовыми;
2). Двойка союзна с квадратом простого гауссова числа;
3). Простые натуральные вида, раскладываются в произведение двух простых сопряженных гауссовых.
Доказательство.
1). Предположим, что простое натуральное вида не является простым гауссовым. Тогда , причем и . Перейдем к нормам: . Учитывая указанные неравенства, получим , то есть -- сумма квадратов двух целых чисел. Но сумма квадратов целых чисел не может давать остаток 3 при делении на 4.
2). Заметим, что
.
Число -- простое гауссово, так как иначе двойка разложилась бы на три необратимых множителя, что противоречит теореме 9.
3). Пусть простое натуральное вида , тогда по лемме 11 существует целое число такое, что . Пусть -- простое гауссово. Так как , то по лемме Евклида на делится хотя бы один из множителей. Пусть , тогда существует гауссово число такое, что . Приравнивая коэффициенты мнимых частей получим, что . Следовательно, , что противоречит нашему предположению о простоте . Значит -- составное гауссово, представимое в виде произведения двух простых сопряженных гауссовых.
Ч.Т.Д.
Утверждение.
Гауссово число, сопряженное к простому, само является простым.
Доказательство.
Пусть простое число гаусса. Если предположить, что составное, то есть. Тогда рассмотрим сопряженное:, то есть представили в виде произведения двух необратимых сомножителей, чего не может быть.
Утверждение.
Гауссово число, норма которого есть простое натуральное число, является простым гауссовым числом.
Доказательство.
Пусть составное число, тогда. Рассмотрим нормы.
То есть получили, что норма составное число, а по условию есть простое число. Следовательно, наше предположение не верно, и есть простое число.
Утверждение.
Если простое натуральное число не является простым гауссовым, то оно представимо в виде суммы двух квадратов.
Доказательство.
Пусть простое натуральное число и не является простым гауссовым. Тогда. Так как равны числа, то равны и их нормы. То есть, отсюда получаем.
Возможно два случая:
1). , то есть представили в виде суммы двух квадратов.
2). , то есть, значит обратимое число, чего не может быть, значит этот случай нас не удовлетворяет.
ГЛАВА 3. ПРИМЕНЕНИЕ ЧИСЕЛ ГАУССА.
Утверждение.
Произведение чисел представимых в виде суммы двух квадратов также представимо в виде суммы двух квадратов.
Доказательство.
Докажем этот факт двумя способами, с помощью чисел Гаусса, и не используя гауссовы числа.
1. Пусть, -- натуральные числа представимые в виде суммы двух квадратов. Тогда, и. Рассмотрим произведение, то есть представили в виде произведения двух сопряженных гауссовых чисел, которое представляется в виде суммы двух квадратов натуральных чисел.
2. Пусть, . Тогда
Утверждение.
Если, где -- простое натуральное вида, то и.
Доказательство.
Из условия следует, что и при этом -- простое гауссово. Тогда по лемме Евклида на делится один из множителей. Пусть, тогда по лемме 10 имеем, что и.
Опишем общий вид натуральных чисел представимых в виде суммы двух квадратов.
Рождественская теорема Ферма или теорема Ферма -- Эйлера .
Ненулевое натуральное число представимо в виде суммы двух квадратов тогда, и только тогда, когда в каноническом разложении все простые множители вида входят в четных степенях.
Доказательство.
Заметим, что 2 и все простые числа вида представимы в виде суммы двух квадратов. Пусть в каноническом разложении числа есть простые множители вида, входящие в нечетной степени. Занесем в скобки все множители представимые в виде суммы двух квадратов, тогда останутся множители вида, причем все в первой степени. Покажем, что произведение таких множителей не представимо в виде суммы двух квадратов. Действительно, если допустить, что, то имеем, что должен делить один из множителей или, но если делит одно из этих гауссовых чисел, то оно обязано и делить другое, как сопряженное к нему. То есть и, но тогда должно быть во второй степени, а оно в первой. Следовательно, произведение любого числа простых множителей вида первой степени не представимо в виде суммы двух квадратов. Значит наше предположение не верно и все простые множители вида в каноническом разложении числа входят в четных степенях.
Задача 1.
Посмотрим применение данной теории на примере решения диафантова уравнения.
Решить в целых числах.
Заметим, что правая часть представима в виде произведения сопряженных гауссовых чисел.
То есть. Пусть делится на некоторое простое гауссово число, и на него делится и сопряженное, то есть. Если рассмотреть разность этих гауссовых чисел, которая должна делиться на, то получим, что должно делить 4. Но, то есть союзно с.
Все простые множители в разложении числа входят в степени кратной трем, а множители вида, в степени кратной шести, так как простое гауссово число получается из разложения на простые гауссовы 2, но, поэтому. Сколько раз встречается в разложении на простые множители числа, столько же раз и встречается в разложении на простые множители числа. В силу того, что делится на тогда и только тогда, когда делится на. Но союзно с. То есть они распределятся поровну, значит, будут входить в разложения этих чисел в степенях кратной трем. Все остальные простые множители, входящие в разложение числа, будут входить только либо в разложение числа, либо числа. Значит, в разложении на простые гауссовы множители числа все множители будут входить в степени кратной трем. Следовательно число есть куб. Таким образом имеем, что. Отсюда получаем, что, то есть должно быть делителем 2. Значит, или. Откуда получаем четыре удовлетворяющие нам варианта.
1. , . Откуда находим, что, .
2. , . Отсюда, .
3. , . Отсюда, .
4. , . Отсюда, .
Задача 2.
Решить в целых числах.
Представим левую часть как произведению двух гауссовых чисел, то есть. Разложим каждое из чисел на простые гауссовы множители. Среди простых будут такие, которые есть в разложении и. Сгруппируем все такие множители и обозначим полученное произведение. Тогда в разложении останутся только те множители, которых нет в разложении. Все простые гауссовы множители, входящие в разложение, входят в четной степени. Те которые не вошли в будут присутствовать либо только в, либо в. Таким образом, число является квадратом. То есть. Приравнивая действительные и мнимые части, получим, что, .
Задача 3.
Количество представлений натурального числа в виде суммы двух квадратов.
Задача равносильна задаче о представлении данного натурального числа в виде нормы некоторого числа Гаусса. Пусть -- число Гаусса, норма которого равна. Разложим на простые натуральные множители.
Где -- простые числа вида, а -- простые числа вида. Тогда, чтобы было представимо в виде суммы двух квадратов, необходимо, чтобы все были четными. Разложим на простые гауссовы множители число, тогда
где -- простые гауссовы числа, на которые раскладываются.
Сравнение нормы с числом приводит к следующим соотношениям, необходимым и достаточным для того, чтобы:
Число представлений подсчитывается из общего числа возможностей для выбора показателей. Для показателей имеется возможность, так как число можно разбить на два неотрицательных слагаемых способом:
Для пары показателей имеется возможность и так далее. Комбинируя всевозможными способами допустимые значения для показателей мы получим всего различных значений для произведения простых гауссовых чисел, с нормой вида или 2. Показатели выбираются однозначно. Наконец, обратимому можно придавать четыре значения: .Таким образом, для числа имеется всего возможностей, и следовательно, число в виде нормы гауссова числа, то есть в виде может быть представлено способами.
При этом подсчете различными считаются все решения уравнения. Однако некоторые решения можно рассматривать, как определяющие одно и то же представление в виде суммы двух квадратов. Так, если -- решения уравнения, то можно указать еще семь решений, определяющих то же самое представление числа в виде суммы двух квадратов: .
Очевидно, что из восьми решений, соответствующих одному представлению, может остаться только четыре различных в том и только в том случае, если или, или. Подобные представления возможны, если полный квадрат или удвоенный полный квадрат, и при том такое представление может быть только одно: .
Таким образом, имеем следующие формулы:
Если не все четные и
Если все четные.
Заключение.
В данной работе была изучена теория делимости в кольце целых чисел Гаусса, а также природа простых гауссовых чисел. Эти вопросы изложены в первых двух главах.
В третей главе рассмотрены применения чисел Гаусса к решению известных классических задач, таких как:
· Вопрос о возможности представления натурального числа в виде суммы двух квадратов;
· Задача нахождения количества представлений натурального числа в виде суммы двух квадратов;
· Нахождение общих решений неопределенного уравнения Пифагора;
а также к решению диафантова уравнения.
Также отмечу, что работа была выполнена без использования дополнительной литературы.
Подобные документы
Свойства делимости целых чисел в алгебре. Особенности деления с остатком. Основные свойства простых и составных чисел. Признаки делимости на ряд чисел. Понятия и способы вычисления наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК).
лекция , добавлен 07.05.2013
Обзор квадратурных формул Гаусса, их определение, интегральные конструкции, примеры, четко описывающие квадратуры Гаусса. Особенности использования некоторых алгоритмов, позволяющих отследить ход решений задач, использующих квадратурные формулы Гаусса.
контрольная работа , добавлен 16.12.2015
Сложение и умножение целых p-адических чисел, определяемое как почленное сложение и умножение последовательностей. Кольцо целых p-адических чисел, исследование свойств их деления. Объяснение данных чисел с помощью ввода новых математических объектов.
курсовая работа , добавлен 22.06.2015
Понятие матрицы. Метод Гаусса. Виды матриц. Метод Крамера решения линейных систем. Действия над матрицами: сложение, умножение. Решение систем линейных уравнений методом Гаусса. Элементарные пребразования систем. Математические перобразования.
лекция , добавлен 02.06.2008
Закон сохранения количества чисел Джойнт ряда в натуральном ряду чисел как принцип обратной связи чисел в математике. Структура натурального ряда чисел. Изоморфные свойства рядов четных и нечетных чисел. Фрактальная природа распределения простых чисел.
монография , добавлен 28.03.2012
Иоганн Карл Фридрих Гаусс - величайший математик всех времен. Интерполяционные формулы Гаусса, дающие приближенное выражение функции y=f(x) при помощи интерполяции. Области применение формул Гаусса. Основные недостатки интерполяционных формул Ньютона.
контрольная работа , добавлен 06.12.2014
Расширенный алгоритм Евклида, его использование для нахождения наибольшего общего делителя натуральных чисел посредством остатков от деления. Математическая проблема календаря. Евклидовы кольца - аналоги чисел Фибоначчи в кольце многочленов, их свойства.
реферат , добавлен 25.09.2009
Вивчення властивостей натуральних чисел. Нескінченість множини простих чисел. Решето Ератосфена. Дослідження основної теореми арифметики. Асимптотичний закон розподілу простих чисел. Характеристика алгоритму пошуку кількості простих чисел на проміжку.
курсовая работа , добавлен 27.07.2015
Расчет значений комплексных чисел в алгебраической, тригонометрической и показательной формах. Определение расстояния между точками на комплексной плоскости. Решение уравнения на множестве комплексных чисел. Методы Крамера, обратной матрицы и Гаусса.
контрольная работа , добавлен 12.11.2012
Теоретико-числовая база построения СОК. Теорема о делении с остатком. Алгоритм Евклида. Китайская теорема об остатках и её роль в представлении чисел в СОК. Модели модулярного представления и параллельной обработки информации. Модульные операции.
Натуральные числа не являются кольцом, так как 0 не является натуральным числом, а также для натуральных чисел нет натуральных противоположных им. Структура, образуемая натуральными числами, называется полукольцом. Более точно,
Полукольцом называется коммутативная полугруппа по сложению и полугруппа по умножению, в которой операции сложения и умножения связаны дистрибутивными законами.
Введём теперь строгие определения целых чисел и докажем их эквивалентность. Исходя из представлений об алгебраических структурах и того факта, что множество натуральных числе является полукольцом, но не является кольцом, можно ввести следующее определение:
Определение 1. Кольцом целых чисел называется минимальное кольцо, содержащее в себе полукольцо натуральных чисел.
Данное определение ничего не сообщает о внешнем виде таких чисел. В школьном курсе целые числа определяются как натуральные числа, им противоположные и 0. Данное определение также можно взять за основу для построения строгого определения.
Определение 2. Кольцом целых чисел называется кольцо, элементами которого являются натуральные числа, им противоположные и 0 (и только они).
Теорема 1 . Определения 1 и 2 эквивалентны.
Доказательство : Обозначим через Z 1 кольцо целых чисел в смысле определения 1, а через Z 2 – кольцо целых чисел в смысле определения 2. В начале докажем, что Z 2 включается в Z 1 . Действительно, все элементы Z 2 это либо натуральные числа (они принадлежат Z 1 , так как Z 1 содержит в себе полукольцо натуральных чисел), либо им противоположные (они тоже принадлежат Z 1 , так как Z 1 кольцо, а значит для каждого элемента этого кольца существует противоположный, и для каждого натурального n Î Z 1 , –n также принадлежит Z 1), либо 0 (0 Î Z 1 , так как Z 1 кольцо, а в любом кольце имеется 0), таким образом, любой элемент из Z 2 принадлежит также и Z 1 , а значит Z 2 Í Z 1 . С другой стороны, Z 2 содержит в себе полукольцо натуральных чисел, а Z 1 является минимальным кольцом, содержащим в себе натуральные числа, то есть не может содержать в себе никакого другого кольца, удовлетворяющего этому условию. Но мы показали, что оно содержит в себе Z 2 , а значит Z 1 = Z 2 . Теорема доказана.
Определение 3. Кольцом целых чисел называется кольцо, элементами которого являются все возможные элементы, представимые в виде разности b – а (все возможные решения уравнения a + x = b), где а и b – произвольные натуральные числа.
Теорема 2 . Определение 3 эквивалентно двум предыдущим.
Доказательство : Обозначим через Z 3 кольцо целых чисел в смысле определения 3, а через Z 1 = Z 2 , как и раньше, – кольцо целых чисел в смысле определения 1 и 2 (их равенство уже установлено). Сначала докажем, что Z 3 включается в Z 2 . Действительно, все элементы Z 3 можно представить в виде некоторых разностей натуральных чисел b – а. Для любых двух натуральных чисел по теореме о трихотомии возможно три варианта:
В этом случае разность b – а также является числом натуральным и потому принадлежит Z 2 .
В этом случае разность двух равных между собой элементов обозначим символом 0. Докажем, что это действительно нуль кольца, то есть нейтральный элемент относительно сложения. Для этого воспользуемся определением разности a – a = x ó a = a + x и докажем, что b + x = b для любого натурального b. Для доказательства достаточно прибавить к правой и левой части равенства a = a + x элемент b, а затем воспользоваться законом сокращения (все эти действия можно выполнять исходя из известных свойств колец). Нуль же принадлежит Z 2 .
В этом случае разность a – b есть число натуральное, обозначим
b – a = – (a – b). Докажем, что элементы a – b и b – a действительно являются противоположными, то есть в сумме дают нуль. В самом деле, если обозначить a – b = х, b – a = у, то получим, что a = b + х, b = у + a. Складывая почленно полученные равенства и сокращая b, получим a = х + у + a, то есть х + у = а – а = 0. Таким образом a – b = – (b – a) является числом противоположным натуральному, то есть вновь принадлежит Z 2 . Таким образом, Z 3 Í Z 2 .
С другой стороны Z 3 содержит в себе полукольцо натуральных чисел, так как любое натуральное число n всегда можно представить как
n = n / – 1 Î Z 3 ,
а значит Z 1 Í Z 3 , так как Z 1 является минимальным кольцом, содержащим в себе натуральные числа. Пользуясь уже доказанным фактом, что Z 2 = Z 1 , получаем Z 1 = Z 2 = Z 3 . Теорема доказана.
Хотя на первый взгляд может показаться, что никаких аксиом в перечисленных определениях целых чисел нет, данные определения являются аксиоматическими, так как во всех трёх определениях говорится, что множество целых чисел является кольцом. Поэтому аксиомами в аксиоматической теории целых чисел служат условия из определения кольца.
Докажем, что аксиоматическая теория целых чисел непротиворечива . Для доказательства необходимо построить модель кольца целых чисел, пользуясь заведомо непротиворечивой теорией (в нашем случае это может быть только аксиоматическая теория натуральных чисел).
Согласно определению 3, каждое целое число представимо в виде разности двух натуральных z = b – а. Сопоставим каждому целому числу z соответствующую пару
Введённое отношение является рефлексивным, симметричным и транзитивным (доказательство предоставляется читателю).
Как и всякое отношение эквивалентности, данное отношение порождает разбиение множества всевозможных пар натуральных чисел на классы эквивалентности, которые мы будем обозначать как [
1) [
2) [
Покажем, что введенные определения корректны, то есть не зависят от выбора конкретных представителей из классов пар. Иными словами, если эквивалентны пары
Доказательство : Применим определение эквивалентности пар:
Почленно сложив равенства (1) и (2), получим:
а + b 1 + с + d 1 = b + a 1 + d + c 1 .
Все слагаемые в последнем равенстве – натуральные числа, поэтому мы в праве применить коммутативный и ассоциативный законы сложения, что приводит нас к равенству
(а + с) + (b 1 + d 1)= (b + d) + (a 1 + c 1),
которое равносильно условию @ .
Для доказательства корректности умножения, равенство (1) умножим на с, получим:
ас + b 1 с= bс + a 1 с.
Затем перепишем равенство (1) в виде b + a 1 = а + b 1 и умножим на d:
bd + a 1 d = аd + b 1 d.
Почленно сложим полученные равенства:
ас + bd + a 1 d + b 1 с = bс + аd + b 1 d + a 1 с,
что означает, что
Затем ту же процедуру проделаем с равенством (2), только умножать его будем на а 1 и b 1 . Получим:
а 1 с + а 1 d 1 = а 1 d + а 1 c 1
b 1 d + b 1 c 1 = b 1 с + b 1 d 1 ,
а 1 с + b 1 d + b 1 c 1 + а 1 d 1 = а 1 d + b 1 d + b 1 c 1 + а 1 c 1 ó
ó @
(здесь мы доказали, что ×
Таким образом, корректность введённых определений доказана.
Далее непосредственно проверяются все свойства колец: ассоциативный закон сложения и умножения для классов пар, коммутативный закон сложения, дистрибутивные законы. Приведем в качестве примера доказательство ассоциативного закона сложения:
Так как все компоненты пар числа натуральные
= <(a + c) +m), (b + d) +n)> =
= <(a + c), (b + d)> +
Остальные законы проверяются аналогично (заметим, что полезным приёмом может служить отдельное преобразование левой и правой части требуемого равенства к одному и тому же виду).
Необходимо также доказать наличие нейтрального элемента по сложению. Им может служить класс пар вида [<с, с>]. Действительно,
[
а + c + b = b + c + a (справедливо для любых натуральных чисел).
Кроме того, для каждого класса пар [
Можно также доказать, что введённое множество классов пар есть коммутативное кольцо с единицей (единицей может служить класс пар [
[
Проверим, пользуясь данным правилом, справедливость условий С1 и С2 (из определения сложения натуральных чисел). Условие С1 (а + 1 = а /) в данном случае перепишется в виде:
[
[
a + c / +b = a + b + 1 + c = b + c + a +1 = b + с + a /
(ещё раз напомним, что все компоненты натуральные).
Условие С2 будет иметь вид:
[
Преобразуем отдельно левую и правую части данного равенства:
[
([
Таким образом, мы видим, что левые и правые части равны, значит условие С2 справедливо. Доказательство условия У1 предоставляется читателю. условие У2 является следствием дистрибутивного закона.
Итак, модель кольца целых чисел построена, а, следовательно, аксиоматическая теория целых чисел непротиворечива, если непротиворечива аксиоматическая теория натуральных чисел.
Свойства операций над целыми числами :
2) а×(–b) = –a×b = –(ab)
3) – (– a) = a
4) (–a)×(–b) = ab
5) a×(–1) = – a
6) a – b = – b + a = – (b – a)
7) – a – b = – (a +b)
8) (a – b) ×c = ac – bc
9) (a – b) – c = a – (b + c)
10) a – (b – c) = a – b + c.
Доказательства всех свойств повторяют доказательства соответствующих свойств для колец.
1) а + а×0 = а×1 + а×0 = a ×(1 + 0) = a×1 = а, то есть а×0 является нейтральным элементом по сложению.
2) а×(–b) + ab = a(–b + b) = a×0 = 0, то есть элемент а×(–b) является противоположным к элементу а×b.
3) (– a) + a = 0 (по определению противоположного элемента). Аналогично (– a) +(– (– a)) = 0. Приравнивая левые части равенств и применяя закон сокращения, получим – (– a) = а.
4) (–a)×(–b) = –(a×(–b)) = –(–(а×b)) = ab.
5) a×(–1) + а = a×(–1) + a×1 = a×(–1 + 1) = a×0 = 0
a×(–1) + а = 0
a×(–1) = –а.
6) По определению разности a – b есть такое число х, что а = х + b. Прибавляя к правой и левой части равенства –b слева и пользуясь коммутативным законом, получаем первое равенство.
– b + a + b – a = –b + b + а – a = 0 + 0 = 0, что доказывает второе равенство.
7) – a – b = – 1×a – 1×b = –1×(a +b) = – (a +b).
8) (a – b) ×c = (a +(–1)× b) ×c = ac +(–1)×bc = ac – bc
9) (a – b) – c = х,
a – b = х + c,
a – (b + c) = х, то есть
(a – b) – c = a – (b + c).
10) a – (b – c) = a + (– 1)×(b – c) = a + (– 1×b) + (–1)× (– c) = a – 1×b + 1×c = = a – b + c.
Задания для самостоятельного решения
№ 2.1. В правом столбце таблицы найти пары эквивалентные парам, приведённым в левом столбце таблицы.
| а) <7, 5> | 1) <5, 7> |
| б) <2, 3> | 2) <1, 10> |
| в) <10, 10> | 3) <5, 4> |
| г) <6, 2> | 4) <15, 5> |
| 5) <1, 5> | |
| 6) <9, 9> |
Для каждой пары указать ей противоположную.
№ 2.2. Вычислить
а) [<1, 5>] + [ <3, 2>]; б)[<3, 8>] + [<4, 7>];
в) [<7, 4>] – [<8, 3>]; г) [<1, 5>] – [ <3, 2>];
д) [<1, 5>] × [ <2, 2>]; е) [<2, 10>]× [<10, 2>].
№ 2.3. Для модели целых чисел, описанной в данном разделе, проверить коммутативный закон сложения, ассоциативный и коммутативный законы умножения, дистрибутивные законы.
Мы видели, что действия над многочленами сводятся к действиям над их коэффициентами. При этом для сложения, вычитания и умножения многочленов достаточно трех арифметических действий - деление чисел не понадобилось. Так как сумма, разность и произведение двух действительных чисел снова являются действительными числами, то при сложении, вычитании и умножении многочленов с действительными коэффициентами в результате получаются многочлены с действительными же коэффициентами.
Однако не всегда приходится иметь дело с многочленами, имеющими любые действительные коэффициенты. Возможны случаи, когда по самой сути дела коэффициенты должны иметь лишь целые или лишь рациональные значения. В зависимости от того, какие значения коэффициентов считаются допустимыми, меняются свойства многочленов. Например, если рассматривать многочлены с любыми действительными коэффициентами, то можно разложить на множители:
Если же ограничиться многочленами с целыми коэффициентами, то разложение (1) не имеет смысла и мы должны считать многочлен неразложимым на множители.
Отсюда видно, что теория многочленов существенно зависит от того, какие коэффициенты считаются допустимыми. Далеко не любую совокупность коэффициентов можно принять за допустимую. Например, рассмотрим все многочлены, коэффициенты которых - нечетные целые числа. Ясно, что сумма двух таких многочленов уже не будет многочленом того же типа: ведь сумма нечетных чисел - четное число.
Поставим вопрос: каковы «хорошие» множества коэффициентов? Когда сумма, разность, произведение многочленов с коэффициентами данного типа имеют коэффициенты того же типа? Для ответа на этот вопрос введем понятие числового кольца.
Определение. Непустое множество чисел называется числовым кольцом, если вместе с любыми двумя числами а и оно содержит их сумму, разность и произведение. Это выражают также короче, говоря, что числовое кольцо замкнуто относительно операций сложения, вычитания и умножения.
1) Множество целых чисел является числовым кольцом: сумма, разность и произведение целых чисел - целые числа. Множество же натуральных чисел числовым кольцом не является, так как разность натуральных чисел может быть отрицательной.
2) Множество всех рациональных чисел - числовое кольцо, так как сумма, разность и произведение рациональных чисел рациональны.
3) Образует числовое кольцо и множество всех действительных чисел.
4) Числа вида а где а и целые, образуют числовое кольцо. Это следует из соотношений:
5) Множество нечетных чисел не является числовым кольцом, так как сумма нечетных чисел четна. Множество же четных чисел - числовое кольцо.
Из курса программирования известно, что целое число может быть представлено в памяти компьютера разными способами, в частности, это представление зависит от того, как оно описано: как величина типа integer , или real , или string . При этом в большинстве языков программирования под целыми числами понимаются числа из весьма ограниченного диапазона: типичный случай - от -2 15 = -32768 до 2 15 - 1 = 32767 . Системы компьютерной алгебры имеют дело с большими целыми числами, в частности, любая такая система умеет вычислять и выводить в десятичной записи числа вида 1000 ! (более тысячи знаков).
В данном курсе мы будем рассматривать представление целых чисел в символьном виде и не вдаваться в подробности, какая память отводится для записи одного символа (бит, байт или другая). Наиболее распространенным является представление целых чисел в позиционных системах счисления . Такая система определяется выбором основания счисления, например, 10 . Множество десятичных целых чисел обычно описывается следующим образом:
Выписанное определение целых чисел дает однозначность представления каждого такого числа, и аналогичное определение (только, может быть, с другим основанием) используется в большинстве систем компьютерной алгебры . Пользуясь таким представлением, удобно реализовать арифметические операции над целыми числами. При этом сложение и вычитание являются относительно "дешевыми" операциями, а умножение и деление - "дорогими" . При оценке сложности арифметических операций следует учитывать как стоимость элементарной операции (одноразрядной), так и количество одноразрядных операций для выполнения какого-либо действия над многозначными числами. Сложность умножения и деления обусловлена, в первую очередь, тем, что с ростом длины числа (его записи в какой-либо системе счисления) количество элементарных операций увеличивается по квадратичному закону, в отличие от линейного для сложения и вычитания. К тому же, то, что мы обычно называем алгоритмом деления многозначных чисел, в действительности основано на переборе (часто весьма значительном) возможной очередной цифры частного, и при этом недостаточно просто воспользоваться правилами деления однозначных чисел. При большом основании системы счисления (часто оно может иметь порядок 2 30 ) этот способ малоэффективен.
Пусть - натуральное число (записанное в десятичной
системе).
Чтобы получить его запись 
в -ичной
системе счисления, можно воспользоваться следующим алгоритмом
( обозначает целую часть числа ):
Дано: A-натуральное число в десятичной системе счисления k > 1-натуральное число Надо: A-запись числа A в k-ичной системе счисления Начало i:= 0 цикл пока A > 0 bi:= A (mod k) A:= i:= i + 1 конец цикла dA:= i - 1 Конец
Для восстановления десятичного числа по последовательности его k -ичной записи используется следующий алгоритм:
Дано: k > 1-натуральное число последовательность цифр, представляющих число A в k-ичной системе Надо: A-запись числа A в десятичной системе счисления Начало A:= 0 цикл пока не конец последовательности b:= очередной элемент последовательности A:= A * k + b конец цикла Конец
1.2. УПРАЖНЕНИЕ. Объясните, почему для перевода числа из десятичной системы в k -ичную используется деление, а для перевода из k -ичной системы в десятичную - умножение.
Перемножая "столбиком" два двузначных числа в десятичной системе счисления, мы выполняем следующие операции:
(10a + b)(10c + d) = 100ac + 10(ad + bc) + bd,
т. е. 4 операции умножения одноразрядных чисел, 3 операции сложения и 2 операции умножения на степень основания счисления, которые сводятся к сдвигу. При оценке сложности можно учитывать все элементарные операции, не разделяя их по весам (в данном примере мы имеем 9 элементарных операций). Задача оптимизации алгоритма сводится при данном подходе к минимизации общего числа элементарных операций. Можно, однако, считать, что умножение является более "дорогой" операцией, чем сложение, которое, в свою очередь, "дороже" сдвига. Учитывая только наиболее дорогие операции, мы получаем, что мультипликативная сложность умножения двузначных чисел "столбиком" равна 4.
В параграфе 5 рассматриваются алгоритмы вычисления наибольших общих делителей и оценивается их сложность.
Рассмотренное представление не является единственным каноническим представлением целых чисел. Как уже отмечалось, для выбора канонического представления можно воспользоваться единственностью разложения натурального числа на простые множители. Такое представление целого числа может быть применено в тех задачах, где используются только операции умножения и деления, так как они становятся очень "дешевыми" , однако несоизмеримо возрастает стоимость операций сложения и вычитания, что препятствует использованию подобного представления. В некоторых задачах отказ от канонического представления дает значительный выигрыш в быстродействии, в частности, может использоваться частичное разложение числа на множители. Особенно полезен аналогичный метод при работе не с числами, а с многочленами.
Если известно, что при работе программы все встречающиеся в вычислениях целые числа ограничены по абсолютной величине некоторой заданной константой, то можно использовать для задания таких чисел их систему вычетов по модулям некоторых взаимно простых чисел, произведение которых превосходит упомянутую константу. Вычисления с классами вычетов выполняются, как правило, быстрее, чем арифметика многократной точности. А арифметикой многократной точности при таком подходе нужно пользоваться только при вводе или выводе информации.
Отметим, что наряду с каноническими представлениями в системах компьютерной алгебры используются и другие представления. В частности, желательно, чтобы наличие или отсутствие знака "+" перед целым числом не влияло на восприятие его компьютером. Таким образом, для положительных чисел получается неоднозначное представление, хотя форма отрицательных чисел определена однозначно.
Другое требование - на восприятие числа не должно влиять наличие нулей перед первой значащей цифрой.
1.3. УПРАЖНЕНИЯ.
- Оценить количество одноразрядных умножений, используемых при умножении столбиком m -значного числа на n - значное.
- Показать, что два двузначных числа можно перемножить, используя только 3 умножения однозначных чисел и увеличив число сложений.
- Найти алгоритм деления длинных чисел, не требующий большого перебора при нахождении первой цифры частного.
- Описать алгоритм перевода натуральных чисел из m -ичной системы счисления в n -ичную.
- В римской нумерации для записи чисел используются следующие символы: I - единица, V - пять, X - десять, L - пятьдесят, C - сто, D - пятьсот, M - тысяча. Символ считается отрицательным, если правее него найдется символ большего числа, и положительным в противном случае. Например, число 1948 в этой системе запишется так: MCMXLVIII . Сформулировать алгоритм перевода числа из римской записи в десятичную и обратно. Реализовать полученный алгоритм на одном из алгоритмических языков (например, C ). Ограничения на исходные данные: 1 <= N < 3700 , в записи результата ни один символ не должен появляться больше 3 раз.
- Сформулировать алгоритм и написать программу сложения натуральных чисел в римской нумерации.
- Будем говорить, что мы имеем дело с системой счисления со смешанным или векторным основанием , если нам задан вектор из n натуральных чисел M = (m 1 , . . . ,m n) (осно вание счисления) и запись K = (k 0 , k 1 , . . . , k n) обозначает число k = k 0 +m 1 (k 1 +m 2 (k 2 +· · ·+m n ·k n) . . .)) . Написать программу, которая по данным (день недели, часы, минуты, секунды) определяет, сколько секунд прошло с начала недели (понедельник, 0, 0, 0) = 0 , и выполняет обратное преобразование.
