Сравнение 1-ой степени с одним неизвестным

Любое сравнение 1 степени с 1 неизвестным можно привести к виду:

ах b (mod m) (I)

a 0 (mod m)

Исследуем, в каких случаях сравнение будет иметь единственное решение, несколько решений или не иметь решений вообще.

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

Доказательство: сравнение (1) имеет несколько решений, сколько вычетов полной системы вычетов ему удовлетворяет по mod m,

т.к. (a,m)=1 - также полная система вычетов по этому модулю при одном и только одном значении х , взятым из полной системы вычетов, число а х будет сравнимо с b по mod m

а х (mod m) сравнение (1) имеет единственное решение: x (mod m)

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

Доказательство:

пусть x (mod m) – решение сравнений (1) (mod m) ac-b mt(…) (t z) ac-mt=b (a,m)=d b d

d

Полученное противоречие доказывает теорему.

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

Доказательство: т.к. a, b и m d, положим a=a d, b=b d, m=m d сравнение a x b (… m ) (2)

Где (a , m )=1, а значит (2) имеет единственное решение по мод m :

х х (… m ) или х = х + m t (любое t z), где х - наименьший неотрицательный вычет по мод. m

или

…… х -2 m , х - m , х , х + m , х +2 m ….. х +(d-1) m … х +d m (3)

Все эти вычеты и только они удовлетворяют сравнение (2), а, значит и равносильны ему сравнение (1). По модулю m = все эти числа принадлежат одному классу; по мод. m= m d они будут принадлежать различным классам, вычетам которых являются: х , х - m , х +2 m ….. х +(d-1) m сравнение (1) имеет d различных решений по мод. m:

х х (… m), х х , х + m (… m),

х х +2 m (… m),…., х х +(d-1) m (… m), где х частное решение. Литература:

Контрольные вопросы:

1. Какие числа называются сравнимыми по модулю.

2. Какие свойства сравнений вы знаете?

3. Как определяется функция Эйлера? Дайте формулу для её нахождения.

4. Сформулируйте теоремы Эйлера и Ферма.

5. Что называется полной и приведённой системами вычетов.

6. Как определяется сравнение 1 степени с одним неизвестным?