Funció φ de Euler

La funció φ d'Euler (també cridada funció totiente) és una funció important en teoria de números. Si n és un número entero positiu, llavors φ(n) es definix com la cantitat de sancers positius menors a n i coprimos en n, és dir, formalment es pot definir com:^[1]^[2]

φ (n) = | {m \in ℕ | m \leq n \land m c d (m, n) = 1} |

a on |·| significa la cardinalidad del conjunt descrit.

Una atra forma de definir el totiente d'un número natural n és indicar que és la cantitat d'número entero positius menors que n tals que el màxim comú divisor sobre n és igual a 1.

La funció φ és important principalment perque proporciona el tamany del grup multiplicativo de sancers mòdul n. Més precisament, $φ (n)$ és l'orde del grup d'unitats del anell $ℤ / n ℤ$ . En efecte, junt en el teorema de Lagrange dels possibles tamanys de subgrups d'un grup, proporciona una demostració del teorema de Euler que diu que $a^{φ (n)} \equiv 1 (\mod n)$ per a tot a coprimo en n. La funció φ juga també un paper clau en la definició del sistema de sifrat RSA.

Història, terminologia i notació

Leonhard Euler va introduir la funció en 1763.^[3]^[4]^[5] No obstant, en eixe moment no va elegir cap símbol específic per a denotar-la. En una publicació de 1784, Euler va estudiar de nou la funció més a fondo, elegint la lletra grega $π$ per a denotar-la: va escriure $πD$ per a "la multitut de números menors que $D$ , i que no tenen un divisor comú en ell".^[6] Esta definició varia de la definició actual de la funció totiente en $D = 1$ pero, per lo demés, és la mateixa. La notació ara estàndar^[4]^[7] $φ (A)$ prové del tractat de Carl Friedrich Gauss de 1801 Disquisitiones arithmeticae,^[8]^[9] encara que Gauss no va usar paréntesis al voltant de l'argument i va escriure $φA$ . Per lo tant, a sovint li la crida funció phi de Euler o simplement funció phi.

En 1879, J. J. Sylvester va falcar el terme totiente per a esta funció,^[10]^[11] per lo que també li la coneix com a funció totiente de Euler, totiente de Euler, o el totiente de Euler. El totiente de Jordan és una generalisació de l'idea de Euler.

El cototiente de $n$ es definix com $n - φ (n)$ . Conta el número de sancers positius menors o iguals a $n$ que tenen a lo manco un factor primer en comú en $n$ .

Primeres propietats i càlcul de la funció

Se seguix de la definició que $φ (1) = 1$ , puix l'element $1$ només pot ser coprimo en si mateixa. Per a atres números es complix que:

$φ (p) = p - 1$ si $p$ és primer.
$φ (p^{k}) = (p - 1) p^{k - 1}$ si $p$ és primer i $k$ és un número natural.
$φ$ és una funció multiplicativa: si $m$ i $n$ són coprimos, llavors $φ (m n) = φ (m) φ (n)$ .

La primera propietat es demostra fàcilment, perque un número primo és coprimo en tots els seus números anteriors. I, per tant, existixen $p - 1$ elements coprimos en $p$ . En atres paraules, com $p$ és primer només tindrà de divisores a sí mateix i a l'unitat, la qual està present en els $p - 1$ números anteriors a $p$ ..

Per a la segona propietat, devem observar que si $p$ és primer només els seus múltiples $n p$ menors o iguals que $p^{k}$ presenten un comú divisor en $p^{k}$ distint d'un. Açò és, $1 p, 2 p, 3 p, ..., (p^{k - 1}) p$ són els únics números $m$ tals que $m c d (p^{k}, m) \neq 1$ . Com en total hi ha $p^{k - 1}$ números que satisfan esta propietat, el restant de números entre $1$ i $p^{k}$ només tenen a $1$ com divisor comú en $p^{k}$ . Açò és, $φ (p^{k}) = p^{k} - p^{k - 1} = (p - 1) p^{k - 1}$ . (Note's que esta segona propietat es complix perque $p$ és primer. En efecte, si hi haguera un $m \neq n p$ , $m \geq 2$ tal que $m c d (p^{k}, m) = a \neq 1$ , llavors $a$ seria divisor de $p^{k} = p \cdot p ... p$ ( $k$ voltes); és dir, $a$ seria una potència (i per tant múltiple) de $p$ , contradient la suposició inicial $m \neq n p$ ).

