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

Overpseudoprimi

Teoria dei numeri 

Si chiamano “overpseudoprimi in base b” i numeri composti n tali che ordn(b) = ordd(b) per tutti i divisori d di n. Per esempio, 1541 è overpseudoprimo in base 5, perché 1541 = 23 • 67 e ord23(5) = ord67(5) = 22.

 

Furono studiati per la prima volta da Vladimir Sheverel nel 2008, poi da J.H. Castillo, G. García-Pulgarín, e J.M. Velásquez-Soto nel 2012; questi ultimi Autori chiamarono questi numeri “pseudoprimi di Midy”, dal nome di un matematico che aveva lavorato sul tema.

 

Carl Pomerance dimostrò che gli overpseudoprimi in base 2 sono infiniti.

Vladimir Sheverel dimostrò nel 2008 che gli overpseudoprimi in base 2 minori di x sono meno di Limite superiore per il numero di overpseudoprimi minori di x, per una costante c.

 

Se n è overpseudoprimo in base b, ordn(b) divide la differenza tra due qualsiasi divisori di n (Vladimir Sheverel, 2008). Per esempio, nel caso di 1541, 22 divide 67 – 23 = 44.

Il contrario non è sempre vero; per esempio, ord4681(2) = 15 divide la differenza tra qualsiasi coppia di divisori di 4681, ma 4681 non è overpseudoprimo in base 2, perché uno dei sui divisori è 31 e ord31(2) = 5

 

Se p è overpseudoprimo in base b, è uno pseudoprimo forte in base b (Vladimir Sheverel, 2008).

Se p è overpseudoprimo in base b, è un superpseudoprimo in base b (Vladimir Sheverel, 2012).

 

Se n è overpseudoprimo in base b, per ogni divisore d di n, bd – b è un multiplo di d.

 

Se p e q sono overpseudoprimi in base b e ordp(b) ≠ ordq(b), p e q sono primi tra loro (Vladimir Sheverel 2008).

 

Se p1, p2, … pn sono primi distinti o potenze di primi distinti overpseudoprimi in base bordpk(b) = ordpm(b) per ogni coppia di interi k, m non superiori a n, il loro prodotto è overpseudoprimo in base b.

 

Un numero composto è overspeudoprimo in base 2 se e solo se è esprimibile come Φn(2) / MCD(Φn(2), n), dove Φn(x) è l’n-esimo polinomio ciclotomico.

 

Un overpseudoprimo in base 2 è un numero di super-Poulet, ma non viceversa (Vladimir Sheverel 2008). Per esempio, 9691627 è un numero di super-Poulet ma non un overpseudoprimo in base 2, perché 9691627 = 167 • 499 • 1163 e ord167(2) = 83, ord499(2) = 166, ord1163(2) = 166.

 

I numeri della forma bn + 1 con b pari sono primi o overpseudoprimi in base b se e solo se n è una potenza di 2; quindi i numeri di Fermat generalizzati con b pari sono primi o overpseudoprimi in base b (Vladimir Sheverel, 2008).

 

I numeri pluriunitari (b^p – 1) / (b – 1) sono primi o overpseudoprimi in base b se e solo se p è un primo che non divide b – 1 (Vladimir Sheverel, 2008). Ne segue che se p è un primo che non divide b – 1, p divide la differenza tra tutti di divisori di (b^p – 1) / (b – 1).

In particolare i numeri di Mersenne Mp composti con p primo sono overpseudoprimi in base 2 (Vladimir Sheverel 2008).

Un numero pluriunitario (b^p – 1) / (b – 1) è primo o overpseudoprimo in base b se e solo se vi è un solo primo q della forma np + 1 tale che ordq(b) = p (Vladimir Sheverel, 2012).

 

Se p è primo, (b^(p^n) – 1) / (b^(p^(n – 1)) – 1) è primo o overpseudoprimo in base b se e solo se è primo rispetto a bpn – 1– 1.

