Funció de Carmichael

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

${\displaystyle a^{m}\equiv 1{\pmod {n}}}$

per a tot enter ${\displaystyle a}$ que és al mateix temps coprimer amb i més petit que ${\displaystyle 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 ${\displaystyle \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)

Rep el seu nom en honor del matemàtic americà Robert Daniel Carmichael (1879-1967).

Exemple numèric

5² ≡ 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, 3² =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

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

Per a qualsevol nombre primer ${\displaystyle p}$ i notural ${\displaystyle k}$ tal que ${\displaystyle p\geq 3}$ o ${\displaystyle k\leq 2}$:

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

Per a l'enter ${\displaystyle k\geq 3}$

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

Per a nombres primers diferents ${\displaystyle p_{1},p_{2},\ldots ,p_{t}}$ i naturals ${\displaystyle k_{1},k_{2},\ldots ,k_{t}}$:

${\displaystyle \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 ${\displaystyle \mathrm {mcm} }$ denota el mínim comú múltiple.

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

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

on ${\displaystyle \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

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

valor Mitjà i típic

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

${\displaystyle {\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 ${\displaystyle N}$ i tots trets de o(N) naturals n ≤; N:

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

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

Fites Inferiors

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

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

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

Per a qualsevol successió ${\displaystyle n_{1}<n_{2}<n_{3}<\cdots }$ de naturals, qualsevol ${\displaystyle 0<c<1/\ln 2}$ constant, i qualsevol ${\displaystyle i}$ prou gran:

${\displaystyle \lambda (n_{i})>(\ln n_{i})^{c\ln \ln \ln n_{i}}}$.^[5]

Valors petits

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

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

A més, ${\displaystyle n}$ és de la forma

${\displaystyle n=\prod _{(q-1)|m{\text{ and }}q{\text{ is prime}}}q}$

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

Vegeu també

• Nombres de Carmichael

Notes

Referències

• Paul Erdős, Carl Pomerance, Eric Schmutz (1991) Carmichael's lambda function, Acta Arithmetica, vol. 58, 363–385.
• John Friedlander, Carl Pomerance, Igor E. Shparlinski (2001) Period of the power generator and small values of the Carmichael function, Mathematics of Computation, vol. 70 no. 236, pp. 1591-1605.