Per a demostrar la tercera propietat, siguen $A$ , $B$ , $C$ els conjunts de sancers positius que són coprimos i menors que $m$ , $n$ , $m n$ respectivament ( llavors $| A | = φ (m)$ , $| B | = φ (n)$ i $| C | = φ (m n)$ ). Després, pel Teorema Chinenca del Restant existix una biyección entre $C$ i $A \times B$ , lo que implica que $φ (m n) = φ (m) φ (n)$ .

En açò, el valor de $φ (n)$ pot calcular-se amprant el Teorema Fonamental de l'Aritmètica: si

n = p_{1}^{k_{1}} \dots p_{r}^{k_{r}}

a on els p_j són número primo distints, llavors

φ (n) = (p_{1} - 1) p_{1}^{k_{1} - 1} \dots (p_{r} - 1) p_{r}^{k_{r} - 1} .

Esta fòrmula pot reescriure's de la següent manera (coneguda com la Fòrmula de Producte de Euler):

φ (n) = n \prod_{p | n} (1 - \frac{1}{p})

a on els $p$ són els distints cosins que dividixen a $n$ .

Eixemple de càlcul

φ (36) = φ (3^{2} 2^{2}) = 36 (1 - \frac{1}{3}) (1 - \frac{1}{2}) = 36 \cdot \frac{2}{3} \cdot \frac{1}{2} = 12.

També,

φ (36) = φ (3^{2} 2^{2}) = (3 - 1) 3^{(2 - 1)} (2 - 1) 2^{(2 - 1)} = 2 \cdot 3 \cdot 1 \cdot 2 = 12.

Es pot comprovar manualment que els números coprimos en 36 (o siga, que no són divisibles per 2 ni per 3) són dotze: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, i 35.

Transformada de Fourier

El totiente és la transformada de Fourier discreta del mcd, evaluat en 1.^[12] Siga

ℱ {𝐱} [m] = \sum_{k = 1}^{n} x_{k} \cdot e^{- 2 π i \frac{m k}{n}}

a on $x k = mcd(k, n)$ para $k \in {1, ..., n}$ . Llavors

φ (n) = ℱ {𝐱} [1] = \sum_{k = 1}^{n} mcd (k, n) e^{- 2 π i \frac{k}{n}} .

La part real d'esta fòrmula és

φ (n) = \sum_{k = 1}^{n} mcd (k, n) \cos \frac{2 π k}{n}

A diferència del producte de Euler i la fòrmula de la suma del divisor, esta no requerix conéixer els factors de $n$ . No obstant, implica el càlcul del màxim comú divisor de $n$ i tot número entero positiu menor que $n$ , lo que és suficient per a proporcionar la factorización de tots modos.

Suma dels seus divisores

La propietat establida per Gauss,^[13] de que

\sum_{d ∣ n} φ (d) = n,

a on la suma és sobre tots els divisores positius $d$ de $n$ , es pot demostrar de vàries maneres (vore funció aritmètica per a conéixer les convencions de la notació).

Una prova és notar que $φ (d)$ també és igual al número de possibles generadors del grup cíclico $C d$ ; específicament, si $C d = ⟨ g ⟩$ en $g d = 1$ , llavors $g k$ és un generador per a cada coprimo de $k$ a $d$ . Ya que cada element de $C n$ genera un subgrup cíclico, i tots els subgrups $C d \subseteq C n$ són generats precisament per elements $φ (d)$ de $C n$ , la fòrmula és la següent.^[14] De manera equivalent, la fòrmula es pot derivar per mig del mateix argument aplicat al grup multiplicativo de les raïls d'unitat $n$ -ésimas raïls de l'unitat i $d$ -ésimas primitives.

La fòrmula també es pot derivar de l'aritmètica elemental.^[15] Per eixemple, siga $n = 20$ i consideren-se les fraccions positives fins a 1 en denominador 20:

