Funció de Carmichael

De Viquipèdia
Dreceres ràpides: navegació, cerca

En teoria de nombres, la funció de Carmichael d'un nombre natural n, notada \lambda(n) es defineix com l'enter positiu més petit m tal que

a^m \equiv 1 \pmod{n}

per a tot enter a que és al mateix temps coprimer amb i més petit que n.

En altres paraules, en més termes algebraics, defineix l'exponent del grup multiplicatiu de residus mòdul n.

Els primers 26 valors de \lambda(n) per n = 1, 2, 3... són 1, 1, 2, 2, 4, 2, 6, 2, 6, 4, 10, 2, 12, 6, 4, 4, 16, 6, 18, 4, 6, 10, 22, 2, 20, 12... (successió A002322 a l'OEIS)

Exemple numèric[modifica | modifica el codi]

52 ≡ 1 (mod 6) perquè 5 i 6 són coprimers. En altres paraules, el MCD (5,6)=1. Aquí s'hava d'elevar 5 a la 2a potència perquè la funció Fi d'Euler de 6 és 2.[1] Recordar que 1 i 5 són els únics dos nombres que són relativament primers a 6.

Tanmateix, 32 =9 ≡3 (mòd 6) òbviament no funciona perquè el nombre 3 és impermissible com a base per ser elevada a la 2a potència. Sabent que el MCD(3,6)=3, no 1.

El teorema de Carmichael[modifica | modifica el codi]

Aquesta funció també es pot definir recursivament, de la manera següent.

Per a qualsevol nombre primer p i notural k tal que p \ge 3 o k \le 2:

\lambda(p^k) = p^{k-1}(p-1).\, (Això és igual a la funció totient d'Euler, \varphi(p^k)\, )

Per a l'enter k \ge 3

\lambda(2^k) = 2^{k-2}.\,

Per a nombres primers difernts p_1,p_2,\ldots,p_t i naturals k_1,k_2,\ldots,k_t:

\lambda(p_1^{k_1} p_2^{k_2} \cdots p_t^{k_t}) = 
 \mathrm{mcm}( \lambda(p_1^{k_1}), \lambda(p_2^{k_2}), \ldots, \lambda(p_t^{k_t}) )

on \mathrm{mcm} denota el mínim comú múltiple.

El teorema de Carmichael estableix si a és coprimer amb n, llavors

a^{\lambda(n)} \equiv 1 \pmod{n},

on \lambda és la funció de Carmichael definida recursivament. En altres paraules, afirma la correcció de la recurrència. Això es pot demostrar considerant qualsevol N de modulo d'arrel primitiva i el Teorema xinès del residu.

Jerarquia de resultats[modifica | modifica el codi]

El teorema d'Euler clàssic implica que λ(n) divideix φ(n), la Funció Fi d'Euler. De fet relaciona el teorema de Carmichael amb el teorema d'Euler, perquè l'exponent d'un grup abelià finit ha de dividir l'ordre del grup, per la teoria de grups elemental. Les dues funcions difereixen ja en casos petits: λ(15) = 4 mentre φ(15) = 8.

El petit teorema de Fermat és el cas especial del teorema d'Euler on n és un nombre primer p. El teorema de Carmichael per a una nombres primers p no afegeix res al teorema de Fermat, perquè el grup en qüestió és un grup cíclic per al qual l'ordre i exponent són els dos p − 1.

Propietats de la funció de Carmichael[modifica | modifica el codi]

valor Mitjà i típic[modifica | modifica el codi]

Per a algun x > 16, i una constant B ≈ 0.34537:

\frac{1}{x} \sum_{n \leq x} \lambda (n) = \frac{x}{\ln x} e^{B(\ln\ln x) (1+o(1)) / (\ln\ln\ln x) }.[2]

Per a tots els nombres N i tots trets de o(N) naturals n ≤; N:

\lambda(n) = n / (\ln n)^{\ln\ln\ln n + A + o(1)}\,

on A és una constant, A ≈ 0.226969.[3]

Fites Inferiors[modifica | modifica el codi]

Per a qualsevol nombre prou gran N i per a qualsevol \Delta \geq (\ln\ln N)^3, hi ha com a màxim

Ne^{-0.69(\Delta\ln\Delta)^{1/3}}

enters positius n \leq N tals que \lambda(n) \leq ne^{-\Delta}.[4]

Per a qualsevol successió n_1<n_2<n_3<\cdots de naturals, qualsevol 0<c<1/\ln2 constant, i qualsevol i prou gran:

\lambda(n_i) > (\ln n_i)^{c\ln\ln\ln n_i}.[5]

Valors petits[modifica | modifica el codi]

For a constant c and any sufficiently large positive A, there exists an integer n>A such that \lambda(n)<(\ln A)^{c\ln\ln\ln A}.

Per a una constant c i qualsevol positiu prou gran A, existeix un enter n>A tal que \lambda(n)<(\ln A)^{c\ln\ln\ln A}.

A més, n és de la forma

n=\prod_{(q-1)|m \text{ and } q \text{ is prime}}q

per a algun enter lliure de quadrats m<(\ln A)^{c\ln\ln\ln A}.[6]

Vegeu també[modifica | modifica el codi]

Notes[modifica | modifica el codi]

  1. [enllaç sense format] http://www25.brinkster.com/denshade/totient.html
  2. Theorem 3 in Erdös (1991)
  3. Teorema 2 a Erdös (1991)
  4. Teorema 5 a Friedlander (2001)
  5. Theorem 1 in Erdös 1991
  6. Teorema 1 a Erdös 1991

Referències[modifica | modifica el codi]