Modulräkning

Vad blir resterna för 4² och 4³?

En annan metod är att konstatera att 4³ = 64 som är kongruent med 1 modulo 7.

Tips: det finns ett begränsat antal rester som kan uppträda för ett tal på formen 4ⁿ. Du kan visa det så här:

Låt $\displaystyle 4^n = 7k+r_n, n,k\in\mathbb{Z}^+$. Det uttalandet medför att $4^n\equiv_{7}r_n$. Nu konstaterar vi följande:

$\displaystyle r_{n+1}\equiv_{7}(4^n)\cdot 4\equiv_{7}4(7k+r_n)\equiv_{7}4{r_n}$

Testa att stoppa in resten r₁ och plocka fram några på varandra efterföljande rester. Ser du något mönster?

Tillägg: 1 feb 2024 15:53

Och självklart måste $\displaystyle 0\le r_n\le 6$

Smaragdalena skrev:

En annan metod är att konstatera att 4³ = 64 som är kongruent med 1 modulo 7.

En liknande metod är att konstatera att $4=2^2$, så uttrycket kan skrivas om till 

${\left(2^2\right)}^{150} (mod 7)={\left(2^3\right)}^{100} (mod 7) = 8^{100} (mod 7)$

@jacksparta: I moduloräkning är det bra att börja med att undersöka om det går att förenkla basen till något som ger rest 1 eller -1, dvs. något som är 1 större eller 1 mindre än det tal n, som vi behöver dividera med (i denna uppgift är $n=7$). :)