Problem przy potęgowaniu modularnym hgv: Jak policzyć 2⁴25(mod 168)? Podstawa potęgi i moduł nie są względnie pierwsze, więc Twierdzenie Eulera odpada. 168 nie jest liczbą pierwszą, więc Małe Twierdzenie Fermata też się nie przyda. Co zrobić w takiej sytuacji? Albo coś takiego: x≡17⁻¹(mod 83) Jak należy podejść do takich zadań?

hgv: Ten pierwszy przykład powinien wyglądać tak: 2⁴²⁵(mod 168)

Basia: 17⁻¹(mod cokolwiek) nie istnieje modulo to zawsze liczba naturalna

hgv: Dzięki za odpowiedź. Zapamiętam. A masz jakiś pomysł na ten pierwszy przypadek? W całości wygląda tak: 3373x ≡ 2²⁴⁵ (mod 168)

Basia: prawdę mówiąc nie bardzo i w ogóle tego nie rozumiem przecież N(modM) < M 2²⁴⁵ to nie jest liczba mod168 to co najpierw znaleźć 2²⁴⁵ mod168 ?

Vax: 17⁻¹ mod 83 oznacza element odwrotny do 17 mod 83, czyli taką liczbę x, że 17*x = 1 (mod 83). Wyznaczamy ją korzystając z rozszerzonego algorytmu Euklidesa. Jeden przykład rozwiązałem kiedyś w tym temacie: https://matematykaszkolna.pl/forum/102617.html (post 23września 2011 godz. 17:24) Przeanalizuj tamto, jakby co wynik powinien wyjść 17⁻¹ = 44 (mod 83). Co do równania 3373x = 2²⁴⁵ (mod 168) To zauważamy na początku, że 3373 = 13 (mod 168) I trzeba wyliczyć ile to jest 2²⁴⁵ (mod 168), rozwiązujemy to rozbijając to na kilka kongruencji, chcemy znaleźć: y = 2²⁴⁵ (mod 168) Co jest równoważne: {y = 2²⁴⁵ (mod 8) {y = 2²⁴⁵ (mod 3) {y = 2²⁴⁵ (mod 7) Każdą z kongruencji rozpatrujemy oddzielnie, naturalnie 2²⁴⁵ = 0 (mod 8), następnie 2²⁴⁵ = (−1)²⁴⁵ = −1 = 2 (mod 3), oraz 2²⁴⁵ = 2² * (2³)⁸¹ = 2²*8⁸¹ = 2²*1 = 4 (mod 7), czyli: {y = 0 (mod 8) {y = 2 (mod 3) {y = 4 (mod 7) Skąd łatwo wyznaczamy, że y = 32 (mod 168), czyli 2²⁴⁵ = 32 (mod 168), mamy więc: 13x = 32 (mod 168) Wyznaczamy teraz 13⁻¹ (mod 168) (z rozszerzonego algorytmu Euklidesa), po chwili dostajemy 13⁻¹ = 13 (mod 169), więc naszą kongruencje mnożymy stronami przez 13: 13x = 32 (mod 168) /*13 ⇔ x = 80 (mod 168) Koniec

PW: 3373=20•168+13 3373x=20•168x+13x Inaczej mówiąc: dla dowolnej x całkowitej 3373x≡13x(mod168) Może teraz łatwiej?

PW: Przepraszam, że się w ogóle odezwałem (nie odświeżyłem w porę). Dobrze. że chociaż w małym kawałku jesteśmy zgodni (nie lubię całej roboty wykonywać, bo adept mało wtedy sam kombinuje).

hgv: Dzięki za pomoc.