Citat:
Ursprungligen postat av
Red-Eagle
modulo, kongruens
Jag vill lösa ut x:
40 = (x^29) mod (7*13)
Men det står still, kan man utnyttja x^a (kongruent) x mod a?
Använd kinesiska restsatsen samt Eulers/Fermats sats, du har att
5 = 40 = x^29 = x^5 (mod 7),
1 = 40 = x^29 = x^5 (mod 13)
För att lösa den första x^5 = 5 (mod 7), multiplicera båda sidor med x så får man
1 = 5x (mod 7) ⇒
x = 3 (mod 7)
För den andra ekvationen så noterar vi att x måste ha en ordning som delar φ(13) = 12 samt 5, men gcd(12, 5) = 1 så ordningen för x måste vara 1, vilket innebär att x = 1 (mod 13).
Så vi har lösningen (3, 1) ∈ Z_7 × Z_13, om nu ψ: Z_{7*13} → Z_7×Z_13 är den kanoniska avbildningen som finns i kinesiska restsatsen så kan man notera att ψ(14) = (0, 1) och ψ(78) = (1, 0). Så alltså är ψ(78*3 + 14) = (3, 1) vilket alltså ger att x = 78*3 + 14 = 66 (mod 7*13)