Don't take life too seriously: it's just a temporary situation

Carmichael deboli (numeri di)

Teoria dei numeri 

Un numero naturale n composto si chiama “numero di Carmichael debole” se Formula per la definizione dei numeri di Carmichael deboli.

Il criterio è simile a quello per i numeri di Carmichael, ma senza il requisito che n non sia multiplo di un quadrato.

 

Come i numeri di Carmichael, i numeri di Carmichael deboli sono dispari e non sono il prodotto di due primi, ma a differenza di quelli possono essere multipli di quadrati, una potenza di un primo o il prodotto di un primo per una potenza di un altro.

 

Vi sono alcune categorie infinite di numeri di Carmichael deboli:

  • tutti i numeri di Carmichael;

  • tutte le potenze dei numeri primi dispari;

  • tutte le potenze di numeri di Carmichael deboli.

 

Un intero positivo composto n è un numero di Carmichael debole se e solo se per tutti i primi p che dividono n, p – 1 divide n – 1. Un’affermazione equivalente è che un intero positivo composto n è un numero di Carmichael debole se e solo se λ(Π(n)) divide n – 1, dove λ(n) (III) è la funzione di Carmichael.

 

I numeri di Carmichael deboli inferiori a 10000 sono: 9, 25, 27, 45, 49, 81, 121, 125, 169, 225, 243, 289, 325, 343, 361, 405, 529, 561, 625, 637, 729, 841, 891, 961, 1105, 1125, 1225, 1331, 1369, 1377, 1681, 1729, 1849, 2025, 2187, 2197, 2209, 2401, 2465, 2809, 2821, 3125, 3321, 3481, 3645, 3721, 3751, 3825, 4225, 4489, 4913, 4961, 5041, 5329, 5589, 5625, 6241, 6517, 6525, 6561, 6601, 6859, 6889, 7381, 7921, 8125, 8281, 8625, 8911, 9409, 9801.

Qui trovate i numeri di Carmichael deboli inferiori a 1012 (1.4 Mbyte) (M. Fiorentini, 2014).

 

Il minimo numero di Carmichael debole che sia una potenza di un numero composto è 225 = 152; il minimo con due soli fattori primi e che non sia una potenza è 325 = 52 • 13; il minimo che sia prodotto di altri due numeri di Carmichael deboli è 1025 = 45 • 225.

 

Se p e q sono primi o potenze di primi dispari e q = kp + 1, non esistono numeri di Carmichael deboli multipli di pq; in particolare non ne esistono multipli di 21 o 39.

 

Se MCD(n, φ(n)) = 1, naλ(n) e naφ(n) è un numero di Carmichael debole per ogni intero a maggiore di zero, dove λ(n) (III) è la funzione di Carmichael.

 

Dati due primi dispari p e q con p < q e q – 1 non multiplo di p, paφ(q – 1)qbφ(p – 1) è un numero di Carmichael debole per qualsiasi coppia di interi a e b maggiori di zero (J.M. Borwein e E. Wong, 1995). Per esempio con p = 5 e q = 7 abbiamo φ(4) = 2, φ(6) = 2 e scegliendo a = 2, b = 1 otteniamo il numero di Carmichael debole 54 • 72 = 30625.

 

Dati due primi dispari p e q con p < q e q – 1 non multiplo di p, se a e b sono i minimi interi positivi tali che pa ≡ 1 mod q − 1 e qb ≡ 1 mod p − 1, allora pmqn è un numero di Carmichael debole se e solo se a divide m e b divide n (Romeo Meštrović, 2013). Per esempio per p = 13 e q = 17, abbiamo a = 4 e b = 2 e 13m • 17n è un numero di Carmichael debole se e solo se m è multiplo di 4 e n è multiplo di 2.

Di conseguenza nessun numero di Carmichael debole è il prodotto di due primi.

 

