kongruencje popek: Potrzebuje pomocy z wytłumacznieniem jeszcze jednego zadania z kongruencji. Mam znaleźć najmniejsze dodatnie rozwiązanie układu:

⎧	x=19(mod23)
⎨	x=13(mod17)
⎩	x=12(mod15)

Na samym początku liczyliśmy jakieś m = 23 * 17 *15 = 5865 następnie M₁,M₂,M₃

	m		5865
M1=		=		= 255
	m1		23

	m
M1=		=345
	m2

	m
M1=		=401
	m3

I do tego momentu rozumiem, póxniej już nie wiem co się dzieje. N₁=M₁⁻¹(mod m₁) = −11 = 12 (mod 23) N₂=M₂⁻¹(mod m₂) = 315⁻¹(mod 17) = 7 N₃=M₃⁻¹(mod m₃) = 391⁻¹(mod 15) = 1 Później liczyliśmy NWD(17,315) = 1 i stosowaliśmy rozszerzony algorytm Euklidesa czyli 1=....=7*315−112*17 Później to samo z NWD(23,255) =.... 122 * 23−11*255 oraz z NWD(15,391) =.... poźniej używaliśmy czegoś takiego x₀ = a₁M₁N₁+a₂M₂N₂+a₃M₃N₃ = .... Mogłem coś pominąć bo wszystko było na sobie na tablicy.

jc: Chyba dobrze. x₀ jest pewnym rozwiązaniem. Najmniejsze dodatnie rozwiązanie uzyskasz biorąc resztę z dzielenia x₀ przez m.

popek: Ale od momentu, który opisałem nie wiem co się dzieje i co się skąd bierze.

jc: Opisałeś przepis na rozwiązanie. Jeśli x₀ jest pewnym rozwiązaniem, to wszystkie rozwiązania mają postać x₀+km.

Basia: jc popek to przepisał z tablicy, ale tego nie rozumie jeżeli potrafisz wytłumaczyć to też chetnie przeczytam

popek: Dokładnie tak jak Basia pisze.

Adamm: może najpierw dowiemy się czym są a₁, a₂, a₃

jc: Użyję małych liter. Zakładamy, że liczby m₁,m₂, m₃ są parami względnie pierwsze. x = a₁ (mod m₁) x = a₂ (mod m₂) x = a₃ (mod m₃) m = m₁m₂m₃ Równania (m/m_j) n_j + m_j k_j = 1 mają rozwiązania ze względu na n_j, k_j. * x= (m/m₁)n₁ a₁ + (m/m₂)n₂ a₂ + (m/m₃)n₃ a₃ jest pewnym rozwiązaniem, Dlaczego? Weźmy m₁. m₁ dzieli drugi i trzeci składnik, czyli o reszcie z dzielenia x przez m₁ decyduje pierwszy składnik. Reszta z dzielenia (m/m₁)n₁ przez m₁ wynosi 1 (równanie *) Zatem reszta z dzielenia (m/m₁)n₁a₁ przez m₁ wynosi a₁, czyli tyle, ile ma być. itd.

Basia: a skąd tam się nagle wzięło (przy obliczaniu n₂ i n₃) 315 i 391?

jc: m = 23 * 17 *15 = 5865 m/m₁ = 255, n₁= −11 bo 23| −255*11−1 m/m₂ = 345, n₂=7 bo 17|345*7−1 m/m₃ = 391, n₃=1 bo 15|391−1 x = [225*(−11)*19+ ... ] mod 5865 = 387

Basia: a czyli wyżej jest błąd rachunkowy (ten zapis M₁=401)