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 reste 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 connaitre 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

Arithétique modulaire:

En arithétique modulaire l'on ecrit:

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 5 appartient à la classe 7

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

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

Opérations modulaires dans une même classe

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:

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: il est peut ètre temps de prendre un parapluie!!!

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.

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

(a dans sa classe)

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)

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)

donc: Ranger vos parapluies

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)

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°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°1

=> -2 n (mod 7) => (7)-2 5 (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

Table des nombres négatifs en arithmétique modulaire

Inverse d'un nombre fini (mod 7)		Inverse 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

En résumé si l'on lit 5 l'on ne sait pas frocement si il represente 5 ou -2

La méthode juste est de considerer 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 motié.

Division:

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

si 5/3 2 (mod 7) alors 5/3(*3) 2(*3) (mod 7) <=> 15/3 6 (mod 7)

or le reste de 15/3 est 0 et non pas 6

(*) Selon l'aritmé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)?

Donc 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 0 (mod p)

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) )

Nous chercherons en premier lieu l'inverse d'un nombre en arithmétique modulaire , la division étant égale à une multiplication d'inverses, ce qui évite de manipuler un paramètre inutile.

ex a/b est congru à x (mod p) nous ferait manipuler a alors qu'en considerant a * 1/b x (mod p) nous n'avons plus qu'a utiliser b et p... x étant le résultat recherché.

Formules de base:

Si 1/a x (mod p) alors 1 ax (mod p) <= formule de vérification d'un inverse

Exemple: 1/5 3 (mod 7) : pour vérifier 1 3*5 (mod 7)

Exemple: 1/5 x (mod 7) <=> 1 est congru à 5x (mod 7) <=> 5x 1 (mod 7)

Selon la formule des multiplications (a*b est congru à 0 (mod a) <=> a*b 0 (mod b) alors

En théorie l'on cherche à transformer un rectangle en un autre rectangle , ce qui introduit un paramétres supplémentaire , mon idée est de se passer de se paramètre avec l'astuce suivante:

En jaune: ax juxtaposé dans un rectangle mod p ,En blanc p-1

Demonstration par l'exemple 1/5 x (mod 7):

Cet exemple correspond à une vue fractionaire schemath.com inscrite dans un rectangle de p par ?, (? est un paramètre supplémentaire que je ne veut pas utiliser ...) , Dans l'exemple un rectangle de 7 X ?...

On juxtapose x fois des series de a dans ce rectangle comme , une unité dépassera obligatoirement

Pour compléter ce rectangle on ajoute (en blanc) un autre rectangle p-1

On a donc 2 surfaces : ax et p-1 donc:

SI je réajuste ces 2 surfaces en un nouveau rectangle mod a nous avons 2 possiblités: (rappel )

Ce qui est aussi une représentation d'un inverse d'une congruence , la valeur absolue d'un inverse n'étant pas le même nombre.

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 recalcule le nouveau coté (en bas sur l'exemple)

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

<=> <=>

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

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