teoria liczb grzechu: Oblicz następujące wyrażenia: 15³²³ mod 51 Prosiłbym o pomoc w rozwiązaniu tej kongruencji.

ABC: zapisz 323 w postaci sumy potęg 2 :256+64+2+1 znajdź przez podnoszenie do kwadratu 15≡15 15²≡225≡21 15⁴≡441≡33 15⁸≡1089≡18 i tu zaczyna się powtarzać bo 15¹⁶≡324≡18 i dokończ sam

grzechu: 15³²³≡₅₁ 3³²³ * 5³²³≡₅₁ ... φ(51)=φ(17*3)=16*2=32 3⊥51 => 3³² ≡₅₁1 − to jest źle, bo 3 i 51 nie są względnie pierwsze (tj. 3*17=51) 5⊥51 => 5³² ≡₅₁1 ... ≡₅₁(3³²)¹⁰ * 3³ * (5³²)¹⁰ * 5³ ≡₅₁ 3³ * 5³ ≡₅₁(3*5)³ ≡₅₁3375 ≡₅₁9 Generalnie to wynik na samym końcu wyszedł mi dobrze, bo pasuje do klucza odpowiedzi, ale zadanie jest źle wykonane, bo 3 i 51 nie są względnie pierwsze. Proszę o pomoc w rozwiązaniu tego zadania tym “moim” sposobem.

Mila: 1) 51=3*17 5⊥17 5¹⁷⁻¹=1(mod17) 5³=6(mod17) (5¹⁶)²0)*5³=6(mod17) 2)3⊥17 3¹⁶=1(mod17) (3¹⁶)²⁰=1(mod17) 3³²⁰*3²=9(mod 17) 4) 3³²²*5³²³=9*6 (mod17) 3³²²*5³²³=3(mod17) /*3 3³²³*5³²³=9 (mod 51) Sprawdź teorię.

Adamm: 51 = 17*3 15³²³ ≡ 0 (mod 3) 323 ≡ 3 (mod 16) 15³²³ ≡ 15³ ≡ −2³ = −8 ≡ 9 (mod 17) 15³²³ ≡ x (mod 51), gdzie x∊{9, 9+17, 9+2*17} = {9, 26, 43} oraz x ≡ 0 (mod 3) więc x = 9