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

A combien ce nombre est-il congru modulo p ?     

Si a, b et p désignent des entiers relatifs on écrit a ≡ b  [p] pour signifier que a - b est un multiple de p. On dit que a est congru à b modulo p. Il est souvent opportun de connaître le plus petit entier r tel que a ≡ r  [p] : l'entier r est alors le reste de la division euclidienne de a par p.

Dans des exercices, il est également souvent nécessaire de connaître r tel que  an r  [p], n étant un entier naturel. Si a ≡ r  [p], alors an ≡ rn  [p]. Le programme calcule le reste r' de la division de rn par p afin de donner la congruence la plus petite.

En fait tous les résultats intermédiaires sont affichés pour les entiers k n. Si ak ≡ 1  [p], alors les restes apparaîtront périodiquement tous les k résultats suivants puisque si a ≡ r  [p] et ak ≡ 1  [p], alors ak+1 = aka ≡ r1= r  [p], ak+2 ≡ r2 [p], etc.


Existe-t-il un n entier tel que 3n ≡ 1 [144] ?  Rép. : cliquez ici

Programme congruences en JavaScript :

La fonction %, syntaxe a%b, retourne le reste de la division de a par b. Le programme vous demandera successivement le nombre a, le modulo p, puis n tel que an r  [p]. Si vous cherchez simplement a r  [p], entrez 1 pour n (valeur par défaut).



<SCRIPT LANGUAGE=JavaScript>
function congru()
{
a$="";ok=0
a$=prompt("Donnez l'entier naturel a :",a$)
a=eval(a$)
if(a<=0||Math.floor(a)!=a)
{alert("a = "+a+" est incorrect."+"\n"+"Le programme est arrêté");return}

p$="";
p$=prompt("Donnez le modulo p :",p$)
p=eval(p$)
if(p<=1||Math.floor(p)!=p)
{alert("p = "+p+" est incorrect."+"\n"+"Le programme est arrêté");return}

n$="1";
n$=prompt("Donnez l'entier naturel n :",n$)
n=eval(n$)
if(n<=0||Math.floor(n)!=n)
{alert("n = "+n+" est incorrect."+"\n"+"Le programme est arrêté");return}

r1=a%p;rk=r1
alert(a+" est congru à "+r1+" modulo "+p)

if(n>1)
{
for (k=2;k<=n;k++)
{
rk=(rk*r1)%p;  
// récurrence : a^k est congru à r1^k et on affiche le reste de la division de rk par p
if(rk==1&&ok==0){k1=k;ok=1}
if(!confirm(a+"^"+k+" est congru à "+rk+" modulo "+p+"\n"+"Je continue ?")) return
if(ok==1){ok++;alert("Puisque "+a+"^"+k+" est congru à 1, les mêmes restes"+"\n"+"apparaîtront désormais périodiquement.")
}
// fin for
}
// fin if
}
// fin congru
</SCRIPT>


Solution de l'exercice :    

Si 3n ≡ 1 [144], alors 3n - 1 est un multiple de 144. Or =3n - 1 =  3n - 1n = (3 - 1)(3n-1 + 3n-2 + ... + 3 + 1). Donc 3n-1 + 3n-2 + ... + 3 + 1 est multiple de 72, donc multiple de 3. Mais cela est faux car 3n-1 + 3n-2 + ... + 3 + 1 ≡ 1 [3].   N.B. 114 est un leurre, on aurait pu choisir 18... mais c'était trop visible.


© Serge Mehl - www.chronomath.com