Полная и приведенная системы вычетов. Теоремы Эйлера и Ферма

 

Полная система вычетов. Приведённая система вычетов. Наиболее употребительные системы вычетов: наименьшая положительная, наименьшая неотрицательная, абсолютно наименьшая и т.д.

 

Теорема 1. Свойства полной и приведённой система вычетов.

 

1°.Критерий полной системы вычетов. Любая совокупность из m целых чисел, попарно не сравнимых по модулю m, образует полную систему вычетов по модулю m.

2°. Если числа x ₁, x ₂,..., x_m – полная система вычетов по модулю m, (a, m) = 1, b – произвольное целое число, то числа ax ₁+ b, ax ₂+ b,..., ax_m + b также составляют полную систему вычетов по модулю m.

3°. Критерий Приведённой системы вычетов. Любая совокупность, состоящая из j(m) целых чисел, попарно не сравнимых по модулю m и взаимно простых с модулем, образует приведённую систему вычетов по модулю m.

4°. Если числа x ₁, x ₂,..., x _{j( m )} – приведённая система вычетов по модулю m, (a, m) = 1, то числа ax ₁, ax ₂,..., a x _{j( m )} также составляют приведённую систему вычетов по модулю m.

 

Теорема 2. Теорема Эйлера.

 

Если числа a и m взаимно простые, то a ^{j( m )} º 1(mod m).

 

Cледствие.

 

1°. Теорема Ферма. Если p – простое число и a не делится на p, то a^{p –1} º 1(mod p).

2°. Обобщенная теорема Ферма. Если p – простое число, то a^p º a (mod p) для любых a Î Z.

 

§ 4. Решение сравнений с переменной

 

Решение сравнений. Равносильность. Степень сравнения.

Теорема. Свойства решений сравнений.

 

1°.Решениями сравнений являются целые классы вычетов.

2°. (" k)(a_k º b_k (mod m))Ù k = Þ сравнения º 0 (mod m) и º 0 (mod m) равносильны.

3°. Если обе части сравнения умножить на число, взаимно простое с модулем, то получится сравнение, равносильное исходному.

4°. Всякое сравнение по простому модулю p равносильно сравнению, степень которого не превосходит p –1.

5°. Сравнение º 0 (mod p), где p – простое число, имеет не более n различных решений.

6°. Теорема Вильсона. (n –1)! º –1 (mod n) Û n простое число.

 

§ 5. Решение сравнений первой степени

 

ax º b (mod m).

 

Теорема. 1°. Если (a, m) = 1, то сравнение имеет решение, причем единственное.

2°. Если (a, m) = d и b не делится на d, то сравнение не имеет решений.

3°. Если (a, m) = d и b делится на d, то сравнение имеет d различных решений, которые составляют один класс вычетов по модулю .

 

Способы решения сравнений ax º b (mod m) в случае, когда (a, m) = 1:

1) подбор (перебор элементов полной системы вычетов);

2) использование теоремы Эйлера;

3) использование алгоритма Евклида;

4) вариация коэффициентов (использование свойства 2° полной системы вычетов из Теоремы 2.2);

 

§ 6. Неопределенные уравнения первой степени

 

ax + by = c.

 

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

В случае (a, b) = 1 все решения уравнения задаются формулами

t Î Z, где x ₀ является каким-либо решением сравнения

ax º c (mod b), y ₀ = .

 

Диофантовы уравнения.

 

ГЛАВА 10. Комплексные числа

Определение системы комплексных чисел. Существование системы комплексных чисел

 

Определение системы комплексных чисел.

 

Теорема. Система комплексных чисел существует.

Модель: R ² с операциями

(a, b)+(c, d) = (a + c, b + d), (a, b)×(c, d) = (ac – bd, bc + ad),

i = (0, 1) и отождествлением а = (а, 0).

 

Алгебраическая форма комплексного числа

 

Представление комплексного числа в виде z = a + bi, где a, b Î R, i ² = –1. Единственность такого представления. Re z, Im z.

Правила выполнения арифметических действий над комплексными числами в алгебраической форме.

Арифметическое n -мерное векторное пространство C ⁿ. Системы линейных уравнений, матрицы и определители над C.

Извлечение квадратных корней из комплексных чисел в алгебраической форме.

 

⇐ Предыдущая45678910111213Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: