Rozwiazania kongruencji

[MenosGrandes]

\(\displaystyle{ 21x \equiv 13 \pmod{64}}\)
Mam do rozwiazania taka kongruencje i nie wiem jak sie zabrac.. zeby nie liczyc wszystkiego po kolei

[irena_1]

Można tak:
\(\displaystyle{ 21x\equiv13\ (mod\ 64)\\x=64a+13\\21x=63a+a+13\\x=3a+\frac{a+13}{21}\\\frac{a+13}{21}\in C\\a=8\\x=24+1=25\\x\equiv\ 25\ (mod\ 64)}\)

[MenosGrandes]

jeszcze jedno bo próbuje tą samą metodą ale coś nie wychodzi
\(\displaystyle{ 27x \equiv 72 \pmod{900}
NWD(900,27)=9}\)
wiec można podzielić przez 9 co daje
\(\displaystyle{ 3x \equiv 8 \pmod{100}}\)
ale dalej robie tak
\(\displaystyle{ 3x=100j + 8}\)
\(\displaystyle{ 3x=99j + j + 8}\)
dzielimy na 3 co daje
\(\displaystyle{ x= 33j + [(j+8)/3]}\)
i co dalej?

[irena_1]

\(\displaystyle{ x=33j+\frac{j+8}{3}\\j=1\\x=33+3=36\\36\equiv\ 36\ (mod\ 100)}\)

Szukasz możliwie najmniejszej liczby całkowitej (naturalnej) j, żeby licznik dzielił się przez mianownik bez reszty