ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges
 

Nombres de Carmichael             Programme JavaScript

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 an a [n]

  Gauss et la notion de congruence 

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 :

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, ...

Programme Nombres de Carmichael en JavaScript

 La fonction prem() est identique à celle étudiée dans la recherche de primarité d'un nombre donné. La fonction pgcd() est identique à celle étudiée dans la recherche du pgcd par l'algorithme d'Euclide.

 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>

 

Programme des nombres de Carmichael dans [a,b] donné :                  Nombres pseudo-premiers :


© Serge Mehl - www.chronomath.com