Moduloräkning.

Hej!

Jag har nyligen börjat med moduloräkning och har lite problem med att förstå hur det går till.
Uppgiften i fråga är "Bestäm resten då 5^163 delas med 9."

Hittills har jag skrivit om 5^163 som ((5^3)^54)*5^1 men kommer inte längre än så. Är inte säker på att jag skrivit helt rätt heller, tacksam för alla svar.

Sånt här man var bra på under diskret matematik -kursen i universitetet. Sen efteråt så glömde man allting

Du ska inte använda typ Euler's theorem? 163 är dessutom ett primtal, känns inte som någon slump.

Eller Fermat's little theorem. 163 - 1 är en multipel av 9, men jag kanske är ute och cyklar.

Fysik, matematik och teknologi --> Matematiska och naturvetenskapliga uppgifter
/Moderator

<Felaktigt svar>

EDIT2: Enligt Wolfram Alpha är det 5 så jag lägger ner detta

Skriv det som \(5\cdot(5^6)^{27}\);
\[
5^6 \equiv 1\mod 9
\]
varför
\[
5\cdot(5^6)^{27} \equiv 5\cdot1\equiv 5\mod9
\]

ovan rätt men du behöver inte räkna ut vad 5^6 är utan vad 5^3 är.
5^3=125=13*9+8
Nu kommer det smarta i kråksången, du kan skriva 125 på ett smartare sätt.
125=14*9-1
alltså är 125==-1 mod 9
5^163=(5^3)^54 * 5 ==1*5 mod 9
resten är 5 alltså.

du kan inte använda satsen a^(p-1)==1 mod p då a och p ska vara relativt prima (vilket de är) men den gäller bara om äv p är ett primtal. 9=3*3 så inget primtal.