Теория малых чисел. Теория чисел: теория и практика

Теория чисел или высшая арифметика - раздел математики, изучающий целые числа и сходные объекты.

Теория чисел занимается изучением свойств целых чисел. В настоящее время в теорию чисел включают значительно более широкий круг вопросов, выходящих за рамки изучения натурах чисел.

В теории чисел рассматриваются не только натуральные числа, но и множество всех целых чисел, множество рациональных чисел, множество алгебраических чисел. Для современной теории чисел характерно применение весьма разнообразных методов исследований. В современной теории чисел широко пользуются методами математического анализа.

Современную теорию чисел можно разбить на следующие разделы:

1) Элементарная теория чисел. К этому разделу относят вопросы теории чисел, являющиеся непосредственным развитием теории делимости и вопросы о представимости чисел в определенной форме. Более общей является задача решения систем диофантовых уравнений, то есть уравнений, в которых значения неизвестных должны быть обязательно целыми числами.

2) Алгебраическая теория чисел. К этому разделу относят вопросы, связанные с изучением различных классов алгебраических чисел.

3) Диофантовы приближения. К этому разделу относят вопросы, связанные с изучением приближения действительных чисел рациональными дробями. К диофантовым приближениям примыкают тесно связанные с этим же кругом идей вопросы изучения арифметической природы различных классов чисел.

4) Аналитическая теория чисел. К этому разделу относят вопросы теории чисел, для изучения которых приходится применять методы математического анализа.

Основные понятия:

1) Дели?мость - одно из основных понятий арифметики и теории чисел, связанное с операцией деления. С точки зрения теории множеств, делимость целых чисел является отношением, определённым на множестве целых чисел.

Если для некоторого целого числа a и целого числа b существует такое целое число q, что bq = a, то говорят, что число a делится нацело на b или, что b делит a. При этом число b называется делителем числа a, делимое a будет кратным числа b, а число q называется частным от деления a на b.

2) Просто?е число? - это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя. Все остальные числа, кроме единицы, называются составными.

3) Совершенное число? (др.-греч. ἀριθμὸς τέλειος) - натуральное число, равное сумме всех своих собственных делителей (т. е. всех положительных делителей, отличных от самого? числа).

Первое совершенное число - 6 (1 + 2 + 3 = 6), следующее - 28 (1 + 2 + 4 + 7 + 14 = 28). По мере того как натуральные числа возрастают, совершенные числа встречаются всё реже.

4) Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей. Пример: для чисел 70 и 105 наибольший общий делитель равен 35.

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.

5) Наименьшее общее кратное (НОК) двух целых чисел m и n - это наименьшее натуральное число, которое делится на m и n.

6) Числа m и n называются взаимно-простыми, если у них нет общих делителей, кроме единицы. Для таких чисел НОД(m,n) = 1. Обратно, если НОД(m,n) = 1, то числа взаимно просты.

7) Алгори?тм Евкли?да - алгоритм для нахождения наибольшего общего делителя двух целых чисел или наибольшей общей меры двух однородных величин.

Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:

Еще по теме №17. Основные понятия теории чисел.:

Теория чисел - раздел математики, в котором изучаются свойства чисел.

Основной объект теории чисел - натуральные числа (см. Число). Главное их свойство, которое рассматривает теория чисел, это делимость. Первый круг задач теории чисел - разложение чисел на множители. Основными «кирпичиками» в таком разложении являются простые числа, т.е. числа, делящиеся только на 1 и на себя; 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 - вот первые десять простых чисел (число 1 не относят к простым). Замечательная теорема, называемая основной теоремой арифметики, гласит: всякое натуральное число раскладывается на простые множители, причем единственным способом (с точностью до порядка их расположения). Разложив два числа на простые множители, несложно определить, делится одно из них на другое или нет. Но до сих пор бывает трудно выяснить, является ли данное большое число простым, т.е. делится ли оно на какое-либо другое число, кроме себя и единицы.

С разложением чисел на простые множители связан ряд арифметических функций. Укажем некоторые из них. φ(n) - функция Эйлера - количество чисел от 1 до n, взаимно простых с числом n (т.е. не имеющих с n общих множителей, кроме единицы); α(n) количество делителей числа n, т(п)-сумма всех делителей числа n, π(n) - функция Чебышева - количество простых чисел, не превосходящих n. С помощью этих функций выражаются многие свойства натуральных чисел. Теорема Евклида утверждает, что простых чисел бесконечно много. Это означает, что π(n)→∞ при возрастании числа n. Удалось выяснить, как быстро функция π(n) стремится к бесконечности. Оказалось, что примерно так же, как функция

