matematikk.net

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.)

FASIT: 29 og 49

[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]

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]

Janhaa wrote:[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].

Janhaa wrote: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.

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.

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.

Mattegjest wrote: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

Mattegjest wrote: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.

Hege Baggethun2020 wrote:Her kan man bruke Eulers teorem og "law of quadratic reciprocity" (aner ikke hva sistnevnte er på norsk)

"Loven om kvadratisk resiprositet" på norsk

Gustav wrote:

Hege Baggethun2020 wrote: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!