Teoria liczb AHQ: Dzień dobry Potrzebuję pomocy w rozwiązywaniu zadań z teorii liczb. Chodzi mi głównie o kongruencję, twierdzenie chińskie o resztach, twierdzenie Bezouta, Fermata itd. Bardzo proszę o wyjaśnienie podstawowych chwytów na jasnych przykładach, jak wygląda zastosowanie tych twierdzeń Oto kilka zadań: UWAGA jako ,,='' rozumiem ,,przystaje do'' (nie wiem czy jest taka komenda) Zadanie 1.1 Wiedząc, że x należy do przedziału [0;1200] rozwiąż następujący układ kongruencji

⎧	x=3 (mod 5)
⎜	x=3 (mod 6)
⎨	x=1 (mod 7)
⎩	x=0 (mod 11)

Zadanie 1.2 Wyznaczyć x jeżeli x²=1 (mod 144) Zadanie 1.4 Liczba naturalna n jest iloczynem k różnych liczb pierwszych nieparzystych. Ile istnieje takich liczb całkowitych dodatnich a < n, ze liczba a² − 1 jest podzielna przez n? Zadanie 1.8 Wyznaczyć ostatnie trzy cyfry liczby 2008^2007...21 Oczywiście ! Nie oczekuję pustego rozwiązania zadań, ale wskazówek, wyjaśnień itp. Może jedno jako przykład Wszystkie drogocenne rady byłych olimpijczyków i pasjonatów OM mile widziane

Adamm: Nie ma komendy, ale jest symbol na górze (kliknij inne). 1.1 Po kolei. x = 3 (mod 5) x = 3 (mod 6) x = 3 lub 9, 15, 21, 27 (mod 30) Teraz wybieramy ten który jest = 3 mod 5, czyli 3 Zatem ten układ dwóch równań jest równoważny x = 3 (mod 30) Itd.

AHQ: Skąd sugestie tych liczb: 9,15,21,27 ? Czy jeżeli 5 I x−3 oraz 6 I x−3 to z tego wprost nie wynika, ze również i 30 musi dzielić x−3 ?

Saizou : Można też tak x ≡ 3 (mod 5) →x=5k+3 Wstawiam to do kolejnych równań 5k+3 ≡ 3 (mod 6) → 5k ≡ 0 (mod 6) → k ≡ 0 (mod 6) → k = 6l 5k+3 ≡ 1 (mod 7) → 5k ≡ −2 (mod7) /*3 → k ≡ −6 (mod 7) → k ≡ 1 (mod 7) 5k+3 ≡ 0 (mod 11) →5k ≡ −3 (mod11) /*2 → −k ≡ −6 (mod 11) → k ≡ 6 (mod 11) wstawiam wyznaczone k =6l do 3 i 4 równania 6l ≡ 1 (mod 7) → −l ≡ 1 (mod7) → l ≡ 6 ( mod 7) →l = 7p+6 6l ≡ 6 (mod 11) /*2 → l ≡ 1 (mod 11) Wstawiam l do ostatniego równania 7p+6 ≡ 1 (mod 11) →7p ≡ 6 (mod 11) /*8 →p ≡ 4 (mod 11) → p=11m+4 x = 5*6*(7*(11m+4 )+6) +3 = 2310m +1023

Adamm: Bierzesz 3 i dodajesz kolejno szóstkę

AHQ: Ok, już rozumiem. Czy polecacie Panowie jakąś dobrą literaturę na ten temat ?

Adamm: Ponieważ NWD(x−1, x+1)∊{1, 2}, to (x−1)(x+1) = 0 (mod 16*9) ⇔ (x−1)(x+1) = 0 (mod 16) oraz (x−1)(x+1) = 0 (mod 9) (x−1)(x+1) = 0 (mod 9) ⇔ x = ±1 (mod 9) (x−1)(x+1) = 0 (mod 16) ⇔ x = ±1 (mod 8) Mamy 4 możliwości x = 1 (mod 9) i x = 1 (mod 8) skąd x = 1 (mod 9*8) ⇔ x = 1 lub 73 (mod 144) reszta analogicznie

Adamm: n^n−1...1 = C(n) chcemy policzyć C(2018) mod 10³ C(2018) = 0 (mod 8) by obliczyć C(2018) mod 5³, obliczymy C(2017) mod φ(5³), φ(5³) = 5²*4 C(2017) = 1 (mod 4) by obliczyć C(2017) mod 5², obliczymy C(2016) mod φ(5²), φ(5²) = 5*4 C(2016) = 0 (mod 4) C(2016) = 1 (mod 5) i stąd obliczamy C(2016) mod 5*4

Adamm: n = p...q − rozkład na liczby pierwsze To a = ±1 (mod p) ... a = ±1 (mod q). Zauważ, że 1 ≠ −1 (mod p) itd. Czyli takich liczb a jest 2^m(n), gdzie m(n) to liczba czynników w rozkładzie n na liczby pierwsze.

AHQ: Okay, postaram się to zrozumieć , dzięki

Mariusz: AHQ znasz Chińskie twierdzenie o resztach ? x=3 (mod 5) x=3 (mod 6) x=1 (mod 7) x=0 (mod 11) x≡3 mod 30 x≡1 mod 7 x≡0 mod 11 Rozszerzony algorytm Euklidesa 30=4*7+2 2=30−4*7 7=3*2+1 1=7−3*2 1=7−3(30−4*7) 1=13*7−3*30 x≡3 mod 30 x≡1 mod 7 x≡0 mod 11 x≡183 mod 210 x≡0 mod 11 210=19*11+1 1=210−19*11 −38247 mod 2310 210*1*0−19*11*183 209 183 627 1672 209 38247 −38247 mod 2310 −16 −38247:2310 2310 15147 13860 −1287 2310 −1287 1023 x≡1023 mod 2310 x=1023 + 2310k , k∊ℤ i ty wybierasz tylko te które należą do podanego przez ciebie przedziału