forum.zadania.info

Rozwiąż kongruencje liniową
1)15x≡7(mod 24)
2)15x≡10(mod 25)

Prosiłbym o krok po kroku jak to się robi , z góry dziękuje

liniowa kongruencja \(ax\equiv b \pmod n\) ma rozwiazanie wtedy i tylko wtedy gdy \(d:=(a,n)|b\)

zatem 1) nie ma rozwiazania

w drugim \(d=(15,25)=5|10\) zatem mamy rozwiazanie, oznaczmy je przez \(x_{0}\). Poniewaz, \(d=5\) bedziemy miec w sumie 5 rozwiazan tej kongruencji, beda one postaci \(\{x_{0}+k\frac{n}{d}|k= 0,1,2,3,4\}\)

Standartowo przez rownanie Diofantyczne (w ktorym uzywa sie algorytmu Euklidesa)

zapiszmy kongruencje, jako rownanie \(15x-25y=10\)
uzywajac algorytmu Euklidesa mamy \(5=\underbrace{2}_{x_{0}}(15)-25\) ale my potrzebujemy tego samego dla \(10\) wiec mamy \(10=\underbrace{4}_{x_{0}}(15)-2(25)\)

a z tego widac np ze \(15\cdot 4=60\equiv 10 \pmod {25}\)

wiec wszystkie rozwiazania kongruencji naleza do zbioru \(\{4,9,14,19,24\}\)