17 svar
845 visningar
sannakarlsson1337 590
Postad: 17 apr 2020 12:19 Redigerad: 17 apr 2020 12:19

Eulers sats

  • det jag tolkar från detta är att det som är inom phi, är mod vi jobbar med.
  • i SGD(m,b) = 1
  • phi(m) = x

för är det samma m, eller är det bara slumpen som blev av här?

 

tänker om den generella hade varit då

 

bxmodmb^x \mod m


Jag hängde inte med på satsen, när man blandade in SGD...

Kallaskull 692
Postad: 17 apr 2020 13:04

Tjenare 

Satsen säger bara att aϕ(n)=1(mod n) där phi är eulers phi funktion, sgd(a,n)=1 alltså a och n inte har en gemensam faktor(utom såklart 1) som exemplet 3 och 8.

Ifall vi hade haft 4ϕ(8)(mod 8)=44=256=0(mod 8) , satsen gäller inte för att 2 delar båda 4 och 8 alltså sgd(8,4)=2

sannakarlsson1337 590
Postad: 17 apr 2020 13:19
Kallaskull skrev:

Tjenare 

Satsen säger bara att aϕ(n)=1(mod n) där phi är eulers phi funktion, sgd(a,n)=1 alltså a och n inte har en gemensam faktor(utom såklart 1) som exemplet 3 och 8.

Ifall vi hade haft 4ϕ(8)(mod 8)=44=256=0(mod 8) , satsen gäller inte för att 2 delar båda 4 och 8 alltså sgd(8,4)=2