Эта теорема носит название асимптотического закона распределения простых чисел. Она была сформулирована и в существенной части доказана П. Л. Чебышевым (1849), а полностью доказана лишь 50 лет спустя.

Асимптотический закон распределения простых чисел - это результат так называемой аналитической теории чисел, которая широко использует методы математического анализа для исследования теоретико-числовых функций. Обнаруженный во второй половине XIX в. факт связи такого дискретного объекта, как целые числа, с глубокими свойствами функций оказал большое влияние на развитие теории чисел.

Разложение чисел на множители учитывает только структуру множества натуральных чисел, связанную с умножением, наиболее глубокие и трудные задачи теории чисел возникают при сравнении сложения и умножения. К числу таких задач можно отнести, например, проблему Гольдбаха - можно ли всякое четное число представить как сумму двух простых; великую теорему Ферма (см. Ферма великая теорема) - можно ли n-ю степень числа представить как сумму n-х степеней двух каких-либо чисел и т.п.

Теория чисел привлекательна тем, что в ней много простых по формулировкам, но трудных и интересных задач. Этих задач-решенных и нерешенных - накопилось очень много, и часто теория чисел представляется собранием разрозненных изящных головоломок. Однако это не так. Теория чисел создала свои замечательные методы, причем многие из них активно развиваются в последние десятилетия, что влило новую живую струю в эту самую древнюю часть математики.

Классическим методом теории чисел является метод сравнений. Отождествляя между собой числа, дающие одинаковые остатки при делении на выбранное число, часто удается установить невозможность какого-либо соотношения. Например, рассматривая остатки от деления на 3 (или, как говорят, по модулю 3), легко доказать неразрешимость в натуральных числах уравнения Зх 2 + 4у 2 = 5z 2 .

Аналитический метод состоит, как мы уже говорили, в том, что, отправляясь от чисел, строят функции, которые исследуют методами математического анализа. Так, советский ученый академик И. М. Виноградов доказал вариант проблемы Гольдбаха - представимость достаточно большого нечетного числа в виде суммы трех простых.

Геометрический метод теории чисел мы проиллюстрируем на примере великой теоремы Ферма. В этой теореме идет речь о разрешимости в целых числах уравнения х n + у n = z n . Поделив обе части уравнения на z n и заменив x/z на м, a y/z на v, получим уравнение u n + v n = 1. Это уравнение задает на плоскости с координатами (u, v) некоторую кривую. Решения исходного уравнения в целых числах соответствуют решениям нового уравнения в рациональных числах. О каждом таком решении (u, v) можно говорить как о точке с рациональными координатами на этой плоскости. Теперь можем попытаться применить геометрические методы к кривой u n + v n = 1 для исследования на ней множества точек с рациональными координатами.

Большой раздел теории чисел, занимающийся нахождением решений уравнений в целых и рациональных числах, носит название теории диофантовых уравнений, по имени древнегреческого ученого Диофанта (III в.).

К числу очень старых и известных задач теории чисел относится задача представления чисел суммами квадратов. Перечислим некоторые из полученных результатов:

каждое целое число можно представить как сумму четырех квадратов целых чисел (например: 7 = 2 2 + 1 2 + 1 2 + 1 2);

каждое простое число вида 4n + 1 можно представить в виде суммы двух квадратов целых чисел (например: 5 = 2 2 + 1 2 , 41 = 4 2 + 5 2 и т. п.), а ни одно целое (не только простое) число вида 4n + 3 нельзя представить в таком виде;

каждое простое число, кроме чисел вида 8n - 1, можно представить в виде суммы трех квадратов целых чисел.

Простое алгебраическое тождество

(а 2 + b 2) (х 2 + у 2) = (ах + by) 2 + (ay - bx) 2

позволяет сделать вывод: если два числа представимы суммами двух квадратов, то и их произведение представимо суммой двух квадратов. Алгебраические методы в последнее время широко применяются в теории чисел. Этому способствовало развитие такого общего алгебраического понятия, как поле, само появление которого во многом стимулировалось задачами теории чисел.

