Uppgift 1
Lös följande problem.
(a)
Ge exempel på två sammansatta tal $a$ och $b$ så att $\SGD(a,b)=1$.
(b)
Formulera Fermat's lilla sats.
(c)
Beräkna resten då $4^{63}$ delas med $31$.
Diskret matematik · 2024-08-13
Uppgift 1
Visa lösningDölj lösning
- Man kan ta t.ex $a=4$ och $b=9$.
- Om $p$ är ett primtal och $a$ är ett heltal så att $a$ ej delas av $p$, då gäller $a^{p-1} \equiv 1$ (mod $p$).
- Eftersom $31$ är ett primtal, gäller enl. Fermat's lilla sats att \[ 4^{63} = 4^3 (4^{30})^2 \equiv_{31} 4^3 \cdot 1^2 = 64 \equiv_{31} 2. \] Alternativt, $4^{60} = 2^{120} = (2^5)^{24} = (32)^{24} \equiv_{31} 1^{24} = 1$, där $\equiv_{31}$ indikerar att talen ger samma rest modulo $31$.