[PDF] Chapitre 1 Arithmétique Partie 4 : Congruences

View - Download Chapitre 1 Arithmétique Partie 4 : Congruences

Previous PDF

Next PDF

TS Spé Lycée Beaussier Mathématiques 1

Chapitre 1

Arithmétique

Partie 4 : Congruences

Activité préparatoire

Le numéro INSEE ou numéro de Sécurité Sociale est formé de 15 chiffres déterminés, pour

chaque individu de la façon suivante :

1 chiffre pour le sexe : Homme 1 ; Femme 2

2 chiffres qui sont les deux derniers chiffres de l"année de naissance

2 chiffres qui sont le mois de naissance

2 chiffres qui sont le département de naissance

3 chiffres codant la commune de naissance

3 chiffres associés au numéro d"inscription sur le registre des naissances

2 chiffres correspondant à une clé de contrôle

La clé de contrôle est ainsi déterminée : On prend le nombre formé par les 13 premiers chiffres, on cherche son reste r dans la division

par 97, la clé est alors égale au nombre 97 - r écrit avec deux chiffres (le premier étant

éventuellement un 0)

1/ Si vous avez connaissance de votre numéro INSEE ou de celui d"un parent, vérifier la clé

de contrôle. Sinon vérifier la clé de contrôle associée au numéro 2 85 05 33 565 001 89

2/ Le numéro précédent a été retranscrit 2 85 05 33 569 001 89 (erreur sur le 10ième chiffre)

Montrer qu"alors la clé de contrôle permet de détecter l"erreur. Vérifier sur un autre exemple choisi par vous qu"une erreur sur un des chiffres va être détectée par la clé de contrôle.

Définition (Congruence)

Soit n un entier naturel.

Soient a et b deux entiers relatifs.

On dit que a est congru à b modulo n, si a et b ont le même reste dans la division euclidienne par n.

On notera a

≡ b (modulo n) ou a ≡ b (n)

Remarques

• a

≡ b (n) ? b ≡ a (n) La relation de congruence est symétrique.

• Si a

• Si a

≡ 0 (n) alors n divise a

Définition équivalente

Soit n un entier naturel.

Soient a et b deux entiers relatifs.

a ≡ b (n) si et seulement si a - b est divisible par n TS Spé Lycée Beaussier Mathématiques 2

Démonstration :

• Si a et b ont le même reste dans la division par n alors eta n q r b n q r′= × + = × +avec q et q′entiers relatifs et r entier naturel. On soustrait membre à membre ces eux égalités pour obtenir ()a b n q q′- = × -et commeq q′-est entier relatif, n divise a - b. • Si maintenant n divise a - b. Effectuons la division euclidienne de a par n et celle de b par n. Il existe ainsi q et q′entiers relatifs et r etr′entier naturel tels que En effectuant la différence membre à membre des égalités précédentes et après réorganisation, on obtient : ()a b n q q r r′ ′- + - = -. Le membre de gauche de l"égalité précédente est divisible par n car a b-l"est par hypothèse et le terme ()n q q′-est de la forme ;nk k??et est par conséquent divisible par n, d"où le résultat par somme. Par

égalité

r r′-est un multiple de n. En considérant (P1) et du fait que le seul multiple de n strictement compris entre -n et n est 0 on conclut que

0r r r r′ ′- = ? =donc a et b ont

même reste dans la division euclidienne par n.

Propriétés :

a, b, c, a′,b′ sont cinq entiers relatifs et n est un entier naturel

• Si a

≡ b (n) et b ≡ c (n) alors a ≡ c (n) (transitivité de la relation de congruence)

• Si a

≡ b (n) et ()a b n′ ′≡ alors ()a a b b n′ ′+ ≡ + ; ()a a b b n′ ′- ≡ - ; ()a a b b n′ ′× ≡ ×

et pour tout entier naturel non nul p, ()p pa b n≡.

• Si a

≡ b (n) alors pour toutc??, ()a c b c n+ ≡ +;()a c b c n- ≡ - et ()a c b c n× ≡ ×

Démonstration

• Si a

≡ b (n) et b ≡ c (n) alors a - b et b - c sont divisibles par n donc par somme a - c est divisible par n donc a ≡ c (n).

