Moduloräkning

Börja med att kolla vad $4^0$, $4^1$, $4^2$, $4^3$, $4^4$ och så vidare har för rest när de delas med 7. Ser du något mönster?

$4^{1}mod 7 = 4$, $4^{2}mod 7 = 2$, $4^{3}mod 7=\hspace{0.17em}1$, $4^{4}mod 7 = 4$, $4^{5}mod 7= 2$, $4^{6}mod 7 = 1$, $4^{7}mod 7 = 4$..

Vad kan jag dra för slutsats med det här? Att eftersom exponenten (152) slutar på en tvåa - är resten 2 då $4^{2}mod7=\hspace{0.17em}2?$

Nej. Du ser att $4^{3n}mod7=1$, att $4^{3n+1}mod7=4$ och att $4^{3n+2}mod7=2$. Den intressanta delen är att att $4^{3n}mod7=1$, eftersom $1^k$ är extremt lätt att beräkna.

Vad blir det om du skriver om exponenten $152$ på formen $3n+a$, där a är ett så litet positivt heltal som möjligt?

Om jag skulle skriva om exponenten 152 på formen 3n + a hade det väl blivit 3n + 149?
Hur hjälper detta mig? $4^{3n+149}$ mod7? Som du säger är förstås $4^{3n}mod7 =1$.

Nej, n skall vara så stort som möjligt. Då får du den enklare beräkningnen $4^{152 }= 4^{3n}·4^a = 1^{3n}·4^a = 4^a$

Du får ursäkta mig att jag inte riktigt hänger med.. Men ifall n ska vara så stort som möjligt innebär det väl att n är 50, så vi får följande: $4^{3·50+2}$ och $4^{150} mod7=1$? Sedan är $4^{2}mod 7 =2$. 

Du är väldigt, väldigt nära, för att inte säga framme. Vad är alltså resten om $4^{152}$ delas med 7?

2 förstås! Tack så mycket!

En alternativ metod: 

$a^b (\mathrm{mod} \mathrm{c})\equiv (a (\mathrm{mod} \mathrm{c}){)}^b$

$\frac{4^{152}}{7}=\frac{(4^2{)}^{76}}{7}$ (Potenslagarna)

Vilket enligt regeln ovan måste vara samma sak som

$\frac{{16}^{76}}{7}\equiv 2^{76} (\mathrm{mod} 7)$

Vi fortsätter:

$\frac{2^{76}}{7}=\frac{2·2^{75}}{7}=2·\frac{2^{75}}{7}$

Vilket kan skrivas om som:

$2·\frac{(2^3{)}^{25}}{7}\equiv 2·1^{75} (\mathrm{mod} 7)=2$

Metoden liknar den metod som Smaragdalena gett dig här, men med ett lite annorlunda sätt att skriva uträkningen på.