Eurlers funktion

Eulers fi-funktion av ett heltal $n\geq1$ beskriver hur många naturliga tal mindre än eller lika med $n$ som är relativt prima med $n$. Om vi tar $n=3$ skall vi alltså undersöka hur många av talen $1$, $2$ och $3$ som är relativt prima med $3$, d.v.s. ifall $\text{sgd}(x,3)$ är lika med $1$. I detta fall får vi att $\text{sgd}(1,3)$ och $\text{sgd}(2,3)$ är lika med $1$, alltså får vi att $\phi(3)=2$.

Vad är det som är otydligt? De tal som är "coprime to $n$" är alla tal som saknar gemensamma faktorer med $n$. Om $n$ ä rett primtal, är alltså alla heltal som är mindre än $n$ koprima. Om $n=6$ så är inte 2, 3 eller 4 koprima med 6, eftersom både 2 och 3 är faktorer i 6 (och eftersom 2 är en faktor i 4).

AlvinB skrev:

Eulers fi-funktion av ett heltal $n\geq1$ beskriver hur många naturliga tal mindre än eller lika med $n$ som är relativt prima med $n$. Om vi tar $n=3$ skall vi alltså undersöka hur många av talen $1$, $2$ och $3$ som är relativt prima med $3$, d.v.s. ifall $\text{sgd}(x,3)$ är lika med $1$. I detta fall får vi att $\text{sgd}(1,3)$ och $\text{sgd}(2,3)$ är lika med $1$, alltså får vi att $\phi(3)=2$.

Ahh okej, så formeln är sgd(x,n) där n är de man ska kolla :)

tack så mkt!

En översättning av del av texten lyder:

Kom ihåg att två heltal $x$ och $y$ är relativt prima om $sgd(x,y)=1$; för varje $n\geq 1$ betecknar $\phi(n)$ antalet heltal $x$ i spannet $1 \leq x \leq n$ som är relativt prima till $n$.

Notera att om n är ett primtal så är $sgd(n,x)=1$ för alla tal $x$ i spannet $1 \leq x \leq n$, utom för det sista talet $n$ eftersom $sgd(n,n) = n$; det betyder att $\phi(n) = n-1$ och detta är också det största möjliga värde som $\phi(n)$ kan anta för ett givet $n$, primtal eller ej. 

Fråga: Om $\phi(n) = n-1$, betyder det då att $n$ är ett primtal?