Чем особенно ценна теория чисел? Ведь найти непосредственное применение ее результатам трудно. Тем не менее задачи теории чисел привлекают как пытливых молодых людей, так и ученых в течение многих столетий. В чем же здесь дело? Прежде всего эти задачи, как уже говорилось, очень интересны и красивы. Во все времена человека поражало, что на простые вопросы о числах так трудно найти ответ. Поиски этих ответов часто приводили к открытиям, значение которых далеко превосходит рамки теории чисел. Достаточно упомянуть о так называемой теории идеалов немецкого математика XIX в. Э. Куммера, которая родилась в связи с попытками доказать великую теорему Ферма.

Название: Теория чисел. 2008.

Основу учебника составляют результаты элементарной теории чисел, сформировавшейся в трудах классиков - Ферма, Эйлера, Гаусса и др. Рассматриваются такие вопросы как простые и составные числа, арифметические функции, теория сравнений, первообразные корни и индексы, цепные дроби, алгебраические и трансцендентные числа. Обзорно освещены свойства простых чисел, теория диофантовых уравнений, алгоритмические аспекты теории чисел с применениями в криптографии (проверка больших простых чисел на простоту, разложение больших чисел на множители, дискретное логарифмирование) и с использованием ЭВМ.
Для студентов высших учебных заведений.

Предмет изучения теории чисел - числа и их свойства, т. е. числа выступают здесь не как средство или инструмент, а как объект исследования. Натуральный ряд
1,2,3,4, ...,9,10,11, ...,99,100,101, ...
- множество натуральных чисел - является важнейшей областью исследований, необычайно содержательной, важной и интересной.
Изучение натуральных чисел было начато в Древней Греции. Евклид и Эратосфен открыли свойства делимости чисел, доказали бесконечность множества простых чисел и нашли способы их построения. Задачи, связанные с решением неопределенных уравнений в целых числах, были предметом исследований Диофанта, а также ученых Древней Индии и Древнего Китая, стран Средней Азии.

Оглавление
Введение
Глава 1. О делимости чисел
1.1. Свойства делимости целых чисел
1.2. Наименьшее общее кратное и наибольший общий делитель
1.3. Алгоритм Евклида
1.4. Решение в целых числах линейных уравнений

Глава 2. Простые и составные числа
2.1. Простые числа. Решето Эратосфена. Бесконечность множества простых чисел
2.2. Основная теорема арифметики
2.3. Теоремы Чебышева
2.4. Дзета-функция Римана и свойства простых чисел
Задачи для самостоятельного решения
Глава 3. Арифметические функции
3.1. Мультипликативные функции и их свойства
3.2. Функция Мёбиуса и формулы обращения
3.3. Функция Эйлера
3.4. Сумма делителей и число делителей натурального числа
3.5. Оценки среднего значения арифметических функций
Задачи для самостоятельного решения
Глава 4. Числовые сравнения
4.1. Сравнения и их основные свойства
4.2. Классы вычетов. Кольцо классов вычетов по данному модулю
4.3. Полная и приведенная системы вычетов
4.4. Теорема Вильсона
4.5. Теоремы Эйлера и Ферма
4.6. Представление рациональных чисел бесконечными десятичными дробями
4.7. Проверка на простоту и построение больших простых чисел
4.8. Разложение целых чисел на множители и криптографические применения
Задачи для самостоятельного решения
Глава 5. Сравнения с одним неизвестным
5.1.Основные определения
5.2.Сравнения первой степени
5.3.Китайская теорема об остатках
5.4. Полиномиальные сравнения по простому модулю
5.5. Полиномиальные сравнения по составному модулюЗадачи для самостоятельного решения
Глава 6. Сравнения второй степени
6.1. Сравнения второй степени по простому модулю
6.2. Символ Лежандра и его свойства
6.3. Квадратичный закон взаимности
6.4.Символ Якоби и его свойства
6.5.Суммы двух и четырех квадратов
6.6. Представление нуля квадратичными формами от трех переменных
Задачи для самостоятельного решения
Глава 7. Первообразные корни и индексы
7.1. Показатель числа по заданному модулю
7.2. Существование первообразных корней по простому модулю
7.3. Построение первообразных корней по модулям рк и 2рк
7.4. Теорема об отсутствии первообразных корней по модулям, отличным от 2, 4, рк и 2рк
7.5. Индексы и их свойства
7.6. Дискретное логарифмирование
7.7. Двучленные сравнения
Задачи для самостоятельного решения
Глава 8. Цепные дроби
8.1. Теорема Дирихле о приближении действительных чисел рациональными
8.2. Конечные цепные дроби
8.3. Цепная дробь действительного числа
8.4. Наилучшие приближения
8.5. Эквивалентные числа
8.6. Квадратичные иррациональности и цепные дроби
8.7. Использование цепных дробей для решения некоторых диофантовых уравнений
8.8.Разложение числа е в цепную дробь
Задачи для самостоятельного решения
Глава 9. Алгебраические и трансцендентные числа
9.1.Поле алгебраических чисел
9.2. Приближения алгебраических чисел рациональными. Существование трансцендентных чисел
9.3. Иррациональность чисел ег и п
9.4. Трансцендентность числа е
9.5. Трансцендентность числа п
9.6.Невозможность квадратуры круга
Задачи для самостоятельного решения
Ответы и указания
Список литературы

Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Теория чисел - Нестеренко Ю.В. - fileskachat.com, быстрое и бесплатное скачивание.