• Si a

≡ b (n) et ()a b n′ ′≡alorsa b-et a b′ ′-sont divisibles par n donc par

somme ()a a b b′ ′+ - + est divisible par n, par suite()a a b b n′ ′+ ≡ +.

On montre de même par différence que

()a a b b n′ ′- ≡ -. Ensuite puisqu"il existe deux entiers relatifs k et k′tels quea b k n a b kn- = × ? = + et de même a b k n′ ′ ′= + × , on obtient par produit membres à membres que :

()2aa bb bk n b kn kk n bb bk b k kk n n′ ′ ′ ′ ′ ′ ′ ′ ′= + + + = + + +.

Posons

K bk b k kk n′ ′ ′= + +, K est entier relatif car tous les termes qui le composent le sont,

ainsi

aa bb Kn aa bb Kn′ ′ ′ ′= + ? - = avecK??, ainsiaa bb′ ′-est divisible par n et

finalement ()a a b b n′ ′× ≡ ×. Montrons par récurrence que pour tout entier naturel non nul p, ()p pa b n≡.

Amorce : Pour p = 1,

()()1 1a b n a b n≡ ? ≡ce qui est vrai par hypothèse. Hérédité : On suppose la propriété vraie au rang p, c"est-à-dire que ()p pa b n≡, comme on a de plus

()a b n≡alors par propriété du produit démontrée précédemment : ()p pa a b b n× ≡ ×

et finalement ()1 1p pa b n+ +≡qui démontre la propriété au rang p+1. Conclusion : On a montré par récurrence que pour tout entier naturel non nul p : ()p pa b n≡. TS Spé Lycée Beaussier Mathématiques 3

• ()()a c b c a b+ - + = -est divisible par n car par hypothèse a ≡ b (n), donc()a c b c n+ ≡ +.

On montre de manière analogue que

()a c b c n- ≡ -. Et si maintenanta b-est divisible par n alors pour tout entier relatif c, ()c a b a c b c× - = × - ×est divisible par n comme multiple de a - b qui est lui-même multiple de n. On vient de montrer que ()a c b c n× ≡ ×

Remarque

La relation de congruence est compatible avec l"addition, la soustraction et la multiplication. Attention, la relation de congruence n"est pas compatible avec la division ni avec la racine carrée.

Par exemple 22 ≡ 8 (2) , mais on ne peut pas diviser par 2 pour affirmer que 11 est congru à

4 modulo 2 ou encore 9 ≡ 4 (5) , mais on ne peut pas prendre la racine carrée pour affirmer

que 3 est congru à 2 modulo 5 On ne pourra en général pas simplifier dans une congruence comme on simplifie dans une égalité sans prendre d"immenses précautions :

Une congruence du type 2x ≡ 2y (n) ne pourra pas, en général, être simplifiée par 2.

Exemples

• Soit n un entier naturel, démontrons :

,8 1nn? ? -?est divisible par 7 : ()()()8 1 7 ,8 1 1 7 ,8 1 0 7n n nn n≡ ? ? ? ≡ ≡ ?? ? - ≡? ?donc 7 divise8 1n-. On peut aussi démontrer ce résultat par récurrence comme déjà vu au chapitre 0. • Déterminer le reste dans la division par 7 de

2422 1-. Remarquons déjà que()32 8 1 7= ≡.

Effectuons la division euclidienne de 242 par 3, on obtient : 242 = 3

×80 + 2.

On a donc

80 80242 3 80 2 3 2 32 2 2 2 2 4× += = × = ×.

Finalement

80 803 3 80 32 1 7 2 1 1 7 2 4 4 7≡ ? ≡ ≡ ? × ≡et finalement()2422 1 4 1 3 7- ≡ - ≡.

Comme

• Démontrons que pour tout entier n,

22 1n n+ +n"est pas divisible par 3.

Il n"y a dans le que 3 cas possibles :

si

()()2 20 3 , 2 1 2 0 0 1 1 3n n n≡ + + ≡ × + + ≡donc22 1n n+ +n"est pas divisible par 3

si

()()2 21 3 , 2 1 2 1 1 1 4 1 3n n n≡ + + ≡ × + + ≡ ≡donc22 1n n+ +n"est pas divisible par 3

