tallteori og rest

[Janhaa]

Har ikke fått boka ennå, så sliter litt.
Noen som har en grei løsning på denne;

[tex]1301^{338}\equiv r(\text mod \,\,98)[/tex]

[Haakon_V]

Du kan redusere grunntallet:

$1301^{338} \bmod 98 \equiv 27^{338} \equiv 3^{1014} \bmod 98$

Eulers phi-funksjon sier at om 3 og 98 er relativt primisk, så gjelder det at $3^{\phi(98)} \equiv 1 \bmod 98$,
der phi-funksjonen er antall tall under 98, relativt primisk til 98 og kan regnes ut slik:

$\phi(98) = 98 \cdot \frac{2-1}{2} \cdot \frac{7-1}{7} = 42$

Man ser at 42*24 = 1008, altså har man at

$3^{1008} \equiv (3^{42})^{24} \cdot 3^6 \equiv 3^6 \equiv 81 \cdot 9 \equiv (-17) \cdot 9 \equiv 43 \bmod 98$

[Janhaa]

Du kan redusere grunntallet:
$1301^{338} \bmod 98 \equiv 27^{338} \equiv 3^{1014} \bmod 98$
Eulers phi-funksjon sier at om 3 og 98 er relativt primisk, så gjelder det at $3^{\phi(98)} \equiv 1 \bmod 98$,
der phi-funksjonen er antall tall under 98, relativt primisk til 98 og kan regnes ut slik:
$\phi(98) = 98 \cdot \frac{2-1}{2} \cdot \frac{7-1}{7} = 42$
Man ser at 42*24 = 1008, altså har man at
$3^{1008} \equiv (3^{42})^{24} \cdot 3^6 \equiv 3^6 \equiv 81 \cdot 9 \equiv (-17) \cdot 9 \equiv 43 \bmod 98$

Det var fravær ang kunnskap om Eulers phi function som vanskeligjorde dette.
Takk skal du ha Haakon