Arithmétique modulaire

 

Définitions - Explications

L'arithmétique modulaire est une branche des mathématique utilisant un espace fini de nombres entiers.

Nous utilisons tous les jours cette arithmétique pour compter les heures,minutes,secondes ,les angles...; Les ordinateurs utilisent aussi cette arithmétique puisque la capacité d'un processeur n'est pas infinie (exemple pour un ordinateur 64bits le nombre entier se limitera à +ou-263.

Important : On peut compter modulo N de 0 à N-1 , a N-1 on reprend à 0. Exemple si l'on compte les minutes, l'on compte de 0 à 59 minutes.

 

C'est aussi la base du petit théoréme de Fermat sur les nombres premiers.

 

Différences de notation et de logique:

Division Euclidienne:

Dividende/Diviseur=Quotient il reste le Reste

Exemple: 90 minutes => 1 heure 30 minutes

En arithmétique l'on calculerait 90/60 ,1h est le quotient ,30 le reste des minutes: le modulo de 90/60 est 30

L'opération division Euclidienne renvoie 2 nombres: Quotient et reste

 

Informatique (ou calculatrices):

Tableurs

modulo(Dividende;Diviseur)=Reste

La fonction modulo renvoie le reste, pour connaître le quotient il faut utiliser une autre fonction : la division

Quotient=Dividende/Diviseur

L'on dit : le modulo (C.A.D le RESTE) de a et b = reste

 

Arithmétique modulaire:

En arithmétique modulaire l'on écrit:

Dividende reste (mod Diviseur)

L'on dit : le Dividende est congru au reste modulo Diviseur, (C.A.D le DIVISEUR)

90 30 (mod 60) ; 90 est congru à (30 mod 60)

Notez la différence , le diviseur se situe à droite de l'expression ,aprés mod

Différences de notations et de vocabulaire

Informatique
Arithmétique.
Arith. modulaire

Dans un tableur (open office):

modulo(dividende;diviseur)=reste

modulo(12;7)=>5

 

Dividende/Diviseur =>reste

 

On retrouve aussi cette fonction dans différents languages informatique

 

Java,PHP,C:r= a & b ;

r est le reste de la division de a par b

 

SQL: MOD

 

Windev: modulo(a,b)

 

Division Euclidienne

 

on dit que le Dividende est congru au Reste ( modulo Diviseur)

veut dire congru

 

Exemple:

12 5 (mod 7)

12 est congru à 5 modulo 7

 

L'on dit aussi que 12 appartient à la classe 5 modulo 7

 

 

 

En résumé: Dividende  Reste (mod Diviseur) <=> modulo (Dividende/Diviseur) = Reste

Dans la définition des anneaux modulaires , les couples de Dividende/diviseurs donnant un reste  sont appelés éléments de la classe

 

Representation fractionnaire des nombres modulaires

L'on peut aussi représenter les nombres modulaires comme des fractions pour comprendre certains aspects de l'arithetique modulaire : nombres négatifs, inverses, divisions modulaires, PGCD

2 modulo 3 ou -1 modulo 3

n 2 mod 3

Si l'on calcule 5 modulo 3 , l'on obtient 5 congru à2 modulo 3 ce qui donne la fraction suivante : 1+ 2/3 que l'on peut aussi représenter par (3+2)/3

L'on peut aussi dire 5 -1 modulo 3 si l'on considère la partie blanche (détaillé dans nombres négatifs)

 

Travailler avec des congruences différentes :

ajout de 2 modulos différents

1/2 + 1/3 produit un "rectangle commun" de 6

Si l'on veut ajouter 2 nombres de 2 congruences différentes il faut procéder de la même manière qu'une addition de fraction  (voir détails dans math collège):

L'on fabrique 2 rectangles DONT LES COTES SONT IDENTIQUES (ci contre 3 par 2 =>6)

 

Exemple :

(1 1 (mod 2)) + (2 2 (mod 3))

1/2 + 2/3

Mise au même dénominateur

(3 3 (mod 6)) + (4 4 (mod 6))

(1*3/2*3 + 2*2/3*2) => 3/6 + 4/6

= 7 7 (mod 6) =>  7 1 (mod 6)

= 7/6 => 1 + 1/6

 

Un autre exemple avec les mêmes congruences :

(3 1 (mod 2)) + (8 2 (mod 3))

3/2 + 8/3

(9 3 (mod 6)) + (16 4 (mod 6))

9/6 + 16/6 => (1+3/6) + (2+4/6)

25 1 (mod 6)

25/6 => 4 + 1/6

 

 

Addition et Multiplication des nombres modulaires

L'on peut effectuer toutes les opérations sur les nombres modulaires avec toutefois des particularités:

Addition:

En premier exemple je prends un cercle en ° C.A.D mod 360°, ce qui est une meilleure représentation de l'arithmétique modulaire et des nombres finis puisque nous ne nous préocupons plus du nombre de cercles parcourus (quotient).

Exemple: 110mn + 50 mn = 160mn => 1h 40mn oblige à calculer aussi le nombre d'heures,

320°+90° => 50° peut importe le nombre de cercles parcourus (ici 1 C.A.D 360°)

Addition: (*) Il suffit d'ajouter 2 nombres et de retrancher x fois le modulo (C.A.D le diviseur , sa classe) , 160 mn - (2x60) reste 40

 

110mn + 50mn 40mn (mod 60mn)

320°+90° 50° (mod 360°)

Avec nimporte quel nombre :

 

5+3 1 (mod 7) ; different de 5+3=8

6+3 2 (mod 7)

7+2 0 (mod 9)

 

 

 

Multiplication:

 

La multiplication s'éffectue aussi sans problème puisque = à une suite d'additions: (2+2+2+2=4*2=8)

20 * 4 20 (mod 60) , 4*90 0 (mod 360) mais aussi :5*3 1 (mod 7)

 

En multiplication modulaire l'on effectue l'opération et l'on débarrasse le résultat du multiple de 7 => 15 1 (mod 7)

 

Formules sur multiplications

si a*b 0 (mod a ) alors a*b 0 (mod b)

3x4 0 (mod 3) => 3x4 0 (mod 4)

un rectangle a*b est divisible par a ou b

 

n! 0 (mod n)

1*2*3*4*5 cette série est divisible forcement par 5 donc

5! 0 (mod 5)

.

Soustraction modulaire

En théorie il suffirait de soustraire le nombre pour obtenir sa congruence :

320-40 congruence280 (mod 360) , vérifions en ajoutant l'inverse du nombre:

320-40(+40) congruence280(+40) (mod 360) <=> 320 320 (mod 360)

5-3 2 (mod 7) <=> 5-3(+3) congruence2(+3) (mod 7) <=> 5 5 (mod 7)

Le temps se couvre...

 

9-6 3 (mod 7) <=> 9-6(+6) 3(+6) =>99 (mod 7) 

Or 9 2 (mod 7)... Ce qui est logique et illogique , logique car 9-6 3 (mod 7) <> 9-0 2 (mod 7)...(9-6 3 (mod 7) <=> -4 3 (mod 7) est une congruence négative   .

(*) Selon l'arithmétique modulaire, il faut ajouter de part et d'autre le nombre que l'on veut retrancher:

9-6(+6) n+(+6) (mod 7) => 2 n+6 (mod 7)

Quel est le nombre qui ajouté à 6 2 ?

si n  = 3 alors 2 (3+6) (mod 7)

9-6 3 (mod 7)

 

 

autres exemples:

 

40-50 x (mod 60)

Quel est le nombre qui ajouter à 50 40?

si x = 50 alors 50+50 40 (mod 60)

40-50 50 (mod 60)

 

90-50 x (mod 60) => (90 30 (mod 60) - 50 x (mod 60)

30-50 x (mod 60) => 30 x +50 (mod 60)

Quel est le nombre qui ajouter à 50 30?

si x = 40 alors 40+50 30 (mod 60)

30-50 40 (mod 60)

 

90-50 40 (mod 60) =>90-50+(50) 40(+50) (mod 60) => 90 90 (mod 60)

3-5 5 (mod 7) => 3-5+(5) 5(+5) (mod 7) => 3 10 (mod 7)

4-5 6 (mod 7)=> 4-5+(5) 6(+5) (mod 7) => 4 11 (mod 7)

 

Congruence négative

 

Cette particularité est utilisée tous les jours pour compter les minutes (sur une horloge)

Ainsi ne dit t'on pas il est 10h moins le quart ? les Anglais ne disent t'il pas it's quater to ten?

l'on ecrirait donc : 600 - 15n (mod 60) => 600-15 45 (mod 60)

Bon evidement , il y à de fortes chances, si on vous demande l'heure et que vous répondiez il est 45 congru 60, l'on réagisse bizarement...!!!

       20     20     20

(0) -20 40 (mod 60) ce qui peut se lire :

 

il faut 20 minutes pour aller à une heure pleine.

 

(a dans sa classe) ou

60-15 -15 (mod 60) => 45 -15 (mod 60)

ce qui se prouve  par :

Etant donné que p 0 (mop p) => p-a 0-a (mod p)

par équivalence

Semble aussi vrai ... -15 60-15 (mod 60) => 15 45 (mod 60)

Sur cet exemple doit t'on considerer le temps en jaune (40 mn) ou en blanc (20 mn) ?

L'on peut dire il est 1h -20 (si l'on considère le blanc) ou 0 h 40 si l'on considère le jaune

Examen de la valeur absolue:

En mathématique 40-50 = -10 l'inverse 50-40 = 10, la valeur absolue est identique

en mathématique modulaire, 40-50 50 (mod 60) ,l'inverse 50-40 10 (mod 60)

Dans cet exemple ,c'est le temps écoulé entre 50 et 40 C.A.D 50 mn

(40-50) C.A.D -10  (mod 60)-10 (mod 60)

si négatif 40-50  -10(+60) mod 60 => ce qui est l'équivalent d'une retenue en soustraction:

L'arithmétique modulaire n'utilise que des nombres entiers naturels,(nombres uniquement positifs), ce qui implique de soustraire le plus grand - le plus petit et des retenues.

L'arithmétique des nombres entiers relatifs utilisent des nombres positifs et négatifs

L'on notera que les nombres binaires sont aussi des nombres entiers naturels , les nombres négatifs sont issus d'un artifice (voir -> complément à deux et L'arithmetica Livre 1 Question 30 )

Méthode n°1

  1. si un des deux nombres faisant partie d'une opération modulaire dépasse son modulo , le convertir dans sa classe : (90-50 n (mod 60) => 30-50 n (mod 60)
  2. Effectuer l'opération normalement :( =>-20 n mod (60) )
  3. Si le nombre est négatif, lui ajouter une mesure (comme le dirait Fermat) : -20+60=40=> -20 40 mod (60)

a1-b1  n (mod p)

a a1 (mod p)

b b1 (mod p)

si a-b<0 alors a1-b1  p-a mod p

Méthode N°2

  1. Soustraire le plus grand - le plus petit
  2. Faire un conversion modulaire si nécéssaire
  3. modulo-n si il a eu une inversion

a1-b1  n (mod p)

|a1-b1| n (mod p)

si b1>a1 alors n=p-n

 

exemples (ci dessus:

90-50 n (mod 60)

 

Exemples:

méthode N°1

conversion de 90 => 30-50 n (mod 60)

réalisation de l'opération 30-50 => -20 n (mod 60)

ajout du modulo, calcul de n  60-20 40 (mod 60)

ce qui donne: 90-50 40 (mod 60)   

 

méthode N°1

=> -2 n (mod 7) => (7)-2 5 (mod 7)

méthode N°2

Soustraire le plus grand du plus petit => 40

Pas d'inversion, donc pas de soustraction modulaire

90-50 40 (mod 60)    3-5 n (mod 7)

 

 

méthode N°2

3-5 n (mod 7) => 2 =>(7-)2 5 (mod 7

4-5 6 (mod 7)=> 1 =>  (7-)2 5 (mod 7)

3-5 5 (mod 7)

 

Sens de comptage /  mystères des congruences

 

Si on lit :n 6 (mod 7)  n représente t'il -1 6 (mod 7) ou 6 6 (mod 7) , est ce -5 ou 2 2 (mod 7) ?

 

Nombres entiers relatifs

sens croissant -4,-3,-2,-1,0,1,2,3 ... sens décroissant 3,2,1,0,-1,-2,-3,-4

 

en modulo 7 sens croissant:

...,5,6,0,1,2,3,...

si les premiers chiffres représentent des nombres négatifs

-2,-1,0,1,2,3

 

en modulo 7 sens décroissant:

3,2,1,0,6,5,4 <=>

-4,-5,-6,0,6,5,4

 

En résumé si l'on lit 5 l'on ne sait pas forcement si il représente 5 ou -2

 

La méthode juste est de considérer un nombre plus petit que la moitié du modulo comme un nombre négatif et plus grand que sa moitié comme un positif:

 

2 est bien 2 (mod 7) plus petit que la moitié de 7.

5 est -2 , 5 plus grand que la moitié.

Table des nombres négatifs en arithmétique modulaire

Opposé d'un nombre fini (mod 7)

Opposé d'un nombre Entier

 

 

 

-1

(7-1) 6

-1

1

-2

(7-2) 5

-2

2

-3

....    4

-3

3

-4

3

-4

4

-5

2

-5

5

-6

1

-6

6

0

0

 

 

 

 

 

Division modulaire et Inverse modulaire des nombres entiers

 

Rappel:

En théorie il suffirait de diviser le nombre et de prendre le reste pour obtenir sa congruence:

si, en considérant que 5  2 modulo 3,on émet l'hypothèse que 5/3 2 (mod 7) alors  5/3(*3) 2(*3) (mod 7) <=> 15/3 6 (mod 7), ce qui abouti à 5 6 (mod 7)

or 6 * 3 = 18 4 (mod 7)

 

(*) Selon l'arithmétique modulaire, il faut multiplier de part et d'autre de le nombre que l'on veut diviser:

5/3 4 (mod 7) alors  5/3(*3) 4(*3) (mod 7) <=> 15/3 12 (mod 7)

12 étant congru à 5 (mod 7) alors 5/3 4 (mod 7)

Ce qui donne: 5/3 est congru àx (mod p) , multiplication du diviseur

(5*3)/3 congruencex*3 (mod 7) => 5 congruencex*3 (mod 7)

 

 

Quel est le nombre qui , multiplié par 3 est congru à 5 (mod 7) ?

x*3 est congru à5 (mod 7)? x*3-5 est congru à0 (mod 7) ?(si x*3 >5)...

x = 4 car 4*3=12 , 12 est congru à5 (mod 7) <=> 12-5 est congru à0 (mod 7)?

 

a/b est congru àx (mod p) , multiplication du diviseur

(a*b)/b congruencex*b (mod p) => a est congru àx*b mod (p)

si x*b >= a => (x*b)-a est congru à0 (mod p)

Notes:

 

Selon toutes les sources connues (*) , on ne pourait procéder à une division modulaire que si le modulo est un nombre premier.

Congruence de l'inverse de n (1/n est congru à? (mod p) )

Le principe

 

Pour définir une division modulaire , nous  cherchons en premier à multiplier un inverse ce qui nous permettra de chercher un paramètre au lieu de deux.

Exemple a/b nous oblige à chercher a et b (mod p) alors que a * 1/b nous permet de chercher uniquement b (mod p)

Tel que défini a l'heure actuelle un inverse modulaire est défini par l'égalité suivante :  ax − 1 = q ( car  divise ax-1 ) ,ce qui oblige à chercher q et

(ou l'on considère que x est un inverse si le négatif de la somme de m est égale à la somme des négatifs de  ou qu'un inverse modulaire est defini par l'égalité 1/a  = a/a2 = a2/a3 .... modulo p )

Comme il n'est pas possible de diviser un nombre entier en arithmétique modulaire , il nous est donc impossible de manipuler des équations avec les congruences.

Il nous importe donc de trouver une égalité avec un seul paramètre pour pouvoir manipuler les termes de cette équation avec les 4 opérateurs.

Cette égalité nous la trouverons en utilisant un rectangle P+1 ou P-1 dans un carré P

 

Schemas détaillés ci dessous ou aller directemement au sommaire

 

Topologie des rectangles congrus P

Recherche d'égalités par les surfaces :

a et x < p premier

ax est congru à0 (mod p)  = ap ou xp

mais aussi:

ax est congru à0 (mod a) et ax est congru à0 (mod x)

 

Exemple :

Si S = 15 et S est congru à0 (mod 7) alors a=15/7=3 (et x=7) ou x=15/7=3 (et a=3)

 

Un rectangle ax divisible par p est = à ap ou xp

nota: V est le symbole mathématique pour OU

Séparation par développement de 2 rectangles (mod p)

 

Soit P = p1+ p2

Soit S = s1 + s2

 

Pa = a(p1+p2) <=> pa =a.p1 + a.p2

ou

px=x(p1+p2) <=> px=x.p1 + x.p2

 

Les quatres rectangles dans un carré (mod p)

 

Si un rectangle ax (en jaune , exemple ci contre) est P + 1 alors il existe deux rectangles   -1 (en blanc), dans la bande P +1 (horizontale ou verticale)  + rectangle  -1.

 

Il existe donc un autre rectangle congru à +1 symétrique au rectangle P+1

 

Cette configuration est utilisée dans la possibilité 2 des inverses modulaires congrus à (p+1)

 

si un rectangle est  - 1 alors il existe juxtaposé un rectangle P + 1 pouvant représenter ax , couple d'inverses modulaire puisque congru à +1

 

Cette configuration est utilisée dans les inverses modulaires : ajout de P-1

 

D'autre part:   

 

Si le rectangle P+1 à pour grand coté a alors son coté opposé = P+1 / a

 

 

 

1/ Les inverses modulaires : Ajout de (P-1) à a.x

 

nota : a est le nombre dont on cherche l'inverse , x est le a-1 cherché .

Soit a , x < p premier nous rechercherons en premier lieu l'inverse d'un nombre en arithmétique modulaire d'un nombre entier , la division étant égale à la multiplication  par un inverse  (par exemple 4/5 = 4* 1/5)

b/a est congru àx (mod p) nous ferait manipuler les nombres b et a alors qu'en considérant b * 1/a  est congru àx (mod p) nous utiliserons une variable de moins : b

 

ax est congru à1 (mod p)

Si ,la classe des , nous cherchons si 

Pour trouver cette équivalence , dessinons ax est congru à1 (mod p)

Sur cet exemple :

p=7 , x=5

Il faut 3x pour que ax soit congru à 1

15/7 = 2 reste 1

( =2 )

15 est congru à1 p

Nous juxtaposons x fois a dans ce rectangle dont un des deux coté est congru à p ,  

  (*)   , une unité dépassera obligatoirement.

Nota: Si à ce point , si l'on cherchait à calculer , nous aurions 2 inconnues : et x .

(*): il existe si p étant premier, et si p >2 alors ax peut être pair ou impair

Si p est pair (donc non premier) ax doit être impair

 

Donc , pour nous passer du paramètre , pour obtenir un rectangle qui soit totalement est congru àp , nous ajoutons au rectangle ax , le rectangle de surface (p-1)

Si ax est congru à1 (mod p) , alors ax + (p-1) est congru à1+p-1 (mod p)

 

Ajout d'un rectangle  (p-1) au rectangle 1 est congru àax (mod p)

 

 

 

   

Combinaison des deux surfaces : ax et (p-1) afin d'obtenir un égalité

Possibilité 1:

En jaune le rectangle de surface ax , en blanc le rectangle de surface p-1

 

On met le rectangle (p-1) à coté du coté a du rectangle ax et l'on calcule le coté (p-1)/a

 

équivaut aussi (par transformation de p en pa/a et factorisation) :

Égalité que l'on peut maintenant écrire sous la forme

Possibilité 2:

En jaune le rectangle de surface ax , en blanc le rectangle de surface p-1

 

On met le rectangle (p-1) à coté du coté x  du rectangle ax

<=> <=>

 

Égalité que l'on peut maintenant écrire sous la forme:

 

Ces formules impliquent (comme pour la division modulaire) que l'on ne peut pas toujours trouver un inverse entier à un nombre modulaire, ces formules prouveraient que pour trouver un inverse il faut :

Possibilité 1:

(p-1) divisible par a  (p- nombre entier reste entier...)

Possibilité 2:

(p-1) divisible par -a

                      

Ces formules introduisent les nombres rationnels dans les nombres modulaires (rédaction de la suite en cours de depot inpi...)

Vérifications:

1/5 est congru àx (mod 7)

Formule N°1 : x= 7 - (7-1)/5 ; x= 7 - 6/5 ; x = (35-6)/5 ; x= 29/5

ne produit pas un nombre entier mais un rationnel

Formule N°2 : x= (7-1) / (7-5) ; x = 6/2 ; x=3

Vérification : (1*5)/5 est congru à3*5 (mod 7)

1 est congru à15 (mod 7)

 

Vérifions l'inverse:

1/3 est congru àx (mod 7)

Formule N°1 : x=7-(7-1)/3 ; x= 7-(7-1)/3 ; x=7-6/3 ; x=7-2 ; x=5

Formule N°2 : x = (7-1)/(7-3) ; x= 6/4 : x=3/2  ...

2/ Les inverses modulaires : a.a-1  congru à p+1  

 

nota : a est le nombre dont on cherche l'inverse , a-1 est l inverse cherché ; 1/a est l'inverse de a mais a est aussi l'inverse de 1/a

Il existe aussi un couple a . a-1 est congru àP+1 qui sont aussi des inverses modulaires mais qui ne sont pas trouvés par les formules précédentes , dans le cas ou (p-1) est non divisible par a ou -a

Par exemple 1/7 est congru à5 mod 34  (7 x 5 = 35 => 35 est congru à1 mod 34)

 

C'est aussi le cas des nombres dont les inverses sont egaux à eux mêmes C.A.D à par

exemple 1/4 est congru à4 mod 15  (4 x 4 = 16 => 4² est congru à1 mod 15)

Ces inverses modulaires sont considérés comme des cas particuliers, or ils ne le sont pas, ils font partis des cas congrus à p+1

 

Possibilité 1:

(p+1) divisible par a

Exemple P=14 : si A =5 => x=3 si A =3 => x = 5

donc

P+1 contient x fois a donc son coté =  x

Exemple A=3 , X=5 ,p = 14 => 15 est congru à1 (mod 14)

Possibilité 2:

(p+1) divisible par (p-a)

Il existe un second inverse modulaire tel que

 c'est à dire P moins le coté opposé au rectangle P+1      

P au même dénominateur

 <=>  

 

Etude novembre 2011 pages inverses modulaires en cours de modifications

 

Division modulaire

l suffit de multiplier l'inverse ( si il existe )par son dividende et d'en calculer son modulo

 

Exemple :

4/5 est congru àx (mod 7) l'inverse de 1/5 est 3

calculons donc 3*4 est congru àx (mod 7) , 12 est congru à5 (mod 7)

4/5 est congru à5 (mod 7)

Vérification : 4(*5)/5 est congru à5(*5) (mod 7) <=> 4 est congru à25 (mod 7)

 

4/3 est congru àx (mod 7) l'inverse de 1/3 est 5

calculons donc 5*4 est congru àx (mod 7) , 20 est congru à6 (mod 7)

4/3 est congru à6 (mod 7)

 

Vérifions : 4(*3)/3 est congru à6(*3) (mod 7) <=> 4 est congru à18 (mod 7)

 

Pour illustrer ces notions voir : Calculatrice modulaire

Note importante: ces formules fonctionnent aussi avec p non premier !!!

Suite de l'étude sur la division modulaire:

Les inverses modulairesInv modulaire : Etude de fonctionsDiv modulaire: Etudes des rationnelsInv modulaire: Etudes des puissancesDiv modulaire : PCDD-k-BezoudDiv modulaire: Etude Nombres premiers

 

Résumé / Formules modulaires

Mise au même dénominateur:

 

inverse en addition d'un nombre modulaire (-a)

 

Inverse en multiplication d'un nombre modulaire (1/a)

 

Patrick Stoltz le 1/12/2011 publié sur schemath.com ce jour – dépôt INPI 390953-290710

Accueil Schemath.comindex schemath.com
L'arithmetica DiophanteNombres polygonauxLa clef de FermatN premiers Petit Théoreme. Arithmétique modulaireCarrés topologiquesBoite A outilsAvis / Contact

 

(*): Les énigmes mathématiques du 3ém millénaire de Keith Delvin Editions Le Pommier / Internet

Voir aussi l'article (en Anglais) sur wikipédia