Side 1 av 1
Eulers teorem
Lagt inn: 17/06-2020 19:43
av Hege Baggethun2020
Bruk Eulers teorem for å finne de to siste sifrene av [tex]27^{82}[/tex] og av [tex]7^{38}[/tex].
Eulers teorem:
Dersom [tex]n[/tex] er et positivt heltall og [tex]a[/tex] er et vilkårlig heltall med [tex]gcd(a,n)= 1[/tex], så er [tex]a^{\phi (n)} \equiv 1(modn)[/tex].
([tex]\phi (n)[/tex] er Eulers totientfunksjon.)
Re: Eulers teorem
Lagt inn: 17/06-2020 20:21
av eulers sønn
FASIT: 29 og 49
Re: Eulers teorem
Lagt inn: 17/06-2020 20:33
av Janhaa
[tex]\phi(100)=40\\ \gcd(27,100)=1 \\ 27^{40}\equiv 1\pmod{100}\\ \\ (27^{40})^2=27^{80}\equiv 1\pmod{100}\\ 27^{80}*27^2=27^{82}\equiv 27^2\equiv 29 \pmod{100}[/tex]
Re: Eulers teorem
Lagt inn: 17/06-2020 21:11
av Janhaa
Nr 2 er sikkert noe invers Euler's teorem. Som jeg ikke husker :=)
Uansett går det an å "jukse" sånn:
[tex]7^4 \equiv 1 \pmod{100}\\ (7^4)^9=7^{36} \equiv 1 \pmod{100}\\ 7^{36}*7^2=7^{38} \equiv 7^2\equiv 49 \pmod{100}\\[/tex]
Re: Eulers teorem
Lagt inn: 17/06-2020 22:04
av Hege Baggethun2020
Janhaa skrev:[tex]\phi(100)=40\\ \gcd(27,100)=1 \\ 27^{40}\equiv 1\pmod{100}\\ \\ (27^{40})^2=27^{80}\equiv 1\pmod{100}\\ 27^{80}*27^2=27^{82}\equiv 27^2\equiv 29 \pmod{100}[/tex]
Supert!
Her benytter man altså det faktum at hvis man dividerer [tex]27^{82}[/tex] med 100, så vil resten man får ved divisjonen være den samme som de siste to sifrene av [tex]27^{82}[/tex].
Re: Eulers teorem
Lagt inn: 17/06-2020 22:15
av Hege Baggethun2020
Janhaa skrev:Nr 2 er sikkert noe invers Euler's teorem. Som jeg ikke husker :=)
Uansett går det an å "jukse" sånn:
[tex]7^4 \equiv 1 \pmod{100}\\ (7^4)^9=7^{36} \equiv 1 \pmod{100}\\ 7^{36}*7^2=7^{38} \equiv 7^2\equiv 49 \pmod{100}\\[/tex]
Man kan argumentere som følger:
Siden [tex]7^{40}\equiv 1(mod100)[/tex] så er [tex]7^{38}[/tex] en løsning av [tex]7^{2}x\equiv 1(mod100)[/tex].
[tex]7^{2}x\equiv 1(mod100)\leftrightarrow 49x\equiv 1(mod100)[/tex]
[tex]7^{2}x\equiv 1(mod100)\leftrightarrow 49x\equiv 301(mod100)[/tex]
[tex]7^{2}x\equiv 1(mod100)\leftrightarrow 7x\equiv 43(mod100)[/tex]
[tex]7^{2}x\equiv 1(mod100)\leftrightarrow 7x\equiv 343(mod100)[/tex]
[tex]7^{2}x\equiv 1(mod100)\leftrightarrow x\equiv 49(mod100)[/tex]
så de to sifrene er 49.
Re: Eulers teorem
Lagt inn: 08/07-2020 15:30
av Mattebruker
To oppgaver med same tema :
Bruk Euler's teorem til å
1) ..... avgjere om 531441 er deleleg med 3.
2) ..... finne resten når 52[tex]^{3}[/tex][tex]\cdot[/tex] 26 delast på 42.
Re: Eulers teorem
Lagt inn: 09/07-2020 13:51
av Mattebruker
Viser til oppgavene i førre innlegg. Desse er henta frå eit kapittel med overskrifta
Fermat's lille teorem og Euler's phi-funksjon
Meininga er , slik eg tolkar forfattaren , at oppgavene skal løysast med hjelp av verktøyet som kjem fram i overskrifta ( jamfør feit skrift ).
Greier ikkje å knekke denne koden, men har løyst oppgavene på " min måte " :
Vedk. oppgave 1 :
Undersøk om 531441 er deleleg med 3 [tex]\Leftrightarrow[/tex] Undersøk om 531441 [tex]\equiv[/tex] 0 ( mod 3 )
531441 = 5[tex]\cdot[/tex]10[tex]^{5}[/tex] + 3[tex]\cdot[/tex]10[tex]^{4}[/tex] +1[tex]\cdot[/tex]10[tex]^{3}[/tex]+ 4[tex]\cdot[/tex]10[tex]^{2}[/tex] + 4[tex]\cdot[/tex]10 + 1
Ser lett at 10 [tex]\equiv[/tex] 1 ( mod 3 )
531441 ( mod 3 ) = 5[tex]\cdot[/tex](10(mod 3))[tex]^{5}[/tex] + 3[tex]\cdot[/tex](10(mod 3 ))[tex]^{4}[/tex] +
1[tex]\cdot[/tex](10(mod 3 ))[tex]^{2}[/tex] + 4[tex]\cdot[/tex](10(mod 3 ))[tex]^{2}[/tex] + 1[tex]\cdot[/tex](10( mod 3))+1 = 5[tex]\cdot[/tex]1[tex]^{5}[/tex] + 3[tex]\cdot[/tex]1[tex]^{4}[/tex] +.......... + 1 = 5 + 3 + 1 + 4 + 4 +1( mod 3 ) = 18 ( mod 3 ) = (6[tex]\cdot[/tex]3 + 0 ) ( mod 3 ) = 0 ( mod 3 )
Svar: 531441 [tex]\equiv[/tex] 0 ( mod 3 ) [tex]\Leftrightarrow[/tex] 3 " deler " 5314441
Vedk. oppg. 2 :
Problem: Finn resten når 52[tex]^{3}[/tex][tex]\cdot[/tex]26 delast på 42
52[tex]^{3}[/tex][tex]\cdot[/tex]26 = 13[tex]^{4}[/tex][tex]\cdot[/tex]2[tex]^{7}[/tex]
2[tex]^{7}[/tex] ( mod 42 ) = ( 3[tex]\cdot[/tex] 42 + 2 ) ( mod 42 ) = 2
13[tex]^{2}[/tex] ( mod 42 ) = ( 4[tex]\cdot[/tex] 42 + 1 ) ( mod 42 ) = 1
13[tex]^{4}[/tex][tex]\cdot[/tex]2[tex]^{7}[/tex]( mod 42 ) = (13[tex]^{2}[/tex]( mod 42))[tex]^{2}[/tex] [tex]\cdot[/tex] 2[tex]^{7}[/tex]( mod 42 ) = 1[tex]^{2}[/tex][tex]\cdot[/tex]2 = 2
Til deg som måtte lese dette innlegget:
Ovanståande løysing(ar) verkar omstendeleg og tungvint.
Har ein mistanke om at " Fermat's lille " og/eller Euler's phi-funksjon gir ei enklare og langt meir elegant løysing.
Dersom du har ei kvalifisert meining om dette spørsmålet , vil eg vere takksam for ei tilbakemelding.
Re: Eulers teorem
Lagt inn: 09/07-2020 15:09
av Janhaa
Mattegjest skrev:To oppgaver med same tema :
Bruk Euler's teorem til å
1) ..... avgjere om 531441 er deleleg med 3.
2) ..... finne resten når 52[tex]^{3}[/tex][tex]\cdot[/tex] 26 delast på 42.
ang 1)
et tall a er delelig med 3, hvis tverrsummen til a er delelig med 3:
[tex]5+3+1+4+4+1 = 18[/tex]
og
[tex]18/3=6[/tex]
ergo:
[tex]531441 \equiv 0 \pmod{3}[/tex]
ellers:
[tex]3 \equiv 0 \pmod{3}[/tex]
[tex]3^6 \equiv 0 \pmod{3}[/tex]
[tex]3^{12}=531441 \equiv 0 \pmod{3}[/tex]
dog uten Euler's phi function & FLT
Re: Eulers teorem
Lagt inn: 17/08-2020 00:15
av Hege Baggethun2020
Mattegjest skrev:To oppgaver med same tema :
Bruk Euler's teorem til å
1) ..... avgjere om 531441 er deleleg med 3.
2) ..... finne resten når 52[tex]^{3}[/tex][tex]\cdot[/tex] 26 delast på 42.
Heisann,
jeg så ikke denne her før nå! Takk for at du postet denne - veldig artig, jeg prøver meg på oppgave 2. Her kan man bruke Eulers teorem og "law of quadratic reciprocity" (aner ikke hva sistnevnte er på norsk).
Jeg starter med [tex]2^{7}*13^4 (mod42)[/tex], som kan skrives [tex]2^{6}*13^{4}(mod21)[/tex], da [tex]gcd(2^{7}*13^{4},42)= 2[/tex].
[tex]21[/tex] er ikke et primtall. Benytter Euler totientfunksjonen for å finne [tex]\varphi (21)[/tex]. Vi får at [tex]\varphi (21)=\varphi (3)*\varphi(7)=2*6=12[/tex]. Nå kan vi bruke Eulers teorem, som gir [tex]2^{12}\equiv 1(mod21)[/tex]. Dette kan skrives som [tex](2^{6})^{^2}\equiv 1(mod21)[/tex]. Neste steg er å undersøke hvilke av de kvadratiske tallene modulo 21 som er kongruente med [tex]1(mod21)[/tex]. Det holder å sjekke tallene fra [tex]1[/tex] til [tex]\frac{21-1}{2}= 10[/tex] pga symmetri. Resultatet er [tex]\left \{ 1,4,9,16,4,15,7,1,18,16 \right \}(mod21)[/tex] hvilket betyr at [tex]X^{2}\equiv 1(mod21)[/tex] har løsningene [tex]X = 1, -1, 8, -8[/tex].
Siden [tex]2^3=8[/tex] så er [tex]2^{6}\equiv 1(mod21)[/tex]. Videre ser man at [tex]13\equiv -8(mod21)[/tex], hvilket gir [tex]13^4\equiv 1(mod21)[/tex]. Vi får da at [tex]2^{6}*13^{4}\equiv1*1(mod21)[/tex]. Multipliser begge sider med [tex]gcd= 2[/tex] og det endelige svaret på [tex]2^{7}*13^4 (mod42)[/tex] blir [tex]2(mod42)[/tex].
Mitt løsningsforslag var nok enda mer omstendelig enn jeg hadde ønsket... Jaja, det var en morsom oppgave!
Hilsen Hege.
Re: Eulers teorem
Lagt inn: 18/08-2020 06:22
av Gustav
Hege Baggethun2020 skrev:Her kan man bruke Eulers teorem og "law of quadratic reciprocity" (aner ikke hva sistnevnte er på norsk)
"Loven om kvadratisk resiprositet" på norsk
Re: Eulers teorem
Lagt inn: 18/08-2020 15:08
av Hege Baggethun2020
Gustav skrev:Hege Baggethun2020 skrev:Her kan man bruke Eulers teorem og "law of quadratic reciprocity" (aner ikke hva sistnevnte er på norsk)
"Loven om kvadratisk resiprositet" på norsk
Takk, Gustav! Det var ikke verre enn det, nei!