. asdf: modulo i duze potegi 7¹⁸⁴³ mod 9 ?

zombi: Wykorzystamy fakt, że jeśli (a,n) = 1, to a^φ(n) ≡ 1(mod n ), gdzie φ(n) to funkcja Eulera. U nas (7,9) = 1, czyli 7⁶ ≡ 1(mod 9) ponadto 1842 dzieli się przez 6, czyli 7¹⁸⁴³ = 7¹⁸⁴²*7 = 7^6*307*7 ≡ 1³⁰⁶*7 ≡ 7 (mod 9)

asdf: Dzieki! Chodzi oczywiscie o NWD(a,n) = 1, tak?

zombi: Tak

asdf: jeszcze raz, wielkie dzieki Mialem ten wzor przed oczami, ale jeszcze za po pierwszym zadanku jeszcze trudno tak "latac" ze wzoru na wzor

asdf: ale jeszcze po pierwszym zadanku trudno tak "lata" ze wzoru na wzor * (kreslilem, poprawialem, nie przeczytalem − wyszlo g*)

zombi: Jakbyś coś jeszcze miał z kongruencji to mogę się pobawić

asdf: 8¹⁹²⁴ mod 6

asdf: wskazowke jesli mozna

asdf: i jeszcze takie cos: 40⁷ mod 143

zombi: Odnośnie pierwszego, zauważ że 2²ⁿ ≡ −2 (mod 6) natomiast 2²ⁿ⁺¹ ≡ 2 (mod 6)

zombi: Wróć, to nie będzie tak xd

asdf: ok, a drugie?

zombi: A nie jednak dobrze ci powiedziałem, i teraz zauważ, że 8¹⁹²⁴ = 2^3*1924 = 2²ⁿ ≡ −2 ≡ 4 (mod 6)

asdf: tu nie mozna z funkcji Eulera bo NWD(8,6) > 1 tak? ;>

asdf: jeszcze drugie − i ide spac...

zombi: Tak (8,6) ≠ 1. Drugie chyba trochę na chama trzeba bo szybkiego sposobu nie widzę.

asdf: ja tutaj probuje tak: dzielniki 143: 1,11,13, Φ(143) = 3 NWD(143,40) = 1 40*(40³²) mod 143 = 40? a w odp: 105...

zombi: ale φ(143) = 120

asdf: eh...juz chyba pozno

asdf: nie wymysliles nic?

zombi: O takie coś fajne znalazłem. 40 = 2*2*2*5 = 10*4. Zauważasz, że 10³ ≡ −1 )mod 143), czyli 10⁷ ≡ 10 (mod 143) Pozostaje znaleźć 4⁷ = 2⁷*2⁷ ≡ 225 mod 143, czyli 4⁷ ≡ 82 mod 143, czyli 4⁷*10⁷ ≡ 10*82 mod 143 = 105 mod 143.

asdf: wlasnie ja tez to liczylem w taki sposob, ze: 40⁷ = (10⁷*2⁷), ale tam wychodzily takie miliardowe wyniki, ze pomyslalem, ze jest cos latwiejszego

asdf: a takie cos: 11³⁴⁵²⁷ mod 117?

zombi: Podobnie jak pierwszy. (11,117) = 1, liczymy fi(117) = 3*(3−1)*(13−1) = 72, czyli 11⁷² ≡ 1 mod 117. Ok teraz fajnie by było znaleźć jakąś liczbę mniejsza od 34527 podzielną przez 72, wystarczy znać cechę podzielność przez 9 i 8 i łatwo uzyskujemy, że 34524 jest podzielna przez 72, bo suma cyfr = 18, czyli jest podzielna przez 9, ponadto ostatnie dwie cyfry dzielą się przez 8, więc wygraliśmy 11³⁴⁵²⁷ = 11^34524+3 = 11³⁴⁵²⁴*11³ ≡ 11³ ≡ 44 mod 117

asdf: jak liczysz fi(117)?

zombi: Ogólnie chodzi o to, żeby znaleźć sobie liczbę postaci 72k, bo mając 11⁷² ≡ 1 (mod 117) nie ważne do jakiej podniesiemy jedynka, cały czas zostaje, więc luzik nie wpływa nam na wynik.

zombi: Zasada liczenia, jeśli argument x = p₁^k₁*p₂^k₂, gdzie p₁,p₂, pierwsze to fi(p₁^k₁*p₂^k₂) = fi(p₁^k₁)*fi(p₂^k₂) = = p₁^k₁−1*(p₁−1) * p₂^k₂−1*(p₂−1)

zombi: http://www.kopernik.katowice.pl/files/przedmioty/matematyka/kongruencje-oraz-przyklady-ich-zastosowan.pdf tutaj masz ładnie opisane.

asdf: ok, dzieki...ja juz ide spac ! starczy, dobranoc

zombi: Dobranoc