matematikk.net

Hei. Får ikke tl disse oppavene i tallteori.

a) Vis at 13|11^(12n+6)+1 for alle n>= 0

b) Vis at a^21 [symbol:identisk] a(mod15) for alle tall a
Skal bruke Fermats lille teorem, tror jeg.

c) x^2 [symbol:identisk] (mod5)

a) Vi regner modulo 13 og får [tex]11^{12n+6}=11^{6}11^{12n}=(-2)^{6}11^{12n}=64*11^{12n}=(-1)*11^{12n}=-11^{12n}[/tex] Anvender du nå Fermats lille teorem med a=12 og p=13 er du nesten i mål.

b) For å vise at a^21 er kongruent med a modulo 15 holder det å vise at a^21 er kongruent med a modulo 3 OG modulo 5 ettersom 15 primtallsfaktoriseres som 3*5. Som du helt riktig sier bruker du FLT til dette som over. Spør igjen om du ikke helt får taket på det.

c) Jeg antar du skal finne de kvadratiske restene modulo 5? Det finnes smarte, men dermed også avanserte metoder for å finne kvadratiske rester generelt, men jeg foreslår at du prøver å kvadrere 0, 1, 2, 3 og 4 og se hvilke rester du får. (Oppgave: Hvorfor trenger du ikke å kvadrere 5, 6,...?)

Hei. Hvor tar du tallteori?

a)
Sikkert flere måter å gjøre denne her på, induksjon osv osv.

[tex]11^{12n+6} = 11^{6(2n+1}}[/tex]

[tex]11^1 \equiv 11 \pmod {13}[/tex]
[tex]11^2 \equiv 4 \pmod {13}[/tex]
[tex]11^3 \equiv 44 \equiv 5 \pmod{13}[/tex]
[tex]11^6 \equiv 5^2 \equiv -1 \pmod{13}[/tex]

Dette gir oss da:

[tex](11^6)^{2n+1} + 1 \equiv (-1)^{2n+1} +1 \equiv 0 \pmod{13}[/tex]

Ser nå, mens jeg forhåndsviser at tråden allerede har blitt besvart, men lar det stå.

Hei.

Jeg tar matematikk årsstudium på HIA i Kristiansand, og der har jeg tallteori..

Hei-

Takk for svarene, men vil du forklare oppg.a) litt nærmere?

Prøv å lese Magnus' svar på a), det er nesten så direkte som det er mulig å få det. Hvis du leser det gjennom og sier fra hvor det begynner å lugge, er det lettere å hjelpe deg videre.

Hei.

Nå skjønner jeg hva Magnus har gjort.


Men går det an å bruke Fermats lille teorem til å løse oppg.a)??

Flott du er med nå.

Fermats lille teorem kan brukes som beskrevet over:
[tex]11^{12n+6}=11^{6}11^{12n}=(-2)^{6}11^{12n}=64*11^{12n}=(-1)*11^{12n}=-11^{12n}[/tex]
13 er et primtall, og siden vi regner modulo 13, og 13 ikke går opp i 11 kan vi bruke teoremet. Det er ofte beskrivi i lærebøker som [tex]a^{p-1}\equiv 1 (mod p)[/tex]. Med a=11 og p=13 får vi [tex]11^{13-1}\equiv11^{12}\equiv1(mod 13)[/tex] og dermed også [tex]11^{12n}=(11^{12})^n=1^n=1[/tex]. Vi fortsetter derfor likhetene fra over: [tex]11^{12n+6}=...=-11^{12n}=-1[/tex] Følgelig har vi altså [tex]11^{12n+6}+1\equiv0 (mod 13)[/tex] og altså [tex]13\mid11^{12n+6}+1[/tex]. Fattbart?

Hvilken metode man foretrekker, er litt opp til en sjøl. Ved Magnus' direkte metode har man nok større begreper om hva det er som faktisk foregår og det kan også være lurt å benytte seg av dette for å få trening i moduloregning generelt; det er ikke alltid man kjenner til et smart teorem som gjør oppgavene for en. Fordelen med å bruke Fermat er at det ofte er raskere og man kan slippe unna litt regning. Føl deg litt fram er det beste råd jeg kan gi.

Jepp, det er fattbart!

Takk.