Скачать djvu
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.

Теория чисел1

1. Основные понятия теории делимости

Î п р е д е л е н и е. Число a делится на ненулевое числоb , если найдется такое целое числоc , что выполняется равенствоa =b · c .

Обозначения:

1) a .b a делится наb ;

2) b | a b делит a;

3) a кратно (кратное)b ,b делительa .

Деление с остатком

Пусть даны два числа a èb ,a Z ,b N , ãäåZ множество целых чисел, аN множество натуральных чисел. Разделимa íàb с остаткомa =b · q +r , ãäår лежит в промежутке 0≤ r < b ,q неполное частное,r остаток. Например, 7 = 2· 3 + 1.

Теорема 1. Для любого целого a и натуральногоb представление

a = b · q+ r,0 ≤ r < b

единственно.

Ä î ê à ç à ò å ë ü ñ ò â î

1. Существование.

Рассмотрим бесконечное множество чисел {a − tb} , ãäåa ,b фиксированные числа,t любое число,t Z . Из него мы выберем наименьшее неотрицательное числоr =a − q · b . Докажем, чтоr лежит в пределах

0 ≤ r < b.

Пусть это число не принадлежит данному промежутку. Тогда оно больше или равно b . Построим новое числоr ′ =r−b =a−q·b−b =a−b (q +1).

Отсюда видно следующее:

1) r ′ {a − tb};

2) r ′ неотрицательное;

1 С.В.Федоренко. Сентябрь 2012. Курс лекций и задачи. Распространяется свободно. Курс читался в СПбГУАП (1997 1999; 2008 2011) и СПбГПУ (2002 2005).

3) r ′ < r .

Следовательно, не r , a r ′ является наименьшим неотрицательным числом из множества{a − tb} , тогда предположениеr ≥ b ложно.

Существование доказано.

2. Единственность.

Пусть существует другое представление a =bq ′ +r ′ , при условии, что 0≤ r ′ < b ;a ,b фиксированные числа,q Z . Т.е., мы можем разделить числоa íàb двумя способами, тогдаbq +r =bq ′ +r ′ . Перенося слагаемые ñq в одну сторону, а сr в другую, получаемb (q − q ′ ) =r ′ − r . Видно,

÷òî (r ′ − r ) .b . Каждый из остатков меньшеb è

(r′ − r) . b. |r′ − r| < b

Следовательно, r ′ − r = 0, а значитr ′ =r èq =q ′ . Итак, доказали,

что одно число можно разделить на другое единственным способом. Теорема доказана.

Теорема 2. Если a .b èb .c , òîa .c , ãäåb, c ≠ 0. Ä î ê à ç à ò å ë ü ñ ò â î

a = b · q. b= c · t

Следовательно, a =c · qt . По определению видно, чтоa .c .

Теорема 3. Пусть выполняется равенство a 1 +a 2 =b 1 +b 2 и числа a 1 , a 2 , b 1 .d , тогдаb 2 .d .

Ä î ê à ç à ò å ë ü ñ ò â î

a 1 =d · t 1 ,a 2 =d · t 2 ,b 1 =d · t 3 . Выразимb 2 из условия теоремыb 2 = a 1 +a 2 − b 1 =d (t 1 +t 2 − t 3 ). По определению делимости видно, чтоb 2 .d .

2. Наибольший общий делитель

