. asdf: Arytmetyka modularna: da się policzyć jakoś k? 70^k ≡ 1 mod 130

niechciany: k = 0 działa dla k ≥ 1 liczba 70^k − 1 jest liczbą nieparzystą, zatem nie może być podzielna przez liczbę parzystą.

asdf: zle zapisalem i nie doczytalem polecenia...sorry, mialo byc: 70^k ≡ 1 mod 131 gdzie 0 < k <131 dodatkowo 70 jest generatorem grupy, zachodzi taka wlasnosc: g^x ≡ 1 mod p, jesli p jest pierwsza, to: g^x ≡ c mod p, !≡ to jest rozne od ∀_{x1, x2 ∊ Zp} g^x₁ !≡ g^x₂ mod p (krótka definicja generatora) to g^p−1 ≡ 1 mod p (jedna z własności generatora grupy)

asdf: odp: k = 130

asdf: tam powinno byc: g^Φ(p) ≡ 1 mod p, jesli p jest pierwsza i g jest generatorem grupy

asdf: doczytalem MTF, nie ma tutaj zalozenia, ze g jest generatorem, wystarczy tylko, by nwd(g,p) = 1.

niechciany: 70¹³⁰ ≡ 1 mod 131 (MTF)

odp: 10|k

asdf: tak. odp, nie w kazdym przypadku

odp: W jakim nie?

asdf: niekoniecznie 10|k

asdf: np. 9^k ≡₁₃ 1 k = 12

odp: Przecież pytałeś się o 70^k = 1 mod 131, więc do tego przykładu była odpowiedź. A do 9^k = 1 mod 13 odpowiedzią będzie 3|k, 12 to szczególny przypadek.

asdf: 23 tez?

asdf: tzn: 9^k ≡₂₃1

odp: W tym przypadku 11|k. Możesz się zastanowić nad ogólnym przypadkiem dla dowolnego p pierwszego, ja idę spać. Dobranoc.

asdf: ogólny przypadek to: k | p−1 oraz (tu nie jestem pewien, zastanowie sie nad tym): c*k | p−1, c ∊ ℤ Dobranoc

Saizou : Twierdzenie Eulera (tu MTF, które jest szczególnym przypadkiem TE)mówi nam że a^Φ(p)≡1 (mod p) gdy NWD(a,p)=1 NWD(131,70)=1, zatem 70^Φ(131)≡1 mod131 oraz Φ(131)=131−1=130 bo 131 jest pierwsze 70¹³⁰≡1 mod131 czyli k=130