Eulerren φ funtzioa

Eulerren φ funtzioa, Eulerren funtzio adierazlea edo Eulerren funtzio osoa 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.

Adibidez:

φ(1)=1

φ(2)=2

φ(3)=2

φ(4)=4

φ(n)= I{a

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

Propietateak

$\varphi$ (p)=p-1 p lehena bada
$\varphi$ ( $p^{k}$ ) = $p^{k}$ − $p^{k+1}$
$\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.

Beste propietate batzuk

$n$ zenbakiaren zatitzaileak $\{d_{1}=1,d_{2},d_{3},...,d_{k}=n\}$ badira, orduan: $\varphi (d_{1})+\varphi (d_{2})+...+\varphi (d_{k})=n$

Adibidez: $\varphi (1)+\varphi (2)+\varphi (4)+\varphi (5)+\varphi (10)+\varphi (20)=1+1+2+4+4+8=20$

Carl Friedrich Gauss matematikariak propietate hau egiaztatu zuen Disquisitiones Arithmeticae liburuan

$n$ -rekin elkarren arteko lehenak diren zenbakien batura, hau da, $\varphi (n)$ -k kontatzen dituen elementuen batura ${\frac {n\varphi (n)}{2}}$ da.

Adibidez: $1+3+7+9+11+13+17+19=80={\frac {160}{1}}={\frac {20\cdot 8}{2}}={\frac {20\cdot \varphi (20)}{2}}$

$n>2$ bada, $\varphi (n)$ bikoitia da.
Baldin $a|b$ , orduan $\varphi (a)|\varphi (b)$
$\varphi (zkh(a,b))\cdot \varphi (mkt(a,b))=\varphi (a)\cdot \varphi (b)$
$n\neq 2$ eta $n\neq 6$ bada, beti egiaztatuko da $\varphi (n)\geq {\sqrt {n}}$
$\varphi (1)+\varphi (2)+\varphi (3)+...+\varphi (n)\thickapprox {\frac {3n^{2}}{\pi ^{2}}}$ , $n$ zenbat eta handiagoa izan, erlatiboki orduan eta gehiago hurbiltzen da batura balio horretara

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 orokortze 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 1{\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.

Carmichaelen aierua

Badaude balio batzuk Euler-en $\varphi (n)$ funtzioak ezin dituenak inoiz hartu, adibidez, ez dago $n$ zenbaki naturalik non $\varphi (n)=14$ den. Hartu ezin dituen beste balio batzuk hauek dira: 26, 34, 38, 50, 62, 68...

1907an, Robert D. Carmichael matematikariak honako hau konjeturatu zuen: baldin n zenbakia existitzen bazen non $\varphi (n)=k$ , orduan existitu behar zela beste $m$ zenbaki bat non $\varphi (m)=k$ . Teorema bezala aurkeztu zuen, baina geroago egiaztapenak akats bat zeukala ikusi zuten. Oraindik, aurrerapenak egin badira ere, ezin izan dute aierua guztiz egiaztatu.

Bestetik, $\varphi (15)=\varphi (16)$ dela ezaguna da, baina $\varphi (n)=\varphi (n+1)$ propietatea egiaztatzen duten $(n,n+1)$ bikote kopurua infinitua ote den ezezaguna da. Jakina dena da edozein $k$ -rentzat gutxienez $n$ zenbaki bat existitzen dela non $\varphi (n)=\varphi (n+k)$ , Waclaw Sierpinskik egiaztatu zuenez.

Lehmer-en aierua

Jakina da $p$ zenbakia lehena bada, orduan $\varphi (p)=p+1$ . Baina, argi dago $n$ lehena ez bada $n$ -k ezin duela $n-1$ balioa hartu. 1932an D. H. Lehmerrek bere buruari galdetu zion ea $n$ zenbaki konposaturen bat existitzen ote zen non $\varphi (n)$ $(n-1)$ -ren zatitzailea zen. Gaur arte ez da aurkitu propietate hori betetzen duen zenbakirik, eta ez da frogatu ez dagoenik.

Kanpo estekak

Datuak: Q190026
Multimedia: Totient function / Q190026