modulregning og delighet

[Nebuchadnezzar]

Sitter og leser litt om dette og forstår det ikke helt.

For eksempel så bruker boken ofte tegnet

[tex]\equiv[/tex]

som jeg ikke forstår helt betydningen/bruken av. Det betyr vel identisk med, men ser ikke helt når man skal bruke det.

Videre er det masse delingsregler, men forstår ikke helt hva det betyr, eller hvordan jeg kan "regne" med mod

For eksempel så har vi

[tex]a \equiv b \text{mod}(a)[/tex]

Og betydningen av dette er vel at dersom vi trekker b ifra a, så er tallet delelig med a?

Lurer litt på hvordan jeg kan med enkelhet bruke dette for å vise deligheten av diverse tall. Så litt på noen oppgaver med eksemplene var litt kompliserte. ..

For eksempel

Finn resten når 2^{50} deles på 7. Dette kan vel skrives som

[tex]2^{50} \equiv a \text{mod}(7)[/tex] ?

EDIT:

[tex]{2^{50}} \equiv a\bmod \left( 7 \right) \\ {2^3} - 1 \equiv 0\bmod \left( 7 \right) \\ {2^4} - 2 \equiv 0\bmod \left( 7 \right) \\ {2^5} - 4 \equiv 0\bmod \left( 7 \right) \\ {2^5} - 8 \equiv 0\bmod \left( 7 \right) \\ {2^n} - {2^{n - 3}} \equiv 0\bmod \left( 7 \right) \\ {2^{50}} - {2^{47}} \equiv 0\bmod \left( 7 \right) \\ [/tex]

[espen180]

[tex]\equiv[/tex] en et kongruenstegn i tallteori.

Et viktig grunnresultat er at gitt to tall [tex]u,v[/tex], finnes det et unikt par [tex](a,b)[/tex] slik at [tex]u=av+b[/tex] og [tex]b<v[/tex].

Da definerer vi [tex]u\equiv b\, \rm{mod}\, v[/tex]. Vi vet at dette er en veldefinert relasjon på grunn av teoremet over.

Videre kan man utlede forskjellige regneregler som i bunn og grunn sier at modulus av sum er lik sum av moduluser osv.

Når det kommer til oppgaven din, vil jeg anbefale deg å se på [tex]2^n \, \rm{mod} 7[/tex]. Da vil få få sammenhengen
1 - 1
2 - 4
3 - 1
4 - 2
5 - 4
6 - 1
7 - 2
8 - 4
...
Du ser mønsteret. Hvis du kan bevise at dette mønsteret forsetter, vet du at det gjelder for n=50, go da finer du løsningen på en lettvint måte.

[Nebuchadnezzar]

Jeg ser mønsteret men klarer ikke å bevise det =/

[Gustav]

Vi har at

[tex]2^{50}= 2^{5*10}=(2^5)^{10}=32^{10}[/tex].

Siden [tex]32\equiv 4 \, mod(7)[/tex] er [tex]32^{10}\equiv 4^{10}\, mod(7)[/tex].

I grunnen bare å fortsette på samme vis til du får et tall som er mellom 0 og 6. Da vil dette tallet være resten ved divisjon med 7.

[Janhaa]

jeg blander meg inn. kan man skrive slik plutarco?

[tex]2^3 \equiv 1^3 (\text mod\, 7)[/tex]

[tex](2^3)^{16}=2^{48} \equiv 1^{16} (\text mod\, 7)[/tex]

[tex]2^{48}\cdot 2^2=2^{50} \equiv 2^2 (\text mod\, 7)[/tex]

[tex]2^{50} \equiv 4 (\text mod\, 7)[/tex]

[Gustav]

Ja, blir jo i prinsippet bare en variant av det samme. Evt. kan man bruke Fermats lille teorem: [tex]2^{48}=(2^{8})^6\equiv 1\,mod(7)[/tex]

[Janhaa]

Ja, blir jo i prinsippet bare en variant av det samme. Evt. kan man bruke Fermats lille teorem: [tex]2^{48}=(2^{8})^6\equiv 1\,mod(7)[/tex]

OK, forstår. Frisker opp gammal kunnskap...

[svinepels]

Vi har ikke begynt med kongruensregning ennå, Nebu. Jeg ville lest gjennom og forstått kapittelet om delelighet, ettersom du har gått glipp av forelesningene i dette

[Nebuchadnezzar]

JEg gjør det kommer med spørsmål der og etterhvert. går i det minste påå forelesning og øving i morgen. Blir nok endel jobbing i ferien. Og forventer og se deg på forumtreff, blir jo bare noen timer på kvelden. Mamma er ingen unnskyldning.