Bestäm resten då - moduloräkning

Börja med att undersöka vad 23ⁿ är kongruent med modulo 7. Du är på jakt efter någon potens som är kongruent med 1 eller 22 (d v s -1).

23¹ är kongruent med 2, sedan blir det 4 (23² är ju kongruent med 2²) och 16 (d v s 2) och redan här bör du se ett mönster, även om det inte var det mönstret som jag var ute efter...

Behöver du mer hjälp så visa hur långt du har kommit och fråga igen.

Smaragdalena skrev:

Börja med att undersöka vad 23ⁿ är kongruent med modulo 7. Du är på jakt efter någon potens som är kongruent med 1 eller 22 (d v s -1).

23¹ är kongruent med 2, sedan blir det 4 (23² är ju kongruent med 2²) och 16 (d v s 2) och redan här bör du se ett mönster, även om det inte var det mönstret som jag var ute efter...

Behöver du mer hjälp så visa hur långt du har kommit och fråga igen.

Kvadrerar du varje gång? Jag tycker tredje talet blir 8, inte 16.

Att kvadrera varje gång leder visserligen till ett annat sätt att räkna ut det på ett effektivt sätt.

Du har rätt, jag tänkte fel.

Finns möjligtvis en effektivare metod för att ta sig an denna uppgift?

Janekeberg11 skrev:

Finns möjligtvis en effektivare metod för att ta sig an denna uppgift?

Nej, den lättaste metoden är att multiplicera 2 med sig självt lagom  många gånger. 2 är ju kongruent med 23 modulo 7. Varje gång som produkten blir större än 7 så "drar du ner den" till rätt intervall.

23 är kongruent med 2 modulo 7 (skriver inte ut modulo 7 på varje rad...)

23² är kongruent med 2², d v s 4

23³ är kongruent med 2³= 8 som är kongruent med 1 BINGO!

23²⁴ = (23³)⁸ = 1⁸= 1. Klart.

Varför vill man hitta ett tal som är kongruent med 1?

Vad blir $1^n$ om n är ett reellt tal?

Kika igen på vad Smaragdalena gör. Efter att hon inser att $23^3$ är kongruent med 1 så kan vi snabbt inse att om exponenten är en multipel av 3 så är resten 1, om inte, då kan vi splittra talet och eliminera den biten som har en exponent som är en multiipel av 3 eftersom vi vet att den ger en rest på 1. 

Så hade vi istället haft $23^4$, vi vet ju att $23^3$ ger resten 1 så vi kan splittra talet till $23^3 \cdot 23^1$, detta ger då resten $1 \cdot 2$ vilket ger en rest på 2. osv.