var fick du ^4 ifrån? =(

parveln 703 – Fd. Medlem
Postad: 17 apr 2020 13:32

phi(8)=phi(2^3)=(2-1)*2^(3-1)=4. Alternativt kan du bara kolla hur många tal under 8 som är relativt prima 8.

Kallaskull 692
Postad: 17 apr 2020 13:38

Det är euler-phi funktionens värde för 8.

Euler phi funktionen för ett tal n är antalet tal mindre än och lika med n som inte har en gemensam delare med n. Låt oss ta ett exempel 

vad är ϕ(4)? vi har 1,2,3,4 som är mindre än eller lika med 4, vilka av dessa har gemensamma delare med 4? Endast 2 och 4 har det med sgd(4,2)=2 och sgd(4,4)=4 alltså ϕ(4)=2

Med 8 har vi sgd(8,2)=2, sgd(8,4)=4, sgd(8,6)=3,2 och sist sgd(8,8)=8 alltså ϕ(8)=4

sannakarlsson1337 590
Postad: 17 apr 2020 13:42
parveln skrev:

phi(8)=phi(2^3)=(2-1)*2^(3-1)=4. Alternativt kan du bara kolla hur många tal under 8 som är relativt prima 8.

phi(8)=phi(23)=(2-1)*2(3-1)=4phi(8)=phi(2^3)=(2-1)*2^(3-1)=4

hur blev det i andra steget, 2-1? vad dum jag känner mig. 

Kallaskull 692
Postad: 17 apr 2020 13:54 Redigerad: 17 apr 2020 13:56
sannakarlsson1337 skrev:
parveln skrev:

phi(8)=phi(2^3)=(2-1)*2^(3-1)=4. Alternativt kan du bara kolla hur många tal under 8 som är relativt prima 8.

phi(8)=phi(23)=(2-1)*2(3-1)=4phi(8)=phi(2^3)=(2-1)*2^(3-1)=4

hur blev det i andra steget, 2-1? vad dum jag känner mig. 

tror Parveln använder sig av euler phi funktionens egenskaper ϕ(ab)=ab-1·ϕ(a)

ϕ(23)=23-1·ϕ(2)=4·1=4

(Normalt att känna sig dum i huve när man gör matte, jag gör det också, lol)

sannakarlsson1337 590
Postad: 17 apr 2020 14:03 Redigerad: 17 apr 2020 14:03
Kallaskull skrev:
sannakarlsson1337 skrev:
parveln skrev:

phi(8)=phi(2^3)=(2-1)*2^(3-1)=4. Alternativt kan du bara kolla hur många tal under 8 som är relativt prima 8.

phi(8)=phi(23)=(2-1)*2(3-1)=4phi(8)=phi(2^3)=(2-1)*2^(3-1)=4

hur blev det i andra steget, 2-1? vad dum jag känner mig. 

tror Parveln använder sig av euler phi funktionens egenskaper ϕ(ab)=ab-1·ϕ(a)

ϕ(23)=23-1·ϕ(2)=4·1=4

(Normalt att känna sig dum i huve när man gör matte, jag gör det också, lol)

Och den 4an vi får ut, det är den som är ^4 i det du skrev aϕ(8)mod8=44=.....a^{\phi(8)} \mod 8 = 4^4 = .....

Kallaskull 692
Postad: 17 apr 2020 14:26

Ifall du menar att det var så jag fick 4ϕ(8)=44 så ja. Btw tog bara det exemplet för att vissa en situation där euler sats inte gäller

sannakarlsson1337 590
Postad: 17 apr 2020 14:27
Kallaskull skrev:

Ifall du menar att det var så jag fick 4ϕ(8)=44 så ja. Btw tog bara det exemplet för att vissa en situation där euler sats inte gäller

Precis, för att vi fick = 0 i slutet när vi applicerade mod 8.. right?

Kallaskull 692
Postad: 17 apr 2020 14:58

Yesbox det är rätt, igen ville bara vissa att Euler sats inte funka här för att 4 och 8 har en gemensam delare 2.

sannakarlsson1337 590
Postad: 17 apr 2020 15:03
Kallaskull skrev:

Yesbox det är rätt, igen ville bara vissa att Euler sats inte funka här för att 4 och 8 har en gemensam delare 2.

vad bra! =D

Men när dom pratar om att vi har att 4000=4·10004000=4 \cdot 1000 Alltså gäller 
34000=34·1000=(34)10003^{4000} = 3^{4 \cdot 1000} = (3^4)^{1000} så inom parentesen där, applicerar vi mod 8 eller? å får då 110001^{1000}

det är bara ett annat exempel me samma tal, eller hänger dom ihop?

Kallaskull 692
Postad: 17 apr 2020 15:06

Yesbox inom parantesen applicerar vi mod 8 helt rätt!

Skulle säga det bara är ett exempel på hur satsen kan användas, med samma tal så det blir lättare att föstå

sannakarlsson1337 590
Postad: 17 apr 2020 15:34
Kallaskull skrev:

Yesbox inom parantesen applicerar vi mod 8 helt rätt!

Skulle säga det bara är ett exempel på hur satsen kan användas, med samma tal så det blir lättare att föstå

Vad bra! =D 
Men det fungerar bara om de är prima (koprima?) för jag sitter med ett annat tal, som inte är primtal 13120001mod6113^{120001} \mod 61 då kan man inte använda den här satsen? (vad använder man då?)

Kallaskull 692
Postad: 17 apr 2020 15:42

I detta fall kan vi göra såhär

Först 61 och 13 är coprim, båda två är till och med primtal!

Först ϕ(61)=60 eftersom den är prim och sen så 13120001=13120000·31=1360·2000·131=13602000·13

 och enligt Eulers sats har vi 13ϕ(61)=1360=1(mod 61)alltså får vi 13602000·13=12000·13=13(mod 61)

så svaret är 13120001=13(mod 61)

sannakarlsson1337 590
Postad: 17 apr 2020 16:12
Kallaskull skrev:

I detta fall kan vi göra såhär

Först 61 och 13 är coprim, båda två är till och med primtal!

Först ϕ(61)=60 eftersom den är prim och sen så 13120001=13120000·31=1360·2000·131=13602000·13

 och enligt Eulers sats har vi 13ϕ(61)=1360=1(mod 61)alltså får vi 13602000·13=12000·13=13(mod 61)

så svaret är 13120001=13(mod 61)

Men ϕ(61)=60\phi(61)=60 är från $$\phi(a^b) =  a^{b-1} \cdot \phi(a)$$

förlåt om jag är trög.

Kallaskull 692
Postad: 17 apr 2020 17:13

Du är inte de minsta trög, flera personer har skrivit i denna tråd och okända(som jag antar du inte kände till inan) formler har använts naturligt att vara förvirad.

Vet inte om du går på högskola, gör detta för skojs skull(som mig), eller någon blanding. Ifall du har anteckningar eller en bok kolla på Eulers totient funktion igen och kolla om de löser sig, annars kan du googla och kolla runt.

Okej väldigt grund nu. Eulers totient funktion ϕ(n)är antalet tal mindre än n som är co-prim till n(skrev fel på detta förut). Co-prim betyder att de inte har några gemensamma delare(förutom 1)

Ifall vi tar exemplet 6 så har vi talen 1,2,3,4,5 som vi måste kolla, här är 6 och 1 samt 6 och 5 co-prim alltså ϕ(6)=2

Ifall vi tar t.ex 10 får vi att talen som är co-prim är 1,3,7, och 9 alltså är ϕ(10)=4, fattar du typ hur Euler totient funktionen funkar?

Sist, ifall vi har ett primtal P så kommer ϕ(P)=P-1 eftersom primtal defineras som tal vars alla mindre tal är co-prim och 61 är ett primtal alltså ϕ(61)=61-1=60

Laguna Online 30255
Postad: 17 apr 2020 17:16 Redigerad: 17 apr 2020 17:16
sannakarlsson1337 skrev:
Kallaskull skrev:

I detta fall kan vi göra såhär

Först 61 och 13 är coprim, båda två är till och med primtal!

Först ϕ(61)=60 eftersom den är prim och sen så 13120001=13120000·31=1360·2000·131=13602000·13

 och enligt Eulers sats har vi 13ϕ(61)=1360=1(mod 61)alltså får vi 13602000·13=12000·13=13(mod 61)

så svaret är 13120001=13(mod 61)

Men ϕ(61)=60\phi(61)=60 är från ϕ(ab)=ab-1·ϕ(a)\phi(a^b) = a^{b-1} \cdot \phi(a)

förlåt om jag är trög.

Sätter du in 611 i formeln så får du tillbaka ϕ(61)\phi(61). En mer grundläggande egenskap hos phi-funktionen är att ϕ(n)=n-1\phi(n) = n-1 om n är ett primtal.

Svara
Close