Euler fi funktion.

Eulers fifunktion $\varphi(n)$ definieras som antalet tal som saknar gemensamma delare med $n$ andra än 1, dvs att talen är relativt prima eller ekvivalent $sgd(x, n) = 1$

Den enklaste metoden är att löpa igenom alla tal $1, ..., n$ och se hur många som saknar gemensamma delare. Exempelvis för n = 10 har vi

1 (ja), 2 (nej eftersom sgd(2,10) = 2), 3 (ja), 4 (nej), 5(nej), 6 (nej), 7 (ja), 8 (nej), 9 (ja), 10 (nej)

Alltså $\varphi(10) = 4$ pga 1,3,7,9 är relativt prima 10.

Annars kan man även använda primtalsfaktoriseringen https://en.wikipedia.org/wiki/Euler%27s_totient_function 

SeriousCephalopod skrev:

Eulers fifunktion $\varphi(n)$ definieras som antalet tal som saknar gemensamma delare med $n$ andra än 1, dvs att talen är relativt prima eller ekvivalent $sgd(x, n) = 1$

Den enklaste metoden är att löpa igenom alla tal $1, ..., n$ och se hur många som saknar gemensamma delare. Exempelvis för n = 10 har vi

1 (ja), 2 (nej eftersom sgd(2,10) = 2), 3 (ja), 4 (nej), 5(nej), 6 (nej), 7 (ja), 8 (nej), 9 (ja), 10 (nej)

Alltså $\varphi(10) = 4$ pga 1,3,7,9 är relativt prima 10.

Annars kan man även använda primtalsfaktoriseringen https://en.wikipedia.org/wiki/Euler%27s_totient_function 

så fi(n) är det alltså så jag har fi(20) då ska jag hitta sgd(x,20)=1 ?

Vet du vad eulers fi funktion ger för resultat?
"Om n är ett positivt heltal, då definieras φ(n) som antalet positiva heltal mindre än eller lika med n som är relativt prima med n. Till exempel är φ(8) = 4 eftersom de fyra talen 1, 3, 5 och 7 är relativt prima till 8. "

För fi(20) kan du lätt göra detta för hand (bara så du har ett facit).  Talen blir 1,3,7,9,11,13,17,19 så svaret är 8

Men för att räkna ut det kan man använda en av flera formler.
Du kanske tänker på:
φ ( m g n ( m , n ) ) ⋅ φ ( s g d ( m , n ) ) = φ ( m ) ⋅ φ ( n )
Det funkar såklart.

Men annars kan du använda φ(2m)=2φ(m)     (vilket gäller för jämna m
Så ...   φ(20)=φ(2*10)=2*φ(10)   och att φ(10)=4 vet du kanske. Annars kan du fortsätta med:
φ(2m)=φ(m) som gäller när m är udda så... φ(10)=φ(2*5)=φ(5)=4     (som du bara måste veta)
Observera de olika formlerna beroende på om m är jämnt eller udda.

Så du har φ(20)=2*φ(10)=2*φ(5)=2*4=8

joculator skrev:

Vet du vad eulers fi funktion ger för resultat?
"Om n är ett positivt heltal, då definieras φ(n) som antalet positiva heltal mindre än eller lika med n som är relativt prima med n. Till exempel är φ(8) = 4 eftersom de fyra talen 1, 3, 5 och 7 är relativt prima till 8. "

För fi(20) kan du lätt göra detta för hand (bara så du har ett facit).  Talen blir 1,3,7,9,11,13,17,19 så svaret är 8

Men för att räkna ut det kan man använda en av flera formler.
Du kanske tänker på:
φ ( m g n ( m , n ) ) ⋅ φ ( s g d ( m , n ) ) = φ ( m ) ⋅ φ ( n )
Det funkar såklart.

Men annars kan du använda φ(2m)=2φ(m)     (vilket gäller för jämna m
Så ...   φ(20)=φ(2*10)=2*φ(10)   och att φ(10)=4 vet du kanske. Annars kan du fortsätta med:
φ(2m)=φ(m) som gäller när m är udda så... φ(10)=φ(2*5)=φ(5)=4     (som du bara måste veta)
Observera de olika formlerna beroende på om m är jämnt eller udda.

Så du har φ(20)=2*φ(10)=2*φ(5)=2*4=8

Varför flyter man just ut 2:an, här φ(20)=φ(2*10)=2*φ(10)    ? är det för 2 är ett primtal?

Det är alltid 2:an som "flyttas ut", det är så formeln ser ut. Den fungerar bara för φ(2m)
Den fungear alltså inte för 3m eller liknande.

joculator skrev:

Det är alltid 2:an som "flyttas ut", det är så formeln ser ut. Den fungerar bara för φ(2m)
Den fungear alltså inte för 3m eller liknande.

Men om vi hade fi(21) då? kan man tänka då 3*fi(7) ? 

men ... som jag skrev, det MÅSTE vara på formen fi(2*m)  som då är lika med 2*fi(m)    (om m är jämnt) 
3*7 är inte på formen 2*m, alltså kan du inte använda den formeln då och det finns ingen formel för fi(3*m)

Formlerna som joculator skrev fungerar eftersom φ(2)=1 och man kan multiplicera med 1 så mycket men vill utan att förändra uttryckets värde.

joculator skrev:

men ... som jag skrev, det MÅSTE vara på formen fi(2*m)  som då är lika med 2*fi(m)    (om m är jämnt) 
3*7 är inte på formen 2*m, alltså kan du inte använda den formeln då och det finns ingen formel för fi(3*m)

Men om man har då tex fi(21) som inte är ett primtal och inte dividerbar med 2, 

då kan man primtalsfaktorisera i det här fallet 21=7*3 och hitta 

sgd(x,7)=1 och sgd(x,3)=1 eller?