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-2^63.

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 schemath.com 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 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))	(13/23 + 22/32) => 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 congruence 280 (mod 360) , vérifions en ajoutant l'inverse du nombre:

320-40(+40) congruence 280(+40) (mod 360) <=> 320 320 (mod 360)

5-3 2 (mod 7) <=> 5-3(+3) congruence 2(+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)

Méthode n°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)
Effectuer l'opération normalement :( =>-20 n mod (60) )
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

Soustraire le plus grand - le plus petit
Faire un conversion modulaire si nécéssaire
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 congruence x*3 (mod 7) => 5 x*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 0 (mod 7) ?(si x*3 >5)...

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

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

(a*b)/b congruence x*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 ? (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 )

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

Topologie des rectangles congrus P

Recherche d'égalités par les surfaces :

a et x < p premier

ax 0 (mod p) = ap ou xp

mais aussi:

ax 0 (mod a) et ax 0 (mod x)

Exemple :

Si S = 15 et S 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 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 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 1 p
Nous juxtaposons x fois a dans ce rectangle dont un des deux coté 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 p , nous ajoutons au rectangle ax , le rectangle de surface (p-1) Si ax 1 (mod p) , alors ax + (p-1) 1+p-1 (mod p) Ajout d'un rectangle (p-1) au rectangle 1 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 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 3*5 (mod 7)

1 15 (mod 7)

Vérifions l'inverse:

1/3 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 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 5 mod 34 (7 x 5 = 35 => 35 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 4 mod 15 (4 x 4 = 16 => 4² 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 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 x (mod 7) l'inverse de 1/5 est 3

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

4/5 5 (mod 7)

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

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

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

4/3 6 (mod 7)

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

Pour illustrer ces notions voir :

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

Suite de l'étude sur la division modulaire:

Les inverses modulaires

Inv modulaire : Etude de fonctions

Div modulaire: Etudes des rationnels

Inv modulaire: Etudes des puissances

Div modulaire : PCDD-k-Bezoud

Div 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

Carrés topologiques

Fermat : Une solution logique

Nombres polygonaux

Arithmétique modulaire

Conjecture N premiers

(*): 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