Составители:
Рубрика:
7
Так, например, если имеем сравнение 1/3 ≡ 16/15 mod 11, то так как
(15, 11)=1, т. е. числа 15 и 11 взаимно просты, то обе части сравнения
можно умножить на 15 и получим эквивалентное сравнение:
5 ≡ 16 mod 11.
1.3. Решение сравнений
Из приведенных правил эквивалентных преобразований сравнений
следуют общие приемы решения сравнений. Пусть требуется решить
сравнение
27 –13* 5 ≡10*X mod 7
относительно неизвестного X. Можно показать, что если в сравнении
имеется арифметическое выражение, то любой член его можно заме-
нить остатком от деления на модуль (в общем случае – на любое сравни-
мое с ним число). Поскольку 27 ≡ 6 mod 7, 13 ≡ –1 mod 7 и 10 ≡ 3 mod 7, то
исходное сравнение можно представить в виде
6 – (–1)*5 ≡ 3*X mod 7.
Далее вычисляем 11 ≡ 3*X mod 7, 18 ≡ 3*X mod 7, 6 ≡ X mod 7. Откуда
одно из решений сравнения X=6. Общее решение X = 6 + t*7.
Упражнения
Найти общие решения следующих сравнений:
а) 8 ≡ 3X mod 11;
б) 25 ≡ 15 X mod 17;
в) 3( 24–18)/5 ≡ 7X mod 19;
г) 8
125
– 6
29
≡ 5X mod 7;
д) (18
24
+ 20
83
) / (21
6
) ≡ 23
3
X mod 19;
е) 10
112
+12
58
≡ 2X mod11.
1.4. Наименьшее общее кратное и
наибольший общий делитель
Пусть имеется n целых чисел: a
1
, a
2
, a
3
, …, a
n
. Общим кратным
этих чисел называется целое число, которое делится нацело на каждое
из этих чисел. Наименьшее из этих общих кратных называется наи-
меньшим общим кратным чисел a
1
, a
2
, a
3
, …, a
n
и обозначается НОК
(a
1
, a
2
, a
3
, …, a
n
) или [a
1
, a
2
, a
3
, …, a
n
].
Пусть имеется n целых чисел a
1
, a
2
, a
3
, …, a
n
. Общим делителем этих
чисел называется число, которое нацело делит каждое их этих чисел.
Среди делителей имеется наибольшее число, которое называется наи-
большим общим делителем НОД (a
1
, a
2
, a
3
, …, a
n
) или (a
1
, a
2
, a
3
, …, a
n
).
Страницы
- « первая
- ‹ предыдущая
- …
- 5
- 6
- 7
- 8
- 9
- …
- следующая ›
- последняя »
