Nombres de Carmichael

Un entier naturel n non premier (composé) mais pseudo-premier pour toute base a < n est dit absolument pseudo-premier ou encore nombre de Carmichael du nom du mathématicien américain qui les étudia pour la première fois.

Par définition, un nombre de Carmichael est donc un entier naturel n, non premier, tel que :

Pour tout entier a, 1 < a < n , a et n sont premiers entre eux et aⁿ ≡ a [n]

Le programme ci-dessous recherche si un nombre donné n (impair) est absolument premier. On peut facilement le modifier pour qu'il recherche séquentiellement les nombres de Carmichael dans une fourchette donnée, mais attention au temps de calcul... Rappelons que les premiers nombres sont :

! Attention au temps de calcul pour n > 10000... Votre navigateur devrait vous prévenir après un certain temps...

<SCRIPT LANGUAGE=JavaScript>
var n,t
function carmi()
{
n$="";t=0
n$=prompt("Donnez n, entier, impair :",n$)
n=eval(n$)
if(n<=1||n%2==0||Math.floor(n)!=n)
{alert("n = "+n+" est incorrect."+"\n"+"Le programme est arrêté");return} //--- n doit être impair autre que 1
t=prem(n)
if (t==1){alert(n+" est premier."+"\n"+"Le programme est arrêté");return} //--- n doit être composé
for (a=2;a<n;a++)
{
if (pgcd(n,a)==1)   //--- on a trouvé un candidat
      {
      r1=a%n;rn=r1   // ----- r1 est le reste de la division de la base a par n
      for (i=2;i<=n;i++) {rn=(rn*r1)%n} //------- le reste de la div. de a^n par n est congru à r1^n
      if (rn!=r1) {alert("Vous avez entré n = "+n+"."+"\n"+"C'est fichu pour la base "+a+"."
                       +"\n"+"Car modulo "+n+", on a :"+"\n"+a+"^"+n+" congru à "+rn+".");return}
    }
}
alert(n+" est absolument pseudo-premier.")
}

function pgcd()     //------- routine pgcd
{aa=a
bb=n
while (bb > 0)
{
r = aa % bb
aa = bb
bb = r
}
return aa
}

function prem(n)//------- routine n est-il premier ?
{
d=0;k=1;t=1
if(n==3||n==5||n==7) {return 1}
if(n%3==0){return 0}
while (d*d<=n && t==1)
{
d1=6*k-1;d2=6*k+1
if(n%d1==0 || n%d2==0) {t=0}
k++
d=d2
}
return t
}
</SCRIPT>