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 ?   » Anneau quotient Z/nZ des classes résiduelles modulo n

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  aⁿ ≡ r  [p], n étant un entier naturel. Si a ≡ r  [p], alors aⁿ ≡ rⁿ  [p]. Le programme calcule le reste r' de la division de rⁿ 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 a^k ≡ 1  [p], alors les restes apparaîtront périodiquement tous les k résultats suivants puisque si a ≡ r  [p] et a^k ≡ 1  [p], alors a^k+1 = a^k × a ≡ r × 1= r  [p], a^k+2 ≡ r² [p], etc.

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

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 aⁿ ≡ r  [p]. Si vous cherchez simplement a ≡ r  [p], entrez 1 pour n (valeur par défaut).

• Exemple : on s'intéresse aux restes de 127ⁿ modulo 13. On entre a = 127, p = 13 et n = 12 (= 13 - 1) :

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