Lankide:Pedrosa.lucas/Proba orria

EULERREN φ FUNTZIOA

Eulerren φ funtzioa (Eulerren funtzio adierazlea edo funtzio osoa ere deitzen zaio) funtzio garrantzitsua da zenbakien teorian. n zenbaki oso positibo bat bada, orduan φ(n) honela definitzen da: n>1 denean, n baino txkiagoak diren zenbakiak beraien artean elkarrekiko lehenak direnak kontatzen ditu.

Edozein zanbakiren φ(n) kalkulatzeko aritmetikaren oinarrizko teoremarekin kalkula daiteke:

Baldin eta $n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}p_{3}^{\alpha _{3}}...p_{k}^{\alpha _{k}}$ non pi-ak zenbaki lehenak ezberdinak diren, orduan, $\varphi (n)={\bigl (}p_{1}-1{\bigr )}p_{1}^{k_{1}-1}...{\bigl (}p_{k}-1{\bigr )}p_{k}^{k_{k}-1}$ formula hau Euleeren biderketa deritzo eta normalean

$\varphi (n)=n\prod _{p\mid n}\displaystyle {\Biggl (}1-\left({\frac {1}{p}}\right){\Biggr )}$ idazten da, non p dira lehen desberdinak n zatitzen dutenak.

φ(n)-ren lehen mila balioak

Adibidez:

φ(1)=1

φ(2)=2

φ(3)=2

φ(4)=4

φ(n)= I{a

φ(n) = Card{k ∈ N : k ≤ n, zkh(k, n)=1}

PROPIETATEAK

1. $\varphi$(p)=p-1 p lehena bada
2. $\varphi$($p^{k}$) = $p^{k}$ − $p^{k+1}$
3. $\varphi$(mn)= $\varphi$(m)$\varphi$(n)

Frogapenak:

1)   Zenbaki lehen (p) bat aurreko guztiekin elkarrekiko lehenak dira, orduan existitzen dira p-1 dira p-rekin elkarrekiko lehenak direnak.

2)   Baldin eta $\varphi$($p^{k}$) zenbat den jakiteko {1,….,$p^{k}$} multzoan zenbat elementu diren p-rekin elkarekiko lehenak jakin behar dugu. Multzo horretako elementu guztiak hartuko ditugu p-ren multiploak direnak izan ezin. Multzo horretan p-ren multiploak direnak pberkp izango da, hau da $p^{k+1}$. Beraz, $\varphi$($p^{k}$)=$p^{k}$- $p^{k+1}$

3) Frogapen honetarako, hasteko, dakigu

$\varphi (n)=n\prod _{pi\mid n}\displaystyle {\Biggl (}1-\left({\frac {1}{pi}}\right){\Biggr )}$

pi lehena da, beraz:

$\varphi (n)\varphi (m)=mn\prod _{pi\mid n}{\Biggl (}1-\left({\frac {1}{pi}}\right){\Biggr )}\prod _{qi\mid n}{\Biggl (}1-\left({\frac {1}{pi}}\right){\Biggr )}$

zkh(n,m)=1 denez, orduan ez pi ez qi ez direnez berdinak eta mn deskonposaketa ez da afektztzen hau da:$m=q_{1}^{\beta _{1}}q_{2}^{\beta _{2}}q_{3}^{\beta _{3}}...q_{k}^{\beta _{k}}$ eta $n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}p_{3}^{\alpha _{3}}...p_{k}^{\alpha _{k}}$ orduan, lehenen deskonposaketa$mn=q_{1}^{\beta _{1}}q_{2}^{\beta _{2}}q_{3}^{\beta _{3}}...q_{k}^{\beta _{k}}p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}p_{3}^{\alpha _{3}}...p_{k}^{\alpha _{k}}$. Orduan hau inplatzen du $\varphi (n)\varphi (m)=mn\prod _{pi\mid n}{\Biggl (}1-\left({\frac {1}{pi}}\right){\Biggr )}\prod _{qi\mid n}{\Biggl (}1-\left({\frac {1}{pi}}\right){\Biggr )}$ betetzea.

HISTORIA

Leonhard Eulerrek 1763an sartu zuen funtzioa. Hala ere, une horretan ez zuen sinbolo berezirik aukeratu hura denotatzeko. 1784ko argitalpen batean, Eulerrek sakonago aztertu zuen funtzioa, eta π letra grekoa aukeratu zuen hura denotatzeko: πD idatzi zuen "D baino zenbaki txikiagoak eta berarekin zatitzaile komunik ez dutenak" idazteko.

Definizio hori aldatu egiten da D= 1 funtzioaren egungo definizioaren arabera, baina, gainerakoan, funtzio bera da. φ(A) notazio estandarra Carl Friedrich Gauss-en 1801 Disquisitiones arithmeticae tratatutik dator, nahiz eta Gauss-ek ez zuen parentesirik erabili argumentuaren inguruan, eta φA idatzi zuen. Beraz, sarritan Eulerren phi funtzioa edo phi funtzioa deitzen zaio.

1879an, J. J. Sylvesterrek funtzio horretarako termino totientea asmatu zuen, eta Eulerren funtzio totiente edo Eulerren totiente ere deitzen zaio. Eulerren ideia orokortzea da Jordanen totientea. n-ren kobotientea n-φ(n) gisa definitzen da. n baino txikiagoak edo berdinak diren osoko positiboen kopurua kontatzen du, n duten faktore lehenetsi komun bat gutxienez dutenak.

EULERREN TEOREMA

Fermat-en teorema txikiaren orkortze gisa hartu da. Eulerrek teorema honen bidez baieztatzen du zenbaki osoen zatigarritasuna:

a eta n zenbakiak ditugu beraien arteko elkarrekiko lehenak direnak, orduan n zatitu dezake $a^{\varphi (n)}-1$ . Hau beste modu batean emanda aritmetika modularrarekin, $a^{\varphi (n)}\equiv {\pmod {n}}$. Bi formuletan Eulerren funtzioa barruan dauka.

Eulerren teoremaren frogapena honako hau da:

Izan bedi $R=\{r_{1},r_{2},...,r_{\varphi (n)}\}$ hondarra-sesitema murriztu bat, n moduluan. Egiterakoan a$R$ barrukoak bider a eginda hondarra-sistema murriztua modulu n-an izaten jarraituko du. Orduan, $aR=\{ar_{1},ar_{2},...,ar_{\varphi (n)}\}.$ Beraien artean biderketa eginez, $r_{1}r_{2}...r_{\varphi (n)}\equiv a^{\varphi (n)}r_{1}r_{2}...r_{\varphi (n)}{\pmod {n}}$. $r_{i}$ bakoitzk betetzen duenez $zkh(r_{i},n)=1$, orduan $a^{\varphi (n)}\equiv {\pmod {n}}$ da.