Î п р е д е л е н и е. Если число c является делителем чиселa èb , то числоc называется общим делителем чиселa èb .

О п р е д е л е н и е. Наибольший из общих делителей чисел a èb называется наибольшим общим делителем (НОД) чиселa èb .

Обозначение: (a, b ) =d , ãäåa èb числа, аd наибольший общий

делитель этих чисел.

Рассмотрим пример для чисел 12 и 9. Выпишем все делители 12 и все делители 9. Для 12: 1, 2, 3, 4, 6 и 12; для 9: 1, 3 и 9; видно, что у них есть общие делители 1 и 3. Выберем наибольший из них это 3. Таким образом, (12, 9) = 3.

О п р е д е л е н и е. Два числа a èb называются взаимно простыми, если их НОД равен 1.

Пример. Т.к. (10,9)=1, то 10 и 9 взаимно простые числа.

Это определение можно распространить на любое количество чисел. Если (a, b, c, . . . ) = 1, то числаa, b, c, . . . взаимно простые. Например:

Î ï ð å ä å ë å í è å. (a 1 , a 2 , ...a n ) попарно взаимно простые числа, если НОД любой пары равен единице (a i , a j ) = 1,i ≠ j .

Например: 12,17,11 не только взаимно простые, но и попарно взаимно простые.

Теорема 1. Если a .b , òî (a, b ) =b .

Ä î ê à ç à ò å ë ü ñ ò â î

Число b не может делиться на число больше самого себя. Следовательно,b является НОДомa èb .

Теорема 2. Пусть имеется представление a =bq +r (r не обязательно остаток), тогда (a, b ) = (b, r ).

Ä î ê à ç à ò å ë ü ñ ò â î

1. Рассмотрим любой общий делитель a èb c . Åñëèa .c èb .c , òî

по теореме 1.3 r .c , ò.å.c является также общим делителемb èr . Любой общий делительa èb является общим делителемb èr .

2. Любой общий делитель b èr является делителемa . Значит, общие делителиa, b èb, r совпадают. Это верно и для НОД.

3. Алгоритм Евклида

Для любых чисел a èb с помощью алгоритма Евклида можно найти

Пусть a ,b N входные данные алгоритма, а (a, b ) =d N выходные.

		Bq 0	0 < r1 < b
		R 1 q 1	0 < r2 < r1
		R 2 q 2	0 < r3 < r2

	r i−2	R i−1 q i−1	0 < ri < ri− 1

	r n−2 = r n−1 q n−1 + r n		0 < rn < rn− 1
n + 1	r n−1 = r nq n

Шаг 1. Делим a íàb с остаткомa =bq 0 +r 1 , ãäå 0< r 1 < b . По теореме 2.2 (a, b ) = (b, r 1 ).

Шаг 2. Делим b íàr 1 с остаткомb =r 1 q 1 +r 2 , ãäå 0< r 2 < r 1 . Ïî теореме 2.2 (b, r 1 ) = (r 1 , r 2 ).

И так до тех пор, пока не разделится нацело. Из цепочки равенств

(a, b ) = (b, r 1 ) = (r 1 , r 2 ) = (r 2 , r 3 ) =... = (r n− 2 , r n− 1 ) = (r n− 1 , r n ) =r n

следует, что последний ненулевой остаток r n будет наибольшим общим делителемd =r n = (a, b ). Т.к. остатки убывают, то алгоритм завершится за конечное число шагов.

Теоремы, связанные с алгоритмом Евклида

Теорема 1. НОД двух чисел делится на любой общий делитель этих

Åñëè (a, b ) =d , òî (a c , c b ) =d c , ãäå c общий делительa èb .

Ä î ê à ç à ò å ë ü ñ ò â î

Â записи алгоритма Евклида a, b è âñår i разделим наc . Получим

запись алгоритма Евклида с входными данными a b

÷òî ÍÎÄ a		c èc . Из нее видно,
÷òî ÍÎÄ a
	è c	равен c .

Теорема 2. Если два числа разделить на их НОД, то получим взаимно простые числа (a d , d b ) = 1.

Ä î ê à ç à ò å ë ü ñ ò â î

Теорема 3. Если

Вместо c (из теоремы 1) подставимd .

(a, b ) = 1 , òîc .b .ac . b

Ä î ê à ç à ò å ë ü ñ ò â î

Для взаимно простых чисел a èb по теореме 7.1 существует представлениеax +by = 1. Умножая это равенство наc , имеемac ·x +byc =c ,

