Условие:
Решить систему линейных сравнений.
a) x = 3 mod 4
x = 2 mod 5
x = 0 mod 7
b) x = 5 mod 7
x = 7 mod 8
c) x = 1 mod 3
x = 1 mod 2
x = 3 mod 7
x = 1 mod 5
Решение:
Решим каждую из систем линейных сравнений по отдельности.
a) Система:
- x ≡ 3 (mod 4)
- x ≡ 2 (mod 5)
- x ≡ 0 (mod 7)
Сначала решим первые два уравнения:
- x = 4k + 3 для некоторого целого k. Подставим это в второе уравнение: 4k + 3 ≡ 2 (mod 5) 4k ≡ -1 (mod 5) 4k ≡ 4 (mod 5) (так как -1 ≡ 4 (mod 5)) Умножим обе стороны на 4 (обратное к 4 по модулю 5): k ≡ 1 (mod 5) k = 5m + 1 для некоторого целого m.
Теперь подставим k обратно в выражение для x: x = 4(5m + 1) + 3 = 20m + 4 + 3 = 20m + 7.
Теперь подставим это в третье уравнение: 20m + 7 ≡ 0 (mod 7) 20m ≡ -7 (mod 7) 20m ≡ 0 (mod 7) (так...