Eulers sats

Tjenare 

Satsen säger bara att $a^{\varphi \left(n\right)}=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^{\varphi \left(8\right)}(mod 8)=4^4=256=0(mod 8)$ , satsen gäller inte för att 2 delar båda 4 och 8 alltså sgd(8,4)=2

Kallaskull skrev:

Tjenare 

Satsen säger bara att $a^{\varphi \left(n\right)}=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^{\varphi \left(8\right)}(mod 8)=4^4=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? =(

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.

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 $\varphi \left(4\right)$? 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å $\varphi \left(4\right)=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å $\varphi \left(8\right)=4$

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(2^3)=(2-1)*2^(3-1)=4$

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

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(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 $\varphi \left(a^b\right)=a^{b-1}·\varphi \left(a\right)$

$\varphi \left(2^3\right)=2^{3-1}·\varphi \left(2\right)=4·1=4$

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

Kallaskull skrev:

sannakarlsson1337 skrev:

Visa föregående citat

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(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 $\varphi \left(a^b\right)=a^{b-1}·\varphi \left(a\right)$

$\varphi \left(2^3\right)=2^{3-1}·\varphi \left(2\right)=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^{\phi(8)} \mod 8 = 4^4 = .....$

Ifall du menar att det var så jag fick $4^{\varphi \left(8\right)}=4^4$ så ja. Btw tog bara det exemplet för att vissa en situation där euler sats inte gäller

Kallaskull skrev:

Ifall du menar att det var så jag fick $4^{\varphi \left(8\right)}=4^4$ 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?

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.

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 \cdot 1000$ Alltså gäller 
$3^{4000} = 3^{4 \cdot 1000} = (3^4)^{1000}$ så inom parentesen där, applicerar vi mod 8 eller? å får då $1^{1000}$ ? 

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

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å

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 $13^{120001} \mod 61$ då kan man inte använda den här satsen? (vad använder man då?)

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 $\varphi \left(61\right)=60$ eftersom den är prim och sen så ${13}^{120001}={13}^{120000}·3^1={13}^{60·2000}·{13}^1={\left({13}^{60}\right)}^{2000}·13$

 och enligt Eulers sats har vi ${13}^{\varphi \left(61\right)}={13}^{60}=1(mod 61)$alltså får vi ${\left({13}^{60}\right)}^{2000}·13={\left(1\right)}^{2000}·13=13(mod 61)$

så svaret är ${13}^{120001}=13(mod 61)$

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 $\varphi \left(61\right)=60$ eftersom den är prim och sen så ${13}^{120001}={13}^{120000}·3^1={13}^{60·2000}·{13}^1={\left({13}^{60}\right)}^{2000}·13$

 och enligt Eulers sats har vi ${13}^{\varphi \left(61\right)}={13}^{60}=1(mod 61)$alltså får vi ${\left({13}^{60}\right)}^{2000}·13={\left(1\right)}^{2000}·13=13(mod 61)$

så svaret är ${13}^{120001}=13(mod 61)$

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

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

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 $\varphi \left(n\right)$ä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å $\varphi \left(6\right)=2$

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

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

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 $\varphi \left(61\right)=60$ eftersom den är prim och sen så ${13}^{120001}={13}^{120000}·3^1={13}^{60·2000}·{13}^1={\left({13}^{60}\right)}^{2000}·13$

 och enligt Eulers sats har vi ${13}^{\varphi \left(61\right)}={13}^{60}=1(mod 61)$alltså får vi ${\left({13}^{60}\right)}^{2000}·13={\left(1\right)}^{2000}·13=13(mod 61)$

så svaret är ${13}^{120001}=13(mod 61)$

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

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

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