Congruence dans Z

Les congruences dans l'ensemble Z est un cours au programme de terminale scientifique spé maths. Il vous faudra maîtriser cette notion pour assurer face à l'exercice de spécialité lors de l'épreuve du Baccalauréat ! Relisez régulièrement cette...

Document rédigé par un prof Congruence dans Z

Le contenu du document

Les congruences dans l'ensemble Z est un cours au programme de terminale scientifique spé maths. Il vous faudra maîtriser cette notion pour assurer face à l'exercice de spécialité lors de l'épreuve du Baccalauréat ! Relisez régulièrement cette fiche pour vous remémorer les propriétés et bien comprendre comment utiliser cet outil mathématique.

I - Définition

Soit m un naturel, dire que deux entiers relatifs a et a' sont congrus modulo m signifie qu'ils sont le même reste dans la division euclidienne par m ou ce qui est équivalent : a-a est divisible par m.
Le naturel m s'appelle le module de la congruence.
On note a ? a' (modulo m)
a ? a' [m]

II - Démonstration

1 - a et a' ont le même reste dans la division par m

a=m*q+r avec 0?r
a-a'=(m*q)+r-(m*q')-r
a-a'=m(q-q')
Donc a-a' est un multiple de m.

2 - Réciproquement

* a-a' est divisible par m :
* a-a' = k*m (k ? Z)
Soit :
avec 0? r'
On a :
a = a' + k*m
a = m*k'+r'+k*m
a = m*(k+k')+r avec 0? r'
Donc le reste de la division de a par m est aussi r'
Exemple : 31 ? 3[7] car 31-3 = 28 =7*4
-3 ? 2[5] car -3-2 = -5 = 5*(-1)
9 ? -1[10] car 9-(-1) = 10

Remarque :

Si a est divisible par m, alors : a ? 0[m]
1. Règles de calcul
a. a ? a car a-a = 0 = 0*m
b.
Si a ? b[m] Alors a ? c[m]
et b ? c[m]
(transitivité)
c.
Si a ? b[m] Alors a+a' ? b+b'[m]
et a' ? b'[m] a-a' ? b-b'[m]
a*a' ? b*b'[m]

3 - Démonstration

Pour la somme
a ? b donc a-b = k*m
a' ? b' donc a'-b' = k'*m
d'où a-b + a'-b'=(k+k')*m
a+a' - (b+b') =(k+k')*m
a+a' ? b+b' [m]

Cas particuliers :

* Pour tout relatif x, on a : x ? x
donc si a ? b[m] alors :
* a+x ? b+x[m]
* a-x ? b-x[m]
* a*x ? b*x[m]
Si a ? b[m] ,alors pour tout n positif : a^n ? b^b[m]

Récurrence :

* P1 : a ? b vrai
* Pn : a^n ? b^n (hypothèse de récurrence)
On multiplie les deux : a^(n+1) ? b^(n+1)
On peut ajouter, soustraire, multiplier des congruences de même module

Exemple :

i. 3+4 ? 1[6]
d'où 4 ? 1-3 ? -2[6]
ii. 9 ? 3[6]
d'où (9*x) ? (3*x)[6]
iii. x ? 2[5]
y ? 3[5]
donc x+y ? 5 ? 0 [5]]
et x*y ? 6 ? 1[5]
iv. 10 ? 1[9]
donc 10^n ? 1^n ? 1[9]
Attention : Ne pas simplifier une congruence !

Exemple :

2*7 ? 6[8]
Peut-on simplifier par 2 ?
Non : 7 ? 3[8].
4 est un diviseur de 8.
On ne peut simplifier que si x et m sont premiers entre eux :
Si a*x ? a'*x[m]
alors a ? a'[m]

4 - Démonstration

a*x ? a'*x[m]
(a*x) -(a'*x) = 0[m]
(a-a')*x ? m*k
Donc m divise (a-a')*x et m est premier avec x (d'après le théorème de Gauss) m divise a-a'.
Alors a ? a'[m] . On a simplifié par x.
A savoir :
Tout naturel est congru, modulo 10, au chiffre de ses unités :
n= ap*.......a1 *a2 = a0 + 10 a1 + 102 *a2 + ... + 10p * ap
Or : 10 ? 0 [10]
10*a1 ? 0 [10]
102*a2 ? 0 [10] Alors : n ? a0 [10]
10p*ap ? 0[10]
a0 ? a0 [10]

III - Exercices

1. Démontrer que le nombre N=a*b*(a2-b2) est divisible par 3, pour tout relatif a et b.
Problème : N ? 0[3]
Les restes possibles sont 0 ;1 ;2 :
a ? 0 et b ? 0
a*b ? 0
N ?0[3]
a ? 1 et b ? 1
a2 ? b2
a2-b2 ? 0
N ? 0
a ? 2 et b ? 2
a2 ? 4 et b2 ? 4
a2-b2 ? 0
N ? 0
a ? 1 et b ? 2
a2 ? 1 et b2 ? 4 ? 1[3]
a2-b2 ? 0
N ? 0
2. Ecrire des congruences plus simples
-Si x ? 16[7] :
alors x ? 2[7]
-Si a ? 25[6] :
alors a ? 1[6]
-Si a ? 29[6] :
alors a ? -1[6]
-Si x ? 14023[7] :
alors x ? 23 ? 2[7]
3. Que faut-il avoir comme condition nécessaire et suffisante pour que l'équation a*x = b[m] admette une solution entière ?
a*x ? b[m]
a*x - b = m*k (k ? Z)
a*x - k*m = b
Pour que x soit un entier solution : il faut que pgcd(a ;m) divise b. (équation diophantienne)
Démontrer :
A=671^800-1 est divisible par 6 :
On regarde si on a 671^800?0[6]
671=666+5
Donc 671?5[6]
671^800-1=5^800-1[6]
Or : 5?-1[6] donc 5^800?(-1)^800?1[6] et 5^800-1=0[6]
Donc A?0[6]
Fin de l'extrait

Vous devez être connecté pour pouvoir lire la suite

Télécharger ce document gratuitement

Donne ton avis !

Rédige ton avis

Votre commentaire est en attente de validation. Il s'affichera dès qu'un membre de Bac S le validera.
Attention, les commentaires doivent avoir un minimum de 50 caractères !
Vous devez donner une note pour valider votre avis.

Chaque semaine recevez des conseils de révisions de la part de votre
coach bac !

Recevoir

Nos infos récentes du Bac S

Communauté au top !

Révise ton BAC
Contenus en illimité

Inscription gratuite

Accès gratuit à bac-s.net pour préparer le bac !

Vous devez être membre de digiSchool bac S

Pas encore inscrit ?

Ou identifiez-vous :

Mot de passe oublié ?