íî ac =bq ,bqx +byc =c ,b (qx +yc ) =c . Следовательно,c .b .

НОД нескольких чисел

(a1 , a2 , . . . , an ) = dn (a1 , a2 ) = d2

(d 2 , a 3 ) =d 3

(d n− 1 , a n ) =d n

4. Наименьшее общее кратное

Î п р е д е л е н и е. Общее кратное двух чисел a èb это такое число, которое делится на оба этих числаa èb .

Î п р е д е л е н и е. Наименьшее из общих кратных чисел a èb называется наименьшим общим кратным (НОК) чиселa èb .

Пусть M .a èM .b , тогдаM общее кратноеa èb . Наименьшее общее кратное чиселa èb обозначим как .

Теорема 1. НОК двух чисел равен отношению их произведения к

=(a, ab b ) .

Ä î ê à ç à ò å ë ü ñ ò â î

Обозначим некоторое общее кратное чисел a èb черезM , тогдаM .

a èM .b . Кроме того,d = (a, b ),a =a ′ d ,b =b ′ d , причем (a ′ , b ′ ) = 1. По определению делимостиM =a · k , ãäåk Z




					a′ dk				a′ k
					b′ d				b′

a ′ не делится наb ′ , т.к. они взаимно простые, следовательноk .b ′ ïî теореме 3.3

k = b′ · t=




M = a · k=
					(a, b)

вид любого общего кратного чисел a èb . Ïðèt = 1M является НОК чиселa èb .

НОК нескольких чисел

[ a1 , a2 , . . . , an ] = Mn [ a1 , a2 ] = M2

M 3 =M 4

Åñëè (a, b ) = 1, òî =ab . Ïðè (a i , a j ) = 1,i ≠ j ,M =a 1 a 2 · . . . · a n .

5. Простые и составные числа

Любое число делится на 1 и на само себя. Назовем эти делители тривиальными.

О п р е д е л е н и е. Число называется простым, если оно не имеет нетривиальных делителей. Число называется составным, если оно имеет нетривиальный делитель. Число 1 не является ни простым ни составным.

Теорема 1. Для любого натурального числа a и простого числаp

выполняется или (a, p ) = 1 èëèa .p .

Ä î ê à ç à ò å ë ü ñ ò â î

Ó простого числа p имеются два тривиальных делителя. Возможны

два варианта: a .p èëèa ̸ .p . Åñëèa ̸ .p , то НОДомa èp является 1. Следовательно, (a, p ) = 1.

Теорема 2. Наименьший отличный от единицы делитель целого, большего единицы, есть простое число.

Ä î ê à ç à ò å ë ü ñ ò â î

Åñëè a ≠ 1, òîa =p·q , ãäåp наименьший нетривиальный делитель. Предположим, чтоp составное число. Это означает, что существует

такое число s , ÷òîp .s , но тогдаa .s èp не является наименьшим делителем, что противоречит условию. Т.о.p простое число.

Теорема 3. Наименьший нетривиальный делитель составного числа не превосходит его корня.

Ä î ê à ç à ò å ë ü ñ ò â î

a = q · b, q ≤ b, q2 ≤ bq= a, q ≤ a.

Решето Эратосфена

Запишем множество натуральных чисел

1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 ,11 ,12 ,13 ,14 ,15 ,16 ,17 ,18 , . . .

Единица это особое число. С остальными числами поступаем следующим образом: берем число, объявляем его простым и вычеркиваем числа, кратные ему.

Например, 2 простое число, вычеркиваем числа, кратные двойке, следовательно, четных чисел не останется. Аналогично поступим и с тройкой. Нужно вычеркнуть 6, 9, 12, 15, 18, и т.д. Все оставшиеся числа являются простыми.

Теорема 4. Множество простых чисел бесконечно. Д о к а з а т е л ь с т в о

Пусть { 2, 3, 5, . . . , P } конечное множество простых чисел иN = 2· 3· 5·. . .·P +1.N не делится ни на одно из простых чисел, т.к. при делении в остатке получается 1. Но наименьший нетривиальный делительN по теореме 2 является простым числом̸ 2{, 3, 5, . . . , P } . Следовательно, простых чисел не конечное множество, а бесконечное.

6. Каноническая форма числа

Теорема 1 (Основная теорема арифметики). Любое число, отличное от 1, единственным способом представляется в виде произведения простых чисел.

