Eulers teorem

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Hege Baggethun2020
Noether
Noether
Innlegg: 37
Registrert: 13/06-2020 23:21

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.)
[tex]\sum_{y<n\leq x}a(n)f(n) = A(x)f(x)-A(y)f(y)-\int_{y}^{x}A(t)f'(t)dt[/tex]
eulers sønn

FASIT: 29 og 49
Janhaa
Boltzmann
Boltzmann
Innlegg: 8552
Registrert: 21/08-2006 03:46
Sted: Grenland

[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]
La verken mennesker eller hendelser ta livsmotet fra deg.
Marie Curie, kjemiker og fysiker.

[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
Janhaa
Boltzmann
Boltzmann
Innlegg: 8552
Registrert: 21/08-2006 03:46
Sted: Grenland

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]
La verken mennesker eller hendelser ta livsmotet fra deg.
Marie Curie, kjemiker og fysiker.

[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
Hege Baggethun2020
Noether
Noether
Innlegg: 37
Registrert: 13/06-2020 23:21

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].
[tex]\sum_{y<n\leq x}a(n)f(n) = A(x)f(x)-A(y)f(y)-\int_{y}^{x}A(t)f'(t)dt[/tex]
Hege Baggethun2020
Noether
Noether
Innlegg: 37
Registrert: 13/06-2020 23:21

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.
[tex]\sum_{y<n\leq x}a(n)f(n) = A(x)f(x)-A(y)f(y)-\int_{y}^{x}A(t)f'(t)dt[/tex]
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.
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.
Janhaa
Boltzmann
Boltzmann
Innlegg: 8552
Registrert: 21/08-2006 03:46
Sted: Grenland

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
La verken mennesker eller hendelser ta livsmotet fra deg.
Marie Curie, kjemiker og fysiker.

[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
Hege Baggethun2020
Noether
Noether
Innlegg: 37
Registrert: 13/06-2020 23:21

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.
Sist redigert av Hege Baggethun2020 den 19/08-2020 19:35, redigert 1 gang totalt.
[tex]\sum_{y<n\leq x}a(n)f(n) = A(x)f(x)-A(y)f(y)-\int_{y}^{x}A(t)f'(t)dt[/tex]
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

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 :D
Hege Baggethun2020
Noether
Noether
Innlegg: 37
Registrert: 13/06-2020 23:21

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 :D
Takk, Gustav! Det var ikke verre enn det, nei! :lol:
[tex]\sum_{y<n\leq x}a(n)f(n) = A(x)f(x)-A(y)f(y)-\int_{y}^{x}A(t)f'(t)dt[/tex]
Svar