ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Основные свойства сравнений.

Теория чисел

Теоретические сведения

Ниже рассматриваются N – множество натуральных чисел, Z – множество целых чисел. Множество целых чисел Z – счетное, состоит из элементов . На нем определены две алгебраические операции – сложение и умножение. Эти операции обладают следующими свойствами (для любых ):

1) ассоциативность: ; ;

коммутативность: ; ;

2) существует нейтральный элемент – 0 или 1 соответственно:

3) – закон дистрибутивности;

4) для каждого целого существует единственное противоположное целое такое, что .

Теорема 1.1 (о делении с остатком). Для любых целых чисел a и b, , существуют единственные целые числа q и , , такие, что .

В этом равенстве называют остатком, а – частным (неполным частным – при ) от деления на . При величины и называют делителями или множителями числа . Читатель со школьной скамьи умеет находить частное и остаток методом деления уголком.

Следствие. Пусть натуральное число, Для всякого целого числа и максимального целого с условием существуют единственные целые такие, что

Такое равенство записывают сокращенно или (если известно по контексту) и называют записью числа в -ичной позиционной системе счисления или системе счисления по основанию Кажется естественной привычная десятичная позиционная система записи целых чисел . В различных ситуациях более удобными оказываются другие основания. Например, во всех компьютерах на микроуровне вычисления проводятся в двоичной системе счисления. Для перехода к ней с десятичной применяют промежуточную 16-ричную систему счисления.

Лемма 1.1. Если в равенстве все слагаемые – целые числа и все, кроме может быть одного, делятся на целое , то и это исключенное слагаемое также делится на .

Определение 1.1.Если целые числа делятся на целое , то называют их общим делителем.

В дальнейшем речь идет только о положительных целых делителях.

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

Теорема 1.2. Если , то .

Теорема 1.2 позволила Евклиду (примерно 2300 лет тому назад) обосновать следующий факт.

Теорема 1.3. Наибольший общий делитель целых чисел a и b равен последнему отличному от нуля остатку цепочки равенств:

;

…………………

т. е. .

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

Пример 1.1. С помощью алгоритма Евклида найти НОД (72, 26).

Решение. В соответствии с теоремой 1.2 ; ; ; . Следовательно, НОД (72, 26) = 2.

Теорема 1.4. Если , то существуют такие целые и v, что выполняется следующее соотношение (соотношение Безу): .

Пример 1.2. Из примера 1.1 следует, что

Такой способ получения соотношения Безу для конкретных целых чисел называется расширенным алгоритмом Евклида. Он состоит из двух этапов: собственно алгоритма Евклида – прогонки вниз и прогонки вверх – и последовательного выражения остатков в каждом из шагов предыдущего этапа (с соответствующим приведением подобных на каждом шаге).

Определение 1.3. Натуральное число называется простым, если оно делится только на 1 и на себя.

Теорема 1.5. Всякое натуральное число либо является простым числом, либо имеет простой делитель.

Заметим, что из соотношения натуральных чисел, больших единицы, следует, что либо , либо принадлежит отрезку . Легко видеть, что наименьший натуральный делитель натурального числа является простым числом. Исторически первый метод проверки натурального числа на простоту, заключающийся в делении его на простые числа, не превосходящие , носит название «решета Эратосфена». К настоящему времени разработан достаточно большой цикл алгоритмов проверки числа на простоту.

Теорема 1.6 (теорема Евклида). Простых чисел бесконечно много.

Значение простых чисел в том, что они по теореме 1.5 являются составными кирпичиками всех натуральных чисел.

Определение 1.4. Целые числа и называются взаимно простыми, если .

Теорема 1.7 (критерий взаимной простоты целых чисел). Целые числа a и b взаимно просты тогда и только тогда, когда существуют такие целые u и v, что выполняется равенство .

Следствие. тогда и только тогда, когда

Важным в теории чисел и ее приложениях является следующее свойство взаимно простых целых чисел.

Лемма 1.2. Пусть произведение целых чисел делится на целое число и . Тогда делится на .

Теорема 1.8 (основная теорема арифметики). Всякое целое число однозначно раскладывается в произведение простых множителей

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

Пример 1.3. Приведем примеры канонических разложений целых чисел:
a) 196 = 2×98 = 2×2×49 = 2²×7²; б)

Теорема 1.9.Пусть – натуральное число, Для любых целых чисел и следующие условия равносильны:

1) и имеют одинаковые остатки от деления на

2) делится на т. е. для подходящего целого

3) для некоторого целого

Определение 1.5.Целые числа и называются сравнимыми по модулю если они удовлетворяют одному из условий теоремы 1.9. Этот факт обозначают формулой или и называют данную формулу сравнением.

Пример 1.4. –5 7(mod 4) 11(mod 4) 23(mod 4) 3(mod 4).

Пример 1.5. Если то всякое целое число сравнимо по модулю со своим остатком от деления на Это следует из определения 1.5 и второго условия теоремы 1.9. Ведь делится на

Основные свойства сравнений.

1. Пусть Тогда для всякого целого числа то есть к обеим частям сравнения можно добавить (или вычесть из обеих частей) одно и то же число.

2. Сравнения можно почленно складывать и вычитать: если , то

3. Сравнения можно почленно перемножать: если то

4.Сравнения можно почленно возводить в любую натуральную степень: если то

5. Если в сравнении числа имеют общий множитель то на него сравнение можно сократить .

6. Сравнение можно сократить на общий множитель, взаимно простой с модулем: если , , то из сравнения следует сравнимость и по модулю .

7. Сравнение можно умножить на любой целый множитель: если то для всякого целого числа

8. Рефлексивность: для любого целого и всякого натурального

9. Симметричность: если то

10. Транзитивность: если и то

Теорема 1.10 (малая теорема Ферма). Пусть – простое число и целое число не делится на . Тогда .

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

Пример 1.6. Найдем остаток от деления на 31.

Решение. 39 не делится на простое число 31. Поэтому Следовательно, Далее Поэтому в силу свойства 4 сравнений Двоичная запись 29 = 11101. Следовательно, для любого натурального величина
Далее Поэтому Тогда Следовательно,

Таким образом, остаток от деления на 31 равен 4.