Ä î ê à ç à ò å ë ü ñ ò â î

1. Существование.

Число n по теореме 5.2 имеет простой делительp 1

n n 1 = p 1 .

Аналогичные рассуждения справедливы и для числа n 1

n2 = n 1 ,p 2

ãäå p 2 простой делитель n 1 . И так будем продолжать до тех пор, пока не получимn i = 1.

2. Единственность.

Пусть число n имеет два разложения на простые числа

n = p1 · p2 · . . . · pl = q1 · q2 · . . . · qs .

Без ограничения общности примем l ≤ s . Если левая часть равенства делится наp 1 , то и правая тоже делится наp 1 . Значит, некотороеq i =p 1 . Пусть этоq 1 =p 1 . Разделим обе части равенства наp 1

Аналогично, примем q 2 = p 2 . Будем продолжать эту процедуру, пока выражение не примет вид

1 = ql +1 · . . . · qs .

Åñëè l < s , то произведение простых чисел не может быть равно 1. Следовательно, предположение о двух различных разложениях числаn невер-

íî. Åñëè s =l , òîp i =q i äëÿi и два разложения совпадают. Теорема доказана.

Любое число n N можно записать в канонической форме

n = p1 s 1 · . . . · pl s l ,

ãäå p i простые числа,s i N .

Каноническое представление позволяет выписать все делители числа и определить НОД и НОК.

Все делители c числаn имеют вид

c = p1 i 1 · p2 i 2 . . . pl i l ,ãäå ij .

Нахождение НОД и НОК

Пусть числа a èb представлены в виде

a = p1 s 1 · p2 s 2 · . . . · pl s l b= p1 t 1 · p2 t 2 · . . . · pl t l .

Это представление отличается от канонического тем, что некоторые s i è t i могут быть равны 0.

Тогда наибольший общий делитель a èb

(a, b) = p1 min (s 1 ,t 1 ) · p2 min (s 2 ,t 2 ) · . . . · pl min (s l ,t l ) ,

а наименьшее общее кратное:

[ a, b] = p1 max (s 1 ,t 1 ) · p2 max (s 2 ,t 2 ) · . . . · pl max (s l ,t l ) .

Отсюда также видно, что (a, b ) делится на любой общий делительa èb .

7. Линейные диофантовы уравнения с двумя неизвестными

Î п р е д е л е н и е. Линейным диофантовым уравнением с двумя неизвестными называется уравнение вида

ax + by= c,

где коэффициенты a, b, c и неизвестныеx, y целые числа, аa èb не равны нулю одновременно.

Теорема 1 (О линейном представлении НОД). Для любой пары чисел (a, b ) ((a, b ) ≠ (0, 0)) существуют такиеx, y Z , ÷òîax +by =(a, b ).

Ä î ê à ç à ò å ë ü ñ ò â î

Рассмотрим множество чисел {ax +by} и из него выберем минимальное положительное числоd =ax 0 +by 0 .

Докажем, что d является делителемb .

Пусть d не делительb , следовательно,b =d · q +r , ãäå 0< r < d ,

r = b − dq= b −(ax0 + by0 ) q= a(−x0 q) + b(1 − y0 q). Видно, что:

1) число r {ax +by} ;

2) r положительное;

3) r < d .

Но мы предположили, что d наименьшее положительное число из этого множества, следовательно, наше предположение, чтоr < d неверно, значитd делительb .

Аналогично можно доказать, что a .d .

Из всего этого следует, что d является общим делителемa èb .

a . (a, b)

Èòàê, b . (a, b ) d . (a, b ), íîd общий делительa èb , следова-тельно, d ÍÎÄ a è b .

Теорема 2. Уравнение ax +by =c имеет решение тогда и только тогда, когдаc делится на (a, b ).

Ä î ê à ç à ò å ë ü ñ ò â î

1. Пусть c . (a, b ), тогда по теореме 1ax +by = (a, b ). Умножим уравнение наc

(a,b)

a · (a, xc b ) + b ·(a, yc b ) = c.

Пара чисел (x 0 , y 0 ) будет решением исходного уравнения

{ x 0 = (a,b xc )y 0 = (a,b yc ).

2. Докажем, что если уравнение имеет решение, то c . (a, b ).

a . (a, b ) , следовательно,c тоже должно делиться на (a, b ).

b . (a, b)