Gjest wrote:Begge, hvordan går man fram for å bevise d?
Tja, jeg oppdaget kongruensregning for omtrent en uke siden, og har ikke rukket å lære med noen "fancy" metoder enda, men jeg kan ta et enklere regnestykket jeg fant i en video, og prøve å forklare hvordan jeg forstod denne typen regning.
Oppgaven: Vis at 2^48-1 er delelig med 97.
Dette kan vi skrive om som [tex]2^{48}-1\equiv0(mod97)[/tex]. Det dette betyr er at [tex]2^{48}-1[/tex] kan bli delt med 97 slik at vi har 0 i rest. Om vi får en rest, så er de ikke delelige.
[tex]2^{48}-1\equiv0(mod97) \Leftrightarrow 2^{48}\equiv1(mod97)[/tex]
Neste steg er å finne ut hva [tex]2^{48}[/tex] er (mod97).
Vi tar for oss en og en toerpotens.
[tex]2^1\equiv2(mod97)[/tex]
[tex]2^2\equiv4(mod97)[/tex]
[tex]2^4\equiv16(mod97)[/tex]
[tex]2^8\equiv256(mod97)[/tex] Når tallene overstiger 97, så begynner vi å trekke fra 97 helt til vi får igjen en rest større enn 0, men som er mindre enn 97. Dvs. at [tex]2^8\equiv256(mod97)\Leftrightarrow2^8\equiv62(mod97)[/tex] (Litt usikker på om dette stemmer, men jeg tror vi kan skrive det slik.)
[tex]2^{16}\equiv61(mod97)[/tex]
[tex]2^{32}\equiv35(mod97)[/tex]
Fra algebraen har vi at: [tex]2^{48}\equiv2^{16}*2^{32}\equiv2^{16+32}[/tex]
Da ser vi at [tex]2^{16}*2^{32}\equiv61*35\equiv1(mod97)[/tex]. Fordi 61*35=2135 og 2135-(97*22)=1.
Med dette har vi bevist at [tex]2^{48}-1[/tex] er delelig med 97.
