Moduloräkning
Hej! Sitter helt fast med en uppgift. 5^179 divideras med 8. Vad blir resten. Får resten till 4, men är osäker! Någon som har bra tips på hur man kan göra/tänka enkelt kring detta?
Hej! Sitter helt fast med en uppgift. 5^179 divideras med 8. Vad blir resten. Får resten till 4, men är osäker! Någon som har bra tips på hur man kan göra/tänka enkelt kring detta?
Tankesättet när man räknar modulo är vad som blir kvar när man dividerat ett tal så långt det går utan decimaler.
T.ex. 3/10 går 3 gånger utan decimaler (3+3+3 = 9 vilket är så nära 10 man kommer). Resten i detta fall blir 1 (10-9 = 1)
Hänger du med? :)
Ja, sådana enkla förstår jag helt och själva teorin. Men det praktiska för tex mitt tal ovanstående förstår jag inte helt :-
Ja, sådana enkla förstår jag helt och själva teorin. Men det praktiska för tex mitt tal ovanstående förstår jag inte helt :-
Matte 5!
5^179 / 8 -> 5*5*5^177/8 = 5*5^2^59 = 5*25^59 -> 5*1^59 (mod 8) eftersom 25 är delbart med 8 tre gånger och får 1 i rest. Sedan 1^59 = 1 så kvar blir endast 5*1 = 5 (mod 8).
Skrev snabbt, hoppas det inte är något litet fel längs vägen.
Skriv hur du räknat för att få 4 som svar så kan jag/någon hjälpa dig vart det går fel så behöver du inte göra samma miss igen nästa gång eller på ett prov :)
Jag fick resten till 0 när jag körde i ett program. Men vet inte om det hjälper så mycket då det är ett mattetal och då ska man väl kunna redovisa steg för steg och resonera sig fram till svaret, som carpediem86 gjort.
Studerat kongruenslagar i kursen?
Att två tal a och b är kongruenta modulo k innebär att samma rest erhålls vid division a/k som vid b/k.
Med två regler kan man enkelt räkna ut tal med höga exponenter.
Om tal a är kongruent(mod k) med b
-> så är a^n kongruent(mod k) med b^n
Om tal a är kongruent(mod k) med b OCH tal c är kongruent(mod k) med d
-> så är a*c kongruent(mod k) med b*d
5^2 = 25, vilket är kongruent (mod 8) med 1 .
Enligt första regeln är (5^2)^n kongruent(mod 8) med 1^n, som alltså blir 1 oavsett exponenten n.
Använd detta genom att bryta ut n ur exponenten 179:
5^179 = 5^(2*89 +1) = (5^2)^89 * 5^1 =
(5^2)^89 * 5
Termen (5^2)^89 är kongruent(mod 8) med 1^89 = 1 enligt första regeln.
Termen 5 är såklart kongruent(mod 8) med 5.
Enligt andra regeln är (5^2)^89 * 5 kongruent(mod 8) med 1 * 5.
Resten blir alltså 5.
Man kan också göra en tabell
5^1 rest 5
5^2 rest 1
5^3 rest 5
5^4 rest 1
5^5 rest 5
5^6 rest 1
Udda exponent ger rest 5.
Jämn exponent ger rest 1.
5^179 måste därför ha rest 5.