Funció de Carmichael

De la Viquipèdia, l'enciclopèdia lliure

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

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

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

Els primers 26 valors de 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[modifica]

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[modifica]

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

Per a qualsevol nombre primer i notural tal que o :

(Això és igual a la funció totient d'Euler, )

Per a l'enter

Per a nombres primers diferents i naturals :

on denota el mínim comú múltiple.

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

on é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]

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]

valor Mitjà i típic[modifica]

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

.[2]

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

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

Fites Inferiors[modifica]

Per a qualsevol nombre prou gran i per a qualsevol , hi ha com a màxim

enters positius tals que .[4]

Per a qualsevol successió de naturals, qualsevol constant, i qualsevol prou gran:

.[5]

Valors petits[modifica]

For a constant and any sufficiently large positive , there exists an integer such that .

Per a una constant i qualsevol positiu prou gran , existeix un enter tal que .

A més, és de la forma

per a algun enter lliure de quadrats .[6]

Vegeu també[modifica]

Notes[modifica]

  1. [enllaç sense format] http://www25.brinkster.com/denshade/totient.html Arxivat 2011-06-15 a Wayback Machine.
  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]