Fölérendelt lap:21.5. TételAz Euler-függvény értéke prímhatványokra

Bizonyítás

A $\varphi(p^k)$ a 20.18. Következmény alapján a $0$ , $1$ , $2$ , ..., $p^k-1$ közül a $p^k$ -hoz relatív prímek számát adja meg. Nincs más dolgunk tehát, mint ezeket megszámlálni. A 21.4. Lemma szerint egy tetszőleges $a$ egész szám akkor és csak akkor relatív prím $p^k$ -hoz, ha nem osztható $p$ -vel.

Ahhoz tehát, hogy megkapjuk $\varphi(p^k)$ értékét, meg kell számolnunk, hogy összesen hány $p$ -vel osztható egész szám van az első $p^k$ darab pozitív egész szám között. A 21.4. Lemma alapján ugyanis épp az ezeken kívüli számok lesznek relatív prímek $p^k$ -hoz. A $p$ -vel osztható számok ebben a tartományban az alábbiak lesznek:

\begin{aligned}1&\cdot p \\ 2&\cdot p \\ 3&\cdot p \\ &\vdots \\ p^{k-1}&\cdot p\end{aligned}

Ezek száma tehát összesen $p^{k-1}$ . Ezt levonva $p^k$ -ból valóban $\varphi(p^k)$ értékét kapjuk, ahogyan a tétel állítja:

\varphi(p^k)=p^k-p^{k-1}

Végül a speciális eset: A $\varphi(p)$ a 20.18. Következmény alapján a $0$ , $1$ , $2$ , ..., $p-1$ számok közül a $p$ -hez relatív prímek számát adja meg. Ezt ugyanúgy a 21.4. Lemma alapján tudjuk megszámlálni: megszámláljuk, hogy hány $p$ -vel osztható van ezek között, majd ezt levonjuk a darabszámukból, ami ugye $p$ .

A $0$ biztosan osztható $p$ -vel a 16.2. Tétel 3. pontja miatt. A felsorolt további számok közül viszont egyik sem osztható $p$ -vel. Tegyük fel ugyanis indirekt, hogy nem ez a helyzet, vagyis létezik olyan $r$ közöttük, hogy $p|r$ . Ebből a 17.2. Lemma alapján $p\leq r$ következne, ami ellentmondás.

Mivel tehát a $0$ , $1$ , $2$ , ..., $p-1$ számok közül csak a $0$ volt osztható $p$ -vel, így a 21.4. Lemma alapján valóban a maradék $p-1$ darab szám lesz relatív prím $p$ -hez, azaz:

\varphi(p)=p-1

∎

Iratkozz fel a hírlevelünkre