NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 04/04/2018

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique       Brèves de Maths    

            

Arithmétique

 

Débutants

Opérations

MODULO

 

Glossaire

Nombres

 

 

INDEX

 

Théorie des nombres

 

Introduction

Mod 9, 10, 11

Applications

Jeux

Théorie

Carrés

Propriétés

Calculs

Parité

7 ^ 7 ^ 7

Carrés et Cubes

Sun Zi

1110 = 32 mod 71

Terminale S

 

Sommaire de cette page

>>> Propriétés des congruences

>>> Équations avec les congruences

>>> Classes complètes de congruences

 

 

 

 

  

Propriétés des CONGRUENCES

Modulo & Résidus

Voir préalablement Base de la théorie

 

  

PROPRIÉTÉS DES CONGRUENCES

 

Même chose

Ces écritures sont équivalentes

a  b (mod m)

b  a (mod m)

a – b   0 (mod m)

a – b = k.m

b est nommé résidu  (ou reste) de a modulo m.

Cette sorte d'égalité est baptisée congruence.

 

Détermination

 

Soit a  b (mod m)

Soit a  b (mod m)

Voir Tiers exclu

 

 

Relation d'équivalence

*            La relation de congruence modulo m est une relation d'équivalence entre les entiers rationnels, soit:

 

Réflexivité

a  a (mod m)

Pour tout entier a

Symétrie

Si a  b (mod m)

Alors b  a (mod m)

Transitivité

Si a  b (mod m)

et b  c (mod m)

Alors a  c (mod m)

 

 

Multiples

 Si m est un multiple de m'

a  b (mod m)

a  b (mod m')

Si m est un multiple de m', m'', ...

Et m', m'', ... sont deux à deux

premiers entre eux

a  b (mod m)

a  b (mod m')

a  b (mod m'')

    etc.

 

Si a  b (mod m)

                                et c > 0

a.c  b.c (mod m)

a.c  b.c (mod m.c)

 

Opérations

 Si a  b (mod m)

a + x  b + x (mod m)

a – x  b – x (mod m)

a . x  b . x (mod m)

a . x  b . x (mod m . x)

Si a  b (mod m) et d diviseur commun de a et b premier avec m

a / d  b / d (mod m)

Si a + b  c (mod m)

a  c – b (mod m)

Si a – b  c (mod m)

a  c + b (mod m)

Si a + b  c + d (mod m)

a – b  c – d (mod m)

a . b  c . d (mod m)

Si a  a' (mod m)

et b  b' (mod m)

a + b  a' + b' (mod m)

a – b  a' – b' (mod m)

 

a . b  a' . b' (mod m)

 

Si a  b (mod m)

an  bn (mod m)

Si ap   bp (mod m)

ap  bp (mod m² )

Si a  b (mod m)

Et c  d (mod m)

En général

xa    xb (mod m)

ac    bd (mod m)

 

 

 

 

Égalités

Si a  b (mod 0)

a = b

a.x  a.y (mod m) si et seulement si

Si a.x  a.y (mod m)

                                    et (a, m) = 1

x  y (mod m)

 

Multi-modulos

x  y ( mod m )

x  y ( mod m' )

                               (m m') = 1

x  y ( mod m.m' )

x  y ( mod m )

x  y ( mod m' )

                               (m m') = c

x  y ( mod c )

x  y ( mod mi ) pour i = {1, 2 … r}

                          si et seulement si

x  y ( mod [m1 , m2mr ] )

(a, m) = PGCD (a, m); [a, m] = PPCM (a, m)

 

Fractions (exemples)

2 x 4  1 (mod 7)

 

Fonctions

Si f(x) est un polynôme à coefficients entiers

a  b (mod m)

f(a)  f(b) (mod m)

 

 

 

ÉQUATIONS AVEC LES CONGRUENCES

 

Résolution

 

 a . x  b (mod m)

Solution existe si :

b multiple de g.

 

Si x0 est une solution

Il y a g solutions :

x = x0 + k . m / g

 

 

g = PGCD (a, m)

 

 

On note g le PGCD (2e lettre) car p est déjà réservé  aux nombres premiers.

 

Exemples

 

*            Recherche des cas, par programme, pour lesquels le résidu:

 

r = (a . x – b) (mod m) = 0

 

On fixe a, b et m

a

x

b

m

g

r

3

4

5

7

1

0

11

1

0

18

1

0

25

1

0

32

1

0

 

Notez

g = PGCD (a, m) = 1

 

a = 3 et m = 7

sont premiers entre eux

 

Notez également

 

Écart entre les x successifs

= 7 = m / g

 

Solutions possibles

 

*            On maintient a = 3 et b = 5

*            On cherche la première solution en x pour les valeurs de m successives:

 

a

x

b

m

g

r

3

1

5

2

1

0

3

4

1

0

5

5

1

0

4

7

1

0

7

8

1

0

5

10

1

0

 

 

Colonne : première solution.

 

Colonne m : seules valeurs <10 pour lesquelles il existe une solution.

 

m = 3 et ses multiples ne marchent pas !

 

Dans ces cas g = PGCD(a, m) = 3 et 3 ne divise pas b = 5

=> Pas de solution, cela est conforme à notre théorème.

 

Même recherche

 

*            avec a = 25 multiple de b = 5

a

x

b

m

g

r

25

1

5

2

1

0

2

3

1

0

1

4

1

0

1

5

5

0

5

6

1

0

3

7

1

0

5

8

1

0

2

9

1

0

1

10

5

0

 

 

 

Voir Calculs (restes chinois)

  

CLASSES COMPLÈTES DE CONGRUENCES

 

Classe de résidus

*            Soit la classe S dans laquelle on trouve les résidus r

avec les propriétés équivalentes suivantes :

 

a (mod m)

donne un résidu unique r de S.

Un seul résidu quelconque r de S

suffit pour définir toute la classe S.

Les résidus r de S, pris deux à deux

sont non congrus modulo m.

 

 

*            Si dans S, on trouve effectivement tous les résidus possibles

(selon l'une des trois propriétés équivalentes ci-dessus)

S est un système complet de résidus modulo m

 

 

 

 

Suite

Retour

*    Congruences – Exemples de calculs

*    Approche

Voir

*    Carrés

*    Divisibilité

*    Clé de divisibilité, une application de la théorie du modulo

*    La division

*    Exemple d'application du modulo en Codage RSA

Aussi

*    Calcul mental

*    Géométrie

*    Nombres Premiers

*    Nombres Rationnels

*    Preuve par 9Glossaire

*    Théorie des nombres

*    Variations sur les carrés

Cette page

http://villemin.gerard.free.fr/ThNbDemo/ModCongr.htm