youproof.orgDeep Math. Human Access.

Bizonyítás

Tegyük fel ugyanis, hogy teljesül a p|a oszthatóság. Ekkor – mivel a p|p^k oszthatóság nyilvánvalóan teljesül – p egy közös osztója lesz a-nak és p^k-nak. Mivel a tétel szövege szerint p prím – és így a 16.13. Definíció szerint nem egység –, ezért a és p^k valóban nem lehetnek relatív prímek egymáshoz. Másként fogalmazva ha a és p^k relatív prímek egymáshoz, akkor valóban nem teljesülhet a p|a oszthatóság.

Visszafelé: Tegyük most fel, hogy a nem osztható p-vel, azaz p\nmid a. Azt kell igazolnunk, hogy ekkor a és p^k bármely közös osztója egység, mivel ez a 17.10. Definíció alapján épp azt jelenti, hogy ők relatív prímek egymáshoz. Legyen tehát d egy tetszőleges közös osztó, azaz d|a és d|p^k.

Vegyük észre, hogy ha valahogy igazolni tudnánk, hogy d és p relatív prímek, akkor d|p^k-ból az Euklidészi lemma ismételt alkalmazásával következnének az alábbi oszthatóságok:

\begin{aligned} d|\overbrace{p\cdot p^{k-1}}^{=p^k} &\implies d|p^{k-1} \\ d|\overbrace{p\cdot p^{k-2}}^{=p^{k-1}} &\implies d|p^{k-2} \\ d|\overbrace{p\cdot p^{k-3}}^{=p^{k-2}} &\implies d|p^{k-3} \\ &\vdots \\ d|\overbrace{p\cdot p}^{=p^2} &\implies d|p \\ d|\overbrace{p\cdot 1}^{=p} &\implies d|1 \end{aligned}

Vagyis végsősoron d és p relatív prímségéből megkapnánk, hogy a tetszőlegesen választott d közös osztó valóban egység. A d és p relatív prímségének igazolását alább részletezzük.

Miért relatív prím d és p?

Mivel nyilván d|a – hiszen d az a és p^k közös osztója –, ezért p\nmid d, máskülönben p|d-ből d|a mellett a 16.2. Tétel 5. pontja miatt p|a következne, amiről feltettük, hogy nem igaz. Jegyezzük meg tehát, hogy p\nmid d, mert hamarosan szükségünk lesz erre.

Most vizsgáljuk meg d és p valamely tetszőleges c közös osztóját, amiről tehát meg kell mutatnunk, hogy szükségképpen egység. Mivel c közös osztó, ezért teljesülnek a c|d és a c|p oszthatóságok. A c|p oszthatóság a 16.1. Definíció alapján azt jelenti, hogy létezik olyan q egész szám, amelyre teljesül az alábbi egyenlet:

p=cq

Ám ekkor a 16.2. Tétel 1. pontja miatt nyilván teljesül a p|cq oszthatóság, és így p prímtulajdonsága miatt teljesül az alábbi oszthatóságok közül legalább az egyik:

\begin{aligned} p&|c \\ p&|q \end{aligned}

Igenám, de p|c nem teljesülhet, mivel ekkor c|d mellett a 16.2. Tétel 5. pontja miatt p|d következne, amiről már igazoltuk, hogy lehetetlen. Így tehát szükségképpen teljesül p|q, ami a 16.1. Definíció alapján azt jelenti, hogy létezik olyan r egész szám, amelyre teljesül az alábbi egyenlet:

q=pr

A q-ra kapott kifejezést behelyettesítve az első egyenletbe ezt kapjuk:

p=c\underbrace{pr}_{=q}

Minthogy p prím, ezért nem 0, és így a 15.4. Tétel alapján lehet egyszerűsíteni vele:

1=cr

Ez a 16.1. Definíció alapján azt jelenti, hogy c|1, tehát c a 16.5. Tétel szerint valóban egység.

∎