\frac{1}{20}, \frac{2}{20}, \frac{3}{20}, \frac{4}{20}, \frac{5}{20}, \frac{6}{20}, \frac{7}{20}, \frac{8}{20}, \frac{9}{20}, \frac{10}{20}, \frac{11}{20}, \frac{12}{20}, \frac{13}{20}, \frac{14}{20}, \frac{15}{20}, \frac{16}{20}, \frac{17}{20}, \frac{18}{20}, \frac{19}{20}, \frac{20}{20} .

Reduint-les a térmens mínims:

\frac{1}{20}, \frac{1}{10}, \frac{3}{20}, \frac{1}{5}, \frac{1}{4}, \frac{3}{10}, \frac{7}{20}, \frac{2}{5}, \frac{9}{20}, \frac{1}{2}, \frac{11}{20}, \frac{3}{5}, \frac{13}{20}, \frac{7}{10}, \frac{3}{4}, \frac{4}{5}, \frac{17}{20}, \frac{9}{10}, \frac{19}{20}, \frac{1}{1}

Estes vint fraccions són totes les Plantilla:Sfrac ≤ 1 positives els denominadors de les quals són els divisores $d = 1, 2, 4, 5, 10, 20$ . Les fraccions en 20 com a denominador són aquelles en numeradors relativament primers a 20, a saber, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac i Plantilla:Sfrac. Per definició, es tracta de les $φ (20)$ fraccions en denominador 20. De manera similar, hi ha $φ (10)$ fraccions en denominador 10 i $φ (5)$ fraccions en denominador 5, etc. Per lo tant, el conjunt de vint fraccions es dividix en subconjunts de tamany $φ (d)$ per a cada $d$ que dividix 20. S'aplica un argument similar per a qualsevol n.

La fòrmula d'inversió de Möbius aplicada a la fòrmula de la suma del divisor dona

φ (n) = \sum_{d ∣ n} μ (d) \cdot \frac{n}{d} = n \sum_{d ∣ n} \frac{μ (d)}{d},

a on $μ$ és la funció de Möbius, la funció multiplicativa definida per $μ (p) = - 1$ i $μ (p^{k}) = 0$ per a cada primer $p$ i $k \geq 2$ . Esta fòrmula també es pot derivar de la fòrmula del producte multiplicant $\prod_{p ∣ n} (1 - \frac{1}{p})$ per a obtindre $\sum_{d ∣ n} \frac{μ (d)}{d} .$

Un eixemple:

\begin{matrix} φ (20) & = μ (1) \cdot 20 + μ (2) \cdot 10 + μ (4) \cdot 5 + μ (5) \cdot 4 + μ (10) \cdot 2 + μ (20) \cdot 1 \\ = 1 \cdot 20 - 1 \cdot 10 + 0 \cdot 5 - 1 \cdot 4 + 1 \cdot 2 + 0 \cdot 1 = 8. \end{matrix}

Vore també

Referències

