WisFaq!

Machtrekenen met modulo

Ik snap heel goed wanneer je Fermat en Euler kunt toepassen maar wat nou als getal a geen priemgetal is?
Bijvoorbeeld: 1808³⁷⁰³(mod6649)?
1808 is geen priemgetal, ggd(1808,6649)=1 maar wat schiet ik hier mee op?

Henri Dokter
1-3-2004

Antwoord

Of a een priemgetal is of niet doet volgens mij hier niet ter zake. In dit geval lijkt het mij het handigst om 1808³⁷⁰³ te ontbinden (mod 6649) en zo het restsysteem te bepalen:

1808² $\equiv$ 4205 (mod 6649)
1808⁴ $\equiv$ 2334 (mod 6649)
1808⁸ $\equiv$ 2025 (mod 6649)
1808¹⁶ $\equiv$ 4841 (mod 6649)
1808³² $\equiv$ 1808² $\equiv$ 4205 (mod 6649)
1808⁶⁴ $\equiv$ 1808⁴ $\equiv$ 2334 (mod 6649)
1808¹²⁸ $\equiv$ 1808⁸ $\equiv$ 2025 (mod 6649)
1808²⁵⁶ $\equiv$ 1808¹⁶ $\equiv$ 4841 (mod 6649)
1808⁵¹² $\equiv$ 1808³² $\equiv$ 1808² $\equiv$ 4205 (mod 6649)
1808¹⁰²⁴ $\equiv$ 1808⁶⁴ $\equiv$ 1808⁴ $\equiv$ 2334 (mod 6649)
1808²⁰⁴⁸ $\equiv$ 1808¹²⁸ $\equiv$ 1808⁸ $\equiv$ 2025 (mod 6649).

1808³⁷⁰³ =
= 1808²⁰⁴⁸×1808¹⁰²⁴×1808⁵¹²×1808⁶⁴×1808³²×1808¹⁶×1808⁴×1808²×1808¹ $\equiv$
$\equiv$ 2025 × 2334 × 4205 × 2334 × 4205 × 4841 × 2334 × 4205 × 1808 $\equiv$
$\equiv$ 1808 × 2025 × 2334³ × 4205³ × 4841 $\equiv$
$\equiv$ 1808 × 2025 × 5560 × 546 × 4841 $\equiv$
$\equiv$ 4250 × 3816 × 4841 $\equiv$
$\equiv$ 1089 × 4841 $\equiv$ 5841 (mod 6649).

Dit zou het antwoord moeten zijn. Een eenvoudiger methode is mij niet bekend, maar ik hou me graag aanbevolen.

KLY
1-3-2004