Kongruencje Przemysław: Znajdź najmniejsze nieujemne rozwiązania następujących układów kongruencji:

⎧	7x≡6(mod 9)
⎨
⎩	9x≡12(mod 21)

⇔

⎧	63x≡0(mod 9)
⎨
⎩	63x≡0(mod 21)

63x=21*9k x=3k Ale x=3 nie spełnia tego układu. Mogę wziąć k=2 i znowu podstawiać, ale to trochę głupio, bo nie wiadomo, dla którego k dostanę to rozwiązanie. Nie wiem, gdzie robię błąd

Saizou : 7x≡6 mod9 /4⇒28x≡24 mod9⇒x≡8 mod9⇒x=8+9k 9x≡12 mod21 dokończ....

Przemysław: "28x≡24 mod9⇒x≡8 mod9" Skąd to przejście?

Saizou : pomnożyłem obustronnie przez 4 7x≡6 mod9 (mnożąc *4) 28x ≡ 24 mod9 Kongruencje można bezkarnie dodawać, mnożyć i odejmować, gorzej z dzieleniem

Przemysław: Rozumiem, skąd jest 28x ≡ 24 mod9. Ale skąd to: x≡8 mod9?

Saizou : 28x≡24 mod9 (27+1)x≡18+6 mod9 (zabierając wielokrotności 9) x≡6 mod9

Przemysław: czyli tak jakby: 27x≡0(mod 9) x≡24−0 (mod 9)≡6(mod 9)... mamy: x=8+9k czyli: 72+81k≡12 mod21 81k≡60(mod 21)≡18(mod 21) 27k≡6(mod 7) (21+6)k≡6(mod 7) 6k≡6(mod 7) k=7l najmniej dla l=0 k=0 x=8 coś znowu źle

Saizou : masz bład 81≡18 mod21 −60≡−63+3≡3 mod21

Saizou : ja lecę z forum, jutro sprawdzę

Przemysław: 81k≡3(mod 21) 27k≡1(mod 7) 6k≡1(mod 7)

Przemysław: Dobra, dzięki za pomoc, w każdym razie

ZKS: 7x ≡ 6 (mod 9) x ≡ 6 (mod 9) x = 6 + 9k 54 + 81k ≡ 12 (mod 21) 81k ≡ −42 (mod 21) k ≡ 0 (mod 21) k = 21m x = 6 + 9 * 21m = 6 + 189m dla m = 0 mamy x = 6. Sprawdzenie 7 * 6 = 42 = 36 + 6 = 9 * 6 + 6 9 * 6 = 54 = 42 + 12 = 21 * 2 + 12.

ZKS: Oczywiście w sprawdzeniu powinno być " ... = 9 * 4 + 6 ... ".

Saizou : fakt, chyba było z a późno

henrys: Cały myk polega na tym, że 9 i 21 nie są względnie pierwsze dlatego dany układ 7x=6(mod3*3) 9x=12(mod3*7) możemy zastąpić układem 7*3k=6(mod9) x=3k 3*3k=4(mod7) 7k=2(mod3), 7=1(mod3) ⇒k=2(mod3) 9k=4(mod7), 9=2(mod7) ⇒k=2(mod7) k=3*7s+2=21s+2 dla s=0 k=2, x=6

Przemysław: Dziękuję bardzo