Сравнения первой степени
Рассмотрим сравнения первой степени вида
Как решать такое сравнение? Рассмотрим два случая.
Случай 1.Пусть а и m взаимно просты. Тогда несократимая дробь m/a сама просится разложиться в цепную дробь:
Эта цепная дробь, разумеется, конечна, так как m/a — рациональное число. Рассмотрим две ее последние подходящие дроби:
Вспоминаем важное свойство числителей и знаменателей подходящих дробей: mQn-1 -aP n-1 =(-1) n . Далее (слагаемое mQ n-1 , кратное m , можно выкинуть из левой части
и единственное решение исходного сравнения есть:
x ≡ (-1) n-1 P n-1 b(mod m)
Пример.Решить сравнение 111x ≡ 75(mod 322).
Решение.(111, 322)=1. Включаем алгоритм Евклида:
(В равенствах подчеркнуты неполные частные.) Значит, n=4 , а соответствующая цепная
Посчитаем числители подходящих дробей, составив для этого стандартную таблицу:
Числитель предпоследней подходящей дроби равен 29, следовательно, готовая формула
Случай 2.Пусть (a,m)=d . В этом случае, для разрешимости сравнения ax ≡ b(mod m)
необходимо, чтобы d делило b , иначе сравнение вообще выполняться не может.
Действительно, ax ≡ b(mod m) бывает тогда, и только тогда, когда ax- b делится на m нацело, т.е.
ax- b=t · m , t ∈ Z, откуда b=ax- t ⋅ m , а правая часть последнего равенства кратна d .
где уже а1 и m1 взаимно просты. Согласно случаю 1 этого пункта, такое сравнение имеет единственное решение x0 :
По исходному модулю m , числа (*) образуют столько решений исходного сравнения, сколько чисел вида (*) содержится в полной системе вычетов: 0,1,2. m-2, m-1 . Очевидно, что из чисел x = x0 + t⋅m в полную систему наименьших неотрицательных вычетов попадают только x0 , x0 + m1 , x0 +2m1 , . x0 +(d-1)m1 , т.е. всего d чисел. Значит у исходного сравнения имеется d решений.
Подведем итог рассмотренных случаев в виде следующей теоремы
Теорема 1.Пусть (a,m)=d . Если b не делится на d , сравнение ax ≡ b(mod m) не имеет решений. Если b кратно d , сравнение ax ≡ b(mod m) имеет d штук решений.
Пример.Решить сравнение 111x ≡ 75(mod 321) .
Решение.(111,321)=3 , поэтому поделим сравнение и его модуль на 3:
Включаем алгоритм Евклида (как обычно, подчеркнуты неполные частные):
Имеем n=4 и цепная дробь такова:
Таблица для нахождения числителей подходящих дробей:
Три решения исходного сравнения:
x ≡ 99(mod 321), x ≡ 206(mod 321), x ≡ 313(mod 321) ,
и других решений нет.
Теорема 2.Пусть m>1, (a,m)=1 Тогда сравнение ax ≡ b(mod m) имеет решение: x ≡ ba ϕ (m)-1 (mod m) .
Пример.Решить сравнение 7x ≡ 3(mod 10) . Вычисляем:
ϕ (10)=4; x ≡ 3 ⋅ 7 4-1 (mod 10) ≡ 1029(mod 10) ≡ 9(mod 10) .
Видно, что этот способ решения сравнений хорош (в смысле минимума интеллектуальных затрат на его осуществление), но может потребовать возведения числа а в довольно большую степень, что довольно трудоемко. Для того, чтобы как следует это прочувствовать, возведите самостоятельно число 24789 в степень 46728.
Теорема 3.Пусть р – простое число, 0. Тогда сравнение ax ≡ b(mod p) имеет решение:
где 
– биномиальный коэффициент.
Пример.Решить сравнение 7x ≡ 2(mod 11) . Вычисляем:
Лемма 1 (Китайская теорема об остатках).Пусть дана простейшая система сравнений первой степени:
Пример.Однажды средний товарищ подошел к умному товарищу и попросил его найти число, которое при делении на 4 дает в остатке 1, при делении на 5 дает в остатке 3, а при делении на 7 дает в остатке 2. Сам средний товарищ искал такое число уже две недели. Умный товарищ тут же составил систему:
которую начал решать, пользуясь леммой 1. Вот его решение:
Далее он нашел:
т.е. M 1 ∇ =3, M 2 ∇ =2, M 3 ∇ =6. Значит x 0 =35 ⋅ 3 ⋅ 1+28 ⋅ 2 ⋅ 3+20 ⋅ 6 ⋅ 2=513. После этого, по лемме 1, умный товарищ сразу получил ответ:
x ≡ 513(mod 140) ≡ 93(mod 140),
т.е. наименьшее положительное число, которое две недели искал средний товарищ, равно 93. Так умный товарищ в очередной раз помог среднему товарищу.
Лемма 2.Если b 1 ,b 2 . b k пробегают полные системы вычетов по модулям m 1 ,m 2 . m k соответственно, то x 0 пробегает полную систему вычетов по модулю m 1 m 2 . m k .
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
Источник
Сравнения с одним неизвестным
Если a0 не делится на m, то n называется степенью сравнения.
Решить сравнение – значит найти все x, ему удовлетворяющие. Два сравнения, которые удовлетворяют одни и те же значения x, называются равносильными.
Если сравнению (*) удовлетворяет какое-то x=x1, то ему же будут удовлетворять все числа, сравнимые с x1 по модулю m: x ≡ x1(mod m). Весь класс чисел, сравнимых с x1 по модулю m считается за одно решение. Таким образом, (*) будет иметь столько решений, сколько вычетов из полной системы ему удовлетворяет.
x 5 +x+1=0 (mod 7) удовлетворяют x ≡ 2 (mod 7) и x ≡ 4 (mod 7) – 2 решения.
Сравнения первой степени.
Любое сравнение первой степени можно привести к виду ax ≡ b (mod m). Рассмотрим случай, когда (a, m)=1. Согласно утверждению 2 пункта 3 §3, когда x пробегает полную систему вычетов по модулю m, ax тоже пробегает полную систему вычетов по по модулю m. Следовательно, при одном и только одном значении x из полной системы вычетов, ax будет сравнимо с b, т.е. при (a, m)=1 сравнение имеет ровно 1 решение.
Нахождение решения: Так как (a, m) = 1, то по теореме обратимости 
a -1 , и тогда исходному сравнению равносильно x ≡ a -1 ∙b (mod m).
Пусть теперь (a,m)=d>1. Для того, чтобы сравнение имело решение, необходимо, чтобы d\b, иначе сравнение невозможно (свойство сравнений №14).
Если же a=a1d, b=b1d, m=m1d , то исходному сравнению равносильно a1x≡b1(mod m1), причем (a1,m1)=1 
сравнение имеет 1 решение по mod m1: x≡x1(mod m1), или d решений по модулю m:
Решить сравнение 6x = 5 (mod 35).
Вычислим НОД(6, 35), пользуясь алгоритмом Евклида:
5 = 5∙1+0 НОД(6, 35)=1.
Вычислим обратный элемент к 6 по модулю 35, пользуясь расширенным алгоритмом Евклида:
1 = 6–5=6–(35–6∙5)=6–35+6∙5= 6∙6–35
Домножим правую и левую части исходного сравнения на 6:
6 -1 ∙6x≡6 -1 ∙5(mod 35)
Ответ: x ≡ 30 (mod 35)
Решить сравнение 18x = 6 (mod 24).
Вычислим НОД(18, 24), пользуясь алгоритмом Евклида:
18 = 2∙6+0 НОД(18, 24)=6.
Правая и левая части сравнения, а также модуль, делятся на 6. Разделим исходное сравнение на 6 и получим равносильное сравнение:
Вычислим НОД(3, 4), пользуясь алгоритмом Евклида:
3 = 3∙1 + 0 НОД(3, 4)=1.
Вычислим обратный элемент к 3 по модулю 4, пользуясь расширенным алгоритмом Евклида:
1=4–3 3 -1 = –1(mod 4).
Домножим правую и левую части сравнения (*) на –1:
3 -1 ∙3x=–1∙1 (mod 4) x≡ –1 (mod 4).
Или, переводя решение в систему наименьших неотрицательных вычетов, x≡ 3 (mod 4).
Ответ: получили 6 решений по модулю 24:
Система сравнений первой степени. Китайская теорема об остатках.
Рассмотрим систему сравнений
*
От системы сравнений вида aix ≡ bi (mod mi) можно перейти к данной способом, указанным в п.1.
Источник
Решение сравнений первой степени
Сравнение первой степени с одним неизвестным имеет вид:
f(x) 
0 (mod m); f(х) = ах + аn. (1)
Решить сравнение – значит найти все значения х, ему удовлетворяющие. Два сравнения, которым удовлетворяют одни и те же значения х, называются равносильными.
Если сравнению (1) удовлетворяет какое-либо x = x1, то (согласно 49) тому же сравнению будут удовлетворять и все числа, сравнимые с x1, по модулю m: x x1 (mod m). Весь этот класс чисел считается за одно решение. При таком соглашении можно сделать следующий вывод.
66.Сравнение (1) будет иметь столько решений, сколько вычетов полной системы ему удовлетворяет.
6x – 4 0 (mod 8)
среди чисел 0, 1,2, 3, 4, 5, 6, 7 полной системы вычетов по модулю 8 удовлетворяют два числа: х = 2 и х = 6. Поэтому указанное сравнение имеет два решения:
x 2 (mod 8), х 6 (mod 8).
Сравнение первой степени перенесением свободного члена (с обратным знаком) в правую часть можно привести к виду
ax b (mod m). (2)
Рассмотрим сравнение, удовлетворяющее условию (а, m) = 1.
Согласно 66 наше сравнение имеет столько решений, сколько вычетов полной системы ему удовлетворяет. Но когда x пробегает полную систему вычетов по модулю т, то ах пробегает полную систему вычетов (из 60). Следовательно, при одном и только одном значении х, взятом из полной системы, ах будет сравнимо с b. Итак,
67. При (а, m) = 1 сравнение ax b (mod m) имеет одно решение.
Пусть теперь (a, m) = d > 1. Тогда, чтобы сравнение (2) имело решения, необходимо (из 55), чтобы b делилось на d, иначе сравнение (2) невозможно ни при каком целом х. Предполагая, поэтому b кратным d, положим a = a1d, b = b1d, m = m1d. Тогда сравнение (2) будет равносильно такому (по сокращении на d): a1x b1 (mod m), в котором уже (а1, m1) = 1, и потому оно будет иметь одно решение по модулю m1. Пусть х1 – наименьший неотрицательный вычет этого решения по модулю m1, тогда все числа х, образующие это решение, найдутся в виде
x x1(mod m1). (3)
По модулю же mчисла (3) образуют не одно решение, а больше, именно столько решений, сколько чисел (3) найдется в ряде 0, 1, 2, . m – 1 наименьших неотрицательных вычетов по модулю m. Но сюда попадут следующие числа (3):
т.е. всего d чисел (3); следовательно, сравнение (2) имеет d решений.
68. Пусть (a, m) = d. Сравнение ax b (mod m) невозможно, если b не делится на d. При b, кратном d, сравнение имеет d решений..
69.Способ решения сравнения первой степени, основанный на теории непрерывных дробей:
Разлагая в непрерывную дробь отношение m:а,
и рассматривая две последние подходящие дроби:
согласно свойствам непрерывных дробей (согласно 30) имеем
Итак, сравнение имеет решение
для разыскания, которого достаточно вычислить Pn – 1 согласно способу, указанному в 30.
Пример. Решим сравнение
111x = 75 (mod 321). (4)
Здесь (111, 321) = 3, причем 75 кратно 3. Поэтому сравнение имеет три решения.
Деля обе части сравнения и модуль на 3, получим сравнение
37x = 25 (mod 107), (5)
которое нам следует сначала решить. Имеем
Значит, в данном случае n = 4, Pn–1 = 26, b = 25, и мы имеем решение сравнения (5) в виде
x –26 ∙ 25 99 (mod 107).
Отсюда решения сравнения (4) представляются так:
х 99; 99 + 107; 99 + 2 ∙ 107 (mod 321),
х º99; 206; 313 (mod 321).
Вычисление обратного элемента по заданному модулю
70.Если целые числа a и n взаимно просты, то существует число a′, удовлетворяющее сравнению a ∙ a′ ≡ 1(mod n). Число a′ называется мультипликативным обратным к a по модулю n и для него используется обозначение a — 1 (mod n).
Вычисление обратных величин по некоторому модулю может быть выполнено решением сравнения первой степени с одним неизвестным, в котором за x принимается число a′.
Чтобы найти решение сравнения
можно воспользоваться алгоритмом Евклида (69) или теоремой Ферма-Эйлера, которая утверждает, что если (a,m) = 1, то
Группы и их свойства
Группы – один из таксономических классов, используемых при классификации математических структур с общими характерными свойствами. Группы имеют две составляющие: множество (G) и операции ( 
), определенные на этом множестве.
Понятия множества, элемента и принадлежности являются базисными неопределяемыми понятиями современной математики. Любое множество определяется элементами, входящими в него (которые, в свою очередь, тоже могут быть множествами). Таким образом, мы говорим, что множество определено или задано, если для любого элемента мы можем сказать, принадлежит ли он этому множеству или нет.
Для двух множеств A, B записи B 
A, B 
A, B ∩ A, B 
A, B \ A, A × B означают соответственно, что B является подмножеством множества A (т.е. любой элемент из B содержится также и в A, например, множество натуральных чисел содержится в множестве действительных чисел; кроме того, всегда A A), B является собственным подмножеством множества A (т.е. B A и B ≠ A), пересечение множеств B и A (т.е. все такие элементы, которые лежат одновременно и в A, и в B, например пересечение целых чисел и положительных действительных чисел есть множество натуральных чисел), объединение множеств B и A (т.е. множество, состоящее из элементов, которые лежат либо в A, либо в B), разность множеств B и A (т.е. множество элементов, которые лежат в B, но не лежат в A), декартово произведение множеств A и B (т.е. множество пар вида (a, b), где a 
A, b B). Через |A| всегда обозначается мощность множества A, т.е. количество элементов в множестве A.
Операция – это правило, согласно которому любым двум элементам множества G (a и b) ставится в соответствие третий элемент из G: а b.
Множество элементов G с операцией называется группой, если удовлетворяются следующие условия:
1. Ассоциативность: для любых элементов a, b, c 
G выполняется равенство a (b c) = (a b) c.
2. Единичный элемент: существует такой элемент е G, что при любом a G выполняются равенства a e = e a = a.
3. Обратный элемент: для каждого a G найдется элемент a′ G, удовлетворяющий соотношению a a′ = a′ a = e.
Элемент e из G называется нейтральным элементом группы, а элемент a′ – обратным элементом к a. Обратный элемент обозначается a′ = a — 1 .
Группы, в которых операция коммутативна, то есть для любой пары a, b G выполняется равенство a b = b a, называются коммутативными группами, или абелевыми группами.
Число элементов в группе называется ее порядком.
С точки зрения решения уравнений основное свойство группы в том, что в ней однозначно разрешены уравнения вида:
a x = b
y a = b,
при любых a, b G.
1. Целые, рациональные, действительные, комплексные числа по сложению.
2. Ненулевые рациональные, действительные, комплексные числа по умножению.
Источник