Se 6k + 1, 12k + 1 e 18k + 1 sono tre numeri primi e d è un divisore di 36k36 * k / d + 1 è un primo differente dagli altri tre e (36 * k / d + 1)^m ≡ 1 mod 36k per m intero non negativo, (6k + 1)(12k + 1)(18k + 1)(36 * k / d + 1)^m è un numero di Carmichael debole (Romeo Meštrović, 2013). Per esempio, per k = 35 abbiamo i tre primi 211, 421 e 631, possiamo prendere d = 105 per ottenere il quarto primo, 13; dato che 1312m ≡ 1 mod 1260, otteniamo che 211 • 421 • 631 • 1312m è un numero di Carmichael debole per m intero non negativo.

 

Dati n primi dispari distinti p1, p2, … pn, se pl – 1 non è multiplo di pm, per ogni coppia di primi pl e pm, calcoliamo per ciascun primo pm l’esponente em = mcm(p1 – 1, p2 – 1, … pn – 1), dove il minimo comune multiplo si calcola su tutti i primi diversi da pm, allora Prodotto dei primi p(m), ciascuno elevato a k(m)e(m) è un numero di Carmichael debole per ogni combinazione di interi maggiori di zero k1, k2, … kn (Romeo Meštrović, 2013).

Per esempio, prendendo p1 = 3, p2 = 11 e p3 = 17, abbiamo e1 = mcm(10, 16) = 80, e2 = mcm(2, 16) = 16, e3 = mcm(2, 10) = 10 e prendendo k1 = k2 = 2, k3 = 2, abbiamo il numero di Carmichael debole 38011161720 = 27603348444339634920075270700942469205400886790988655762928433013415528845303361. In questo modo si possono costruire infiniti numeri di Carmichael deboli multipli di qualsiasi intero dispari e che non sono numeri di Carmichael.

Viceversa se p1, p2, … pn, sono i fattori primi di un numero di Carmichael debole, pl – 1 non è multiplo di pm, per ogni coppia di primi pl e pm e mcm(p1 – 1, p2 – 1, … pn – 1) divide λ(n), dove λ(n) (III) è la funzione di Carmichael (Romeo Meštrović, 2013).

 

Dato un numero di Carmichael c, divisibile per n fattori primi p1, p2, … pn, preso uno di essi pm, e calcolato r = mcm(p1 – 1, p2 – 1, … pn – 1), dove il minimo comune multiplo si calcola su tutti i primi diversi da pm, sia d il minimo divisore di φ(r) tale che p(m)^d ≡ 1 mod r, allora per ogni intero k > 0, c * p(m)^(k * d) è un numero di Carmichael debole (Romeo Meštrović, 2013). Per esempio, 561 = 3 • 11 • 17 è un numero di Carmichael; prendiamo pm = 3, allora r = mcm(10, 16) = 80 e d = 4, perché 4 è il minimo divisore di φ(80) = 32 tale che 3d ≡ 1 mod 80; allora 561 • 34k è un numero di Carmichael debole per k intero non negativo; per k = 1 otteniamo 45441.

 

Nel 2013 Romeo Meštrović dimostrò che per i numeri di numeri di Carmichael deboli vale un teorema analogo a quello di J.M. Borwein e E. Wong per i numeri di Carmichael: un intero n > 2 è un numero di Carmichael debole, ma non un numero di Carmichael se e solo se Congruenza soddisfatta dai numeri di Carmichael deboli, ma non dai numeri di Carmichael

 

Meštrović avanzò la congettura che per ogni valore di n maggiore di 2 il minimo numero di Carmichael debole con n fattori primi sia un numero di Carmichael: i minimi numeri di Carmichael deboli con 3, 4 e 5 fattori primi sono rispettivamente 561 = 3 • 11 • 17, 41041 = 7 • 11 • 13 • 41, 825265 = 5 • 7 • 17 • 19 • 73, che sono numeri di Carmichael. La congettura si è però rivelata falsa: il minimo numero di Carmichael debole con 6 fattori primi è 135942625 = 53 • 7 • 13 • 17 • 19 • 37, che non è un numero di Carmichael (M. Fiorentini, 2013).

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.