kongruencje Prosty: Jak rozwiązać kongruencje 3x≡4mod7 ? NWD(3,7) = 1, a jak wyznaczyć e. odwrotny etc ... ?

Adamm: 7=2*3+1 ⇒ (−2)*3≡1 (mod 7) ⇒ 4*(−2)*3≡4 (mod 7) i stąd x≡−8 (mod 7)

Prosty: okej dzięki wielkie ! czyli rozumiem ze wyznaczam element odwrotny = −2 i mnoże przez niego równanie obustronnie ? a jeszcze chciałbym zapytać ze jesli NWD > 1 to wiem ze dziele strony równania ale dlaczego wtedy też dziele wartość modulo ?

Prosty: na przykład równanie 9x ≡ 12 mod21

Adamm: Jeśli chcesz się tego dowiedzieć, najlepiej skorzystać z definicji 9x ≡ 12 (mod 21) oznacza tyle co, istnieje taka liczba całkowita k że 9x=12+21k, czyli 3x=4+7k, czyli 3x ≡ 4 (mod 7)

Prosty: dzieki jeszcze raz

Prosty: ma ktoś pomysł jak rozwiązać taki układ kongruencji podstawiając je : x ≡ 5 mod6 x ≡ 6 mod7 x ≡12 mod 13

Adamm: Co znaczy "podstawiając" ?

Prosty: ze z pierwszego równania wiem ze x = 5 + 6n i do drugiego 5 + 6n ≡ 6 mod7 i teraz nwm jak wyznaczyć n

Prosty: nie chce używać chińskiego tw o resztach

Pytający: n,m,k,a,b∊ℤ

	1+7m		1+m
x=5+6n=6+7m ⇒ n=		=m+		∊ℤ ⇒ m=5+6a ⇒
	6		6

⇒ x=6+7m=6+7(5+6a)=41+42a x=41+42a=12+13k ⇒

	−29+13k		13−42+13k		13(k+1)
⇒ a=		=		=		−1∊ℤ ⇒ k+1=42b ⇒
	42		42		42

⇒ x=12+13k=12+13(42b−1)=546b−1

Prosty: dziękuje