si

()()2 22 3 , 2 1 2 2 2 1 11 2 3n n n≡ + + ≡ × + + ≡ ≡donc22 1n n+ +n"est pas divisible par 3

On vient de traiter tous les cas possibles et on peut donc conclure que pour tout entier n,

22 1n n+ +n"est pas divisible par 3.

Exercices sur les congruences

Exercice 1 Soit n un entier naturel

1/ Démontrer que si n ≡ 2 (5) ou si n ≡ 3 (5), alors

2n + 1 est un multiple de 5.

2/ Démontrer que pour tout entier naturel n : ()41n n- est un multiple 5.

TS Spé Lycée Beaussier Mathématiques 4

Exercice 2

Démontrer que pour tout entier naturel n,

16 13n n++est divisible par 7.

Exercice 3

1/ Démontrer que

33 10n n+ - est divisible par 13 ? ()3 13n≡ou()5 13n≡

2/ Déterminer le plus petit entier supérieur ou égal à 2500 pour lequel

33 10n n+ -est divisible par 13.

Exercice 4

Montrer qu"un nombre est divisible par 3 (respectivement par 9) si et seulement si la somme des chiffres le composant est divisible par 3 (respectivement par 9)

Exercice 5

1/ Donner suivant les valeurs de l"entier naturel n les restes de la division euclidienne de

2n par 5.

2/ En déduire le reste de la division euclidienne par 5 de 2

3421

3/ Donner le reste de la division euclidienne par 5 de 32123421

4/ Donner le reste de la division euclidienne par 5 de 2223811

Exercice 6

1/ Montrer qu"un nombre

9

1 1 0...n nA a a a a-=écrit en base 9 est divisible par 8 si et seulement si la

somme de ses chiffres

0 1 2 1...n nS a a a a a-= + + + + +est divisible par 8.

2/ Montrer que

5A xyz= est divisible par 6 si et seulement six y z- +est divisible par 6.

Exercice 7

a/ Justifier que 8

2002 + 2 est divisible par 11.

b/ Quel est le dernier chiffre de l"écriture décimale de 8

2010 + 2 ?

Exercice 8

1/ quel est le reste de la division par 8 du nombre

7noù n est un entier naturel.

2/ Pour quels entiers naturels n le nombre

7 4 1nA n n= × + +est-il divisible par 8 ?

Exercice 9

1/ Etudier les restes des divisions par 9 des puissances successives de 2.

2/ Démontrer que le nombre

()2 2 12 2 1 1n nB+= - -est divisible par 9 pour tout entier naturel n.

Exercice 10

Déterminer les restes des divisions de

37n par 11 où n est un entier naturel quelconque.

Exercice 11

Montrer qu"il n"existe pas d"entier relatif n tel que ()21 0 5n n+ + ≡.

Exercice 13

Un entier naturel N s"écrit

5abccaen base 5 et

8bbaben base 8.

1/ Montrer que 309a + 15c = 226b

2/ Montrer que

()0 3b≡. En déduire b.

3/ Montrer que

()2 5a≡. En déduire a et c.

4/ Ecrire N dans le système décimal.

quotesdbs_dbs24.pdfusesText_30

[PDF] les clés de répartition

[PDF] Chaîne d or sur les Psaumes (tome 1) - Bibliothèque Saint Libère

[PDF] Authentification par jeton | Authentificateur USB SafeNet eToken 5110

[PDF] le guide d 'attribution des clés otp - Académie de Créteil

[PDF] CLE OTP - Académie de Grenoble

[PDF] Utiliser la clé OTP

[PDF] Serial number and product key - Cadac Store

[PDF] A TOUS PNC HOP! - UNAC

[PDF] 3SKey - Guide d 'installation du logiciel du token - Swift

[PDF] CléA, ? quoi ça sert? - IPI BN

[PDF] Qu 'est ce que la clef OTP ? (One Time Password)

[PDF] Gographie Term S - mediaeduscoleducationfr - Ministère de l

[PDF] Bien vieillir - Ville de Nantes

[PDF] Guide d 'inscription et d 'utilisation de clicSÉQUR - Équité salariale

[PDF] Approche des clichés sur les Noirs-Africains - Afric 'Impact