Moduloräkning

Hej!

Jag har suttit med en uppgift som lyder "Bestäm resten då 2^135 delas med 9. " då jag har kommit fram till att det gäller moduloräkning och detta är min uträkning:

Från läraren får jag som svar att min uträkning inte stämmer då" 2^3 (mod 9) rest 2 eftersom 2^3 = 8<9 så 2^3 (mod 9) rest 8". Jag förstår inte vad läraren menade och frågade vad hen menade och fick samma svar igen, vad är det dom menar och har jag tänkt helt fel?

Tack på förhand :)

Allmänt gäller att om a<b så är a (mod b) = a
2^3 = 8
8/9 har rest 8 (0 st hela 9 och rest 8)
Alltså är 2^3 mod 9 = 8

Jag förstår att 2^3 = 8 och att resten blir 8, det jag inte förstår är varför hen skriver så då jag inte har skrivit det utan (2^3)^5 (mod 9)= 2^5

Programmeraren skrev:
Allmänt gäller att om a<b så är a (mod b) = a
2^3 = 8
8/9 har rest 8 (0 st hela 9 och rest 8)
Alltså är 2^3 mod 9 = 8

Jag förstår att 2^3 = 8 och att resten blir 8, det jag inte förstår är varför hen skriver så då jag inte har skrivit det utan (2^3)^5 (mod 9)= 2^5

Ser ut som det blir fel på andra raden. ${(2^{3})}^{45} m o d 9$ kan inte skrivas om som $2^{45} m o d 9$ (just detta steg råkar i detta fall vara rätt men gäller inte generellt. Du ser det tydligare i slutet då (2^3)^5 mod 9 = 8 men 2^5 mod 9 = 5).

För att ha nytta av uppdelningen av 2^135 måste talet inom parentesen vara större än 9 och 2^3 < 9. Prova istället med

$2^{135} = {(2^{5})}^{27}$

Man kan gå olika vägar men jag brukar bryta ut det minsta tal som är större än det tal man räknar modulo med. I detta fall skulle det varit 2^4 men tog 2^5 eftersom 5 delar 135, hade fungerat att istället ta 2^3*(2^4)^33 men det kändes geggigare.

Programmeraren skrev:
Ser ut som det blir fel på andra raden. ${(2^{3})}^{45} m o d 9$ kan inte skrivas om som $2^{45} m o d 9$ (just detta steg råkar i detta fall vara rätt men gäller inte generellt. Du ser det tydligare i slutet då (2^3)^5 mod 9 = 8 men 2^5 mod 9 = 5).

För att ha nytta av uppdelningen av 2^135 måste talet inom parentesen vara större än 9 och 2^3 < 9. Prova istället med

$2^{135} = {(2^{5})}^{27}$

Man kan gå olika vägar men jag brukar bryta ut det minsta tal som är större än det tal man räknar modulo med. I detta fall skulle det varit 2^4 men tog 2^5 eftersom 5 delar 135, hade fungerat att istället ta 2^3*(2^4)^33 men det kändes geggigare.

Hej igen!

Är det här mer i rätt riktining?

Hur försvinner 2^5 i början?

2^5=32 och 32 mod 9 = 5 så du får att

(2^5)^27 mod 9 = 5^27

Sen kan du fortsätta på samma sätt, t ex 5^27=5*(5^2)^13 och ersätta 5^2 med 5^2 mod 9

Du verkar dels göra en del räkneoperationer som jag inte förstår varför du gör och dels göra det onödigt svårt för dig!

Ett exempel på en räkneoperation som jag inte förstår varför du gör är att du skriver ${(2^{5})}^{27} \equiv 2^{27}$ mod 9. Det stämmer, men varför gör du just så?

Ett enklare sätt när du ska lösa den här typen av tal är att leta efter tal som är kongruenta med 1 eller -1.

Då kan man göra så här. Först testar man:

$2^{1} = 2 2^{2} = 4 2^{3} = 8 \equiv - 1 m o d 9$

Sedan skriver man om:

$2^{135} = {(2^{3})}^{45} = 8^{45}$

Och eftersom $8 \equiv - 1 m o d 9$ så är $8^{45} \equiv {(- 1)}^{45} = - 1 m o d 9$

Alltså blir resten 8.

Det viktiga att förstå är räknereglerna och att ordningen inte spelar någon roll.
Vissa val ger fler steg men innan man lär sig optimera uträkningen bör man behärska de grundläggande räknereglerna.

Felet i din uträkning (kl 12.51) är att du generellt antar att ${(a^{x})}^{y} m o d m = a^{y} m o d m$ vilket inte stämmer (det bara råkar stämma i första förenklingen)

Svara

Visa senaste svar