Kongruencje Dominik: Czy jakaś dobra duszyczka mogłaby mi wytłumaczyć jak rozwiązać taką kongruencję krok po kroku? 122x≡1(mod 343) Z mniejszymi modulami wiem, że można to jeszcze jakoś rozpisać ale tutaj mamy przedział x∊(0,343> wiec robi sie klopot

mat: 344=1 mod 343 NWW(344,122)=20984

	20984
zatem x=		=172
	122

mat: nie nie nie..

mat: Rozwiąż równanie 122a+343b=1

mat: W liczbach całkowitych

mat: zbiorze liczb całkowitych*

Pytający: 122x=343k+1 122x−343k=1 343=2*122+99 122=1*99+23 99=4*23+7 23=3*7+2 7=3*2+1 1=7−3*2=7−3(23−3*7)=10*7−3*23=10(99−4*23)−3*23=10*99−43*23= =10*99−43(122−1*99)=53*99−43*122=53(343−2*122)−43*122=53*343−149*122 x≡−149≡194

Dominik: Kurcze, mądre

Dominik: To wkoncu która odpowiedź jest dobra? Bo mi udało się dojść do wyniku pytającego, 194

Mila: 343=122*2+99 122=99*1+23 99=23*4+7 23=7*3+2 7=2*3+1 odwracamy algorytm 1=7−2*3=7−3*(23−7*3)=7−3*23+9*7=10*7−3*23= =10*(99−23*4)−3*23)=10*99−40*23−3*23= =10*99−43*23=10*99−43*(122−99*1)= 10*99−43*122+43*99=53*99−43*122= =53*(343−122*2)−43*122= =53*343−106*122−43*122= =53*343−149*122 ============= −149+343=194 122⁻¹≡_z343194

Dominik: Dzięki za rozpisanie ale mogłabyś jeszcze wyjaśnić początek tego algorytmu? Bo nie wiem co tu jest mnożone i sumowane do siebie itp.

Mila: Rozszerzony algorytm Euklidesa http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1/Wyk%C5%82ad_10:_Teoria_liczb