↑ Long (1972, p. 85)
↑ Pettofrezzo y Byrkit (1970, p. 72)
↑ L. Euler "Theoremata arithmetica nova methodo demonstrata" (An arithmetic theorem proved by a new method), Novi commentarii academiae scientiarum imperialis Petropolitanae (New Memoirs of the Saint-Petersburg Imperial Academy of Sciences), 8 (1763), 74–104. (L'obra va ser presentada en l'Acadèmia de Sant Petersburgo el 15 d'octubre de 1759. Una obra en el mateix títul va ser presentada en l'Acadèmia de Berlín el 8 de juny de 1758). Disponible en llínea en: Ferdinand Rudio, Plantilla:Abbr, Leonhardi Euleri Commentationes Arithmeticae, volume 1, in: Leonhardi Euleri Opera Omnia, séries 1, volume 2 (Leipzig, Germany, B. G. Teubner, 1915), pages 531–555. On page 531, Euler definixes $n$ as the number of integers that llaure smaller than $N$ and relatively prime to $N$ (... aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi, ...), que és la funció fi, φ(N).
↑ ^4,0 ^4,1 Sandifer, p. 203
↑ Graham et al. p. 133 note 111
↑ L. Euler, Speculationes circa quasdam insignes proprietates numerorum, Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4, (1784), pp. 18–30, or Opera Omnia, Séries 1, volume 4, pp. 105–115. (L'obra va ser presentada en l'Acadèmia de Sant Petersburgo el 9 d'octubre de 1775).
↑ Both $φ (n)$ and $ϕ (n)$ llaure seen in the literature. These llaure two forms of the lower-case Greek letter φ.
↑ Gauss, Disquisitiones Arithmeticae article 38
↑ Cajori, Florian (1929). A History Of Mathematical Notations Volume II, Open Court Publishing Company.
↑ J. J. Sylvester (1879) "On certain ternary cubic-form equations", American Journal of Mathematics, 2 : 357-393; Sylvester coins the term "totient" on page 361.
↑ "totient". Oxford English Dictionary (2nd ed.). Oxford University Press. 1989.
↑ Schramm (2008)
↑ Gauss, DA, art 39
↑ Gauss, DA art. 39, arts. 52-54
↑ Graham et al. pp. 134-135

Bibliografia

Les Disquisitiones Arithmeticae han segut traduïdes del llatí a l'anglés i a l'alemà. L'edició alemana inclou tots els artículs de Gauss sobre teoria de números: totes les proves de la reciprocitat quadràtica, la determinació del signe de la suma de Gauss, les investigacions sobre la reciprocitat biquadràtica i notes inèdites.

Les referències a les Disquisitiones són de la forma Gauss, DA, art. nnn.

. See paragraph 24.3.2.
Dickson, Leonard Eugene, "History Of The Theory Of Numbers", vol 1, chapter 5 "Euler's Function, Generalizations; Farey Séries", Chelsea Publishing 1952
.

(2004).«Unsolved Problems in Number Theory».Springer-Verlag.New York, NY:
(1972).«Elementary Introduction to Number Theory».D. C. Heath and Company.Lexington:
(1970).«Elements of Number Theory».Prentice Hall.Englewood Cliffs:
(2006).«Handbook of number theory I».Springer-Verlag.Dordrecht:

9–36.

(2004) Handbook of number theory II, Dordrecht: Kluwer Academic, pp. 179–327. ISBN 1-4020-2546-7.
.

Referències

Este artícul conté una traducció derivada de «Función φ de Euler» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Long (1972, p. 85)

[2] Pettofrezzo y Byrkit (1970, p. 72)

[3] L. Euler "Theoremata arithmetica nova methodo demonstrata" (An arithmetic theorem proved by a new method), Novi commentarii academiae scientiarum imperialis Petropolitanae (New Memoirs of the Saint-Petersburg Imperial Academy of Sciences), 8 (1763), 74–104. (L'obra va ser presentada en l'Acadèmia de Sant Petersburgo el 15 d'octubre de 1759. Una obra en el mateix títul va ser presentada en l'Acadèmia de Berlín el 8 de juny de 1758). Disponible en llínea en: Ferdinand Rudio, Plantilla:Abbr, Leonhardi Euleri Commentationes Arithmeticae, volume 1, in: Leonhardi Euleri Opera Omnia, séries 1, volume 2 (Leipzig, Germany, B. G. Teubner, 1915), pages 531–555. On page 531, Euler definixes $n$ as the number of integers that llaure smaller than $N$ and relatively prime to $N$ (... aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi, ...), que és la funció fi, φ(N).

[Sandifer,_p._203-4] 4,0 ^4,1 Sandifer, p. 203

[5] Graham et al. p. 133 note 111

[6] L. Euler, Speculationes circa quasdam insignes proprietates numerorum, Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4, (1784), pp. 18–30, or Opera Omnia, Séries 1, volume 4, pp. 105–115. (L'obra va ser presentada en l'Acadèmia de Sant Petersburgo el 9 d'octubre de 1775).

[7] Both $φ (n)$ and $ϕ (n)$ llaure seen in the literature. These llaure two forms of the lower-case Greek letter φ.

[8] Gauss, Disquisitiones Arithmeticae article 38

[9] Cajori, Florian (1929). A History Of Mathematical Notations Volume II, Open Court Publishing Company.

[10] J. J. Sylvester (1879) "On certain ternary cubic-form equations", American Journal of Mathematics, 2 : 357-393; Sylvester coins the term "totient" on page 361.

[11] "totient". Oxford English Dictionary (2nd ed.). Oxford University Press. 1989.

[12] Schramm (2008)

[13] Gauss, DA, art 39

[14] Gauss, DA art. 39, arts. 52-54

[15] Graham et al. pp. 134-135

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]