Se p è primo, (b^(p^n) – 1) / (b^(p^(n – 1)) – 1) è primo o overpseudoprimo in base b se e solo se non è multiplo di p.

 

Se  p e q sono primi distinti, (b^(p^r * q^s) – 1) * (b^(p^(r – 1) * q^(s – 1)) – 1) / (b^(p^(r – 1) * q^s) – 1) * (b^(p^r * q^(s – 1) – 1))) è primo o overpseudoprimo in base b se e solo se è primo rispetto a (b^(p^(r – 1) * q^s) – 1) * (b^(p^r * q^(s – 1)) – 1) / (b^(p^(r – 1)*q^(s – 1)) – 1) (Vladimir Sheverel 2008) e in particolare (b – 1) * (b^(p * q) – 1) / ((b^p – 1) * (b^q – 1)) è primo o overpseudoprimo in base b se e solo se è primo rispetto a (b^p – 1) * (b^q) – 1) / (b – 1).

Se p e q sono primi con p > q(b – 1) * (b^(p * q) – 1) / ((b^p – 1) * (b^q – 1)) è primo o overpseudoprimo in base b se e solo se n non è multiplo di p; se n è multiplo di pn / p è primo o overpseudoprimo in base b.

 

Un numero primo si dice “primo di Wieferich generalizzato in base b” se p2 divide bp – 1 – 1.

Si chiama “ordine” di un primo di Wieferich generalizzato p il massimo valore di w tale che pw + 1 divida bp – 1.

Un primo p è un primo di Wieferich generalizzato in base b di ordine almeno w se e solo se pw + 1 è un overpseudoprimo in base b (Vladimir Sheverel, 2008). I quadrati dei primi di Wieferich generalizzati in base b sono quindi overpseudoprimi in base b.

Se p è overpseudoprimo in base b, non è multiplo di quadrati, a meno che sia multiplo di quadrati di primi di Wieferich in base b (Vladimir Sheverel, 2008). Per esempio, 121 = 112 è overpseudoprimo in base 3 e 11 è un primo di Wieferich in base 3.

 

Se n è il prodotto di primi distinti, il massimo dei quali è p, se m uguale al prodotto, calcolato sui divisori d di n, di b^((d – 1) * μ(d) * μ(n)) non è multiplo di p, m è primo o overpseudoprimo in base b, altrimenti m / p è primo o overpseudoprimo in base b.

 

Gli overpseudoprimi noti in base 2 sono: 2047, 3277, 4033, 8321, 65281, 80581, 85489, 88357, 104653, 130561, 220729, 253241, 256999, 280601, 390937, 458989, 486737, 514447, 580337, 818201, 838861, 877099, 916327, 976873, 1016801, 1082401, 1145257, 1194649, 1207361, 1251949, 1252697, 1325843 (Vladimir Sheverel, The Online Encyclopedia of Integer Sequences http://oeis.org).

 

Gli overpseudoprimi noti in base 3 sono: 121, 703, 3281, 8401, 12403, 31621, 44287, 47197, 55969, 74593, 79003, 88573, 97567, 105163, 112141, 211411, 221761, 226801, 228073, 293401, 313447, 320167, 328021, 340033, 359341, 432821, 443713, 453259, 478297, 497503, 504913, 679057, 709873, 801139, 867043, 894781, 973241, 1042417 (Vladimir Sheverel, The Online Encyclopedia of Integer Sequences http://oeis.org).

 

Gli overpseudoprimi noti in base 5 sono: 781, 1541, 5461, 13021, 15751, 25351, 29539, 38081, 40501, 79381, 100651, 121463, 133141, 195313, 216457, 315121, 318551, 319507, 326929, 341531, 353827, 375601, 416641, 432821, 432821, 453331, 464881, 498451, 555397, 556421, 753667, 764941, 863329, 872101 (Vladimir Sheverel, The Online Encyclopedia of Integer Sequences http://oeis.org).

 

Il minimo overpseudoprimo in base 2 che sia anche un numero di Carmichael è 541955409 (Vladimir Sheverel, 2008).

Contattami

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