Divisibilité et congruences

« Chapitre 2 Divisibilité et congruences dans Z Dans ce chapitre nous allons nous focaliser sur les nombres entiers (N ou Z) et nous allons nous intéresser aux propriétés satisfaites par de tels nombres. 2.1 2.1.1 Introduction Survol historique Cette branche des mathématiques est très ancienne et remonte à l’antiquité : • au 3ième siècle avant J.C., pour la première fois de l’Histoire, Euclide rassemble dans un livre (les Eléments) la majeure partie des connaissances des mathématiciens de l’époque. Parmi eux, il présente la définition de la division euclidienne (celle que vous avez rencontré en primaire). • En −250, Diophante d’Alexandrie explique dans son ouvrage comment résoudre certaines équations dont les solutions sont des nombres entiers ou des fractions.

En Chine, Sun Zi écrit lui aussi un traité de mathématiques et s’intéresse à des problèmes impliquant le reste d’une division euclidienne. • Au 13ième siècle, les problèmes étudiés par Sun Zi sont complètement résolu par Qin Jiushao. Toutefois, son savoir ne dépasse pas les frontières chinoises avant le 20ième siècle. • L’arithmétique est également très étudiée en Inde (Arybhata au 5ième siècle, Brahmagupta au 6ième siècle, Bhaskara au 12ième siècle,.

.

.

). • la civilisation islamique n’est pas reste également.

Non seulement, elle véhicule le savoir acquis par les Grecs, Indiens et Chinois mais elle apporte des connaissances nouvelles Par exemple, Al-Kwarizmi écrit un livre sur la numération indienne. • C’est à partir du 17ième siècle que l’Europe poursuit l’étude de cette branche de mathématique à partir d’une traduction en latin du livre de Diophante.

Les questions soulevées intéressent alors les mathématiciens de l’époque (Fermat, Mersenne, Descartes,.

.

.

) qui continuent d’explorer ce domaine.

A ce moment là, Fermat annonça par missives à un collègue qu’il avait réussi à démontrer un théorème important (le grand théorème de Fermat) mais qu’il n’avait pas la place dans sa lettre pour développer sa démonstration.

Nous ne serons jamais s’il avait 15 CHAPITRE 2.

DIVISIBILITÉ ET CONGRUENCES DANS Z 16 véritablement réussi mais il est certain qu’il fallut attendre les travaux d’Andrew Wiles en 1994 pour avoir une démonstration rigoureuse de l’affirmation de Fermat. • Le 18ième siècle permet de voir briller les génies Euler, Legendre et Gauss dans ce domaine. D’ailleurs, Gauss démontra un théorème remarquable (appelée théorème de réciprocité quadratique) à l’âge de 17 ans.

La théorie des nombres connait un essor sans pareil à cette période et les idées remarquables de Gauss furent enrichies par les travaux de Jacobi et Dirichlet. • Même si nous ne poursuivons pas ce rapide survol historique, soyez certain que l’Histoire ne s’arrête pas ici et que, de nos jours, de nombreux mathématiciens continuent de chercher des solutions à des problèmes provenant de la théorie des nombres. Bien que cela ne soit pas évident du tout, la théorie des nombres (et donc l’arithmétique) a donné naissance à la cryptographie : l’art de coder et décoder des messages.

Par exemple, les protocoles de sécurité d’un site internet, d’une carte bancaire, de l’armée,.

.

.

reposent sur des restes de divisions euclidiennes très compliquées.

Bien entendu, ce résumé est un peu grossier et ne rend pas hommage aux travaux des mathématiciens Rivest, Shamir et Adleman qui ont crée le système de cryptage R.S.A.. 2.1.2 Problèmatique Les objets que nous allons étudier permettent de résoudre le problème suivant. Un satellite artificiel d’observation de la Terre a été placé sur une orbite parallèle à l’équateur à 12 000 km au dessus de la surface du globe.

Nous considérons que sa trajectoire est un cercle dont le centre est celui de la Terre, que sa vitesse est constante et que sa période de révolution est de 7 heures. Nous savons de plus que le 1er janvier 2020 à 0h00, le satellite passe au-dessus de la Colombie et deux heures plus tard il survole le Kenya.

De plus, le 8 janvier à 10h, il se trouve au dessus de l’Indonésie. 1.

Combien de fois le satellite survole-t-il la Colombie le 1er janvier 2020 ? 2.

Donner les horaires de passages du satellite au-dessus du Kenya le 2 janvier. 3.

Le satellite survolera-t-il le Kenya un jour à 0h00 ? 4.

Où se situe le satellite le 30 janiver à 6h00 du matin ? 5.

... 2.2 2.2.1 Divisibilité dans Z Diviseurs et multiples Rappelons que l’ensemble des entiers relatif Z est composé uniquement des entiers positifs et négatifs.

L’ensemble des entiers naturel N est composé uniquement des entiers positifs. √ /Z / Z et 13 ∈ Exemple 2.2.1. 1.

−2 ∈ Z 10000 ∈ Z mais 2 ∈ 2.

3 ∈ N mais 3.15 ∈ / N, −3 ∈ / N et 3 10 ∈ / N. 2.2.

DIVISIBILITÉ DANS Z 17 La première notion que nous allons étudier est celle de la divisibilité.

Dans ce qui suit tout les nombres a, b, c, k, .

.

.

∈ Z Définition 2.2.1.

Nous dirons qu’un nombre a divise un nombre b s’il existe un nombre k ∈ Z tel que b = ak et noterons ceci par a|b.

Nous dirons alors que a est un diviseur de b ; de manière alternative, nous dirons que b est un multiple de a. Remarque. 1.

Il n’est pas difficile d’observer que les nombres 1 et −1 divisent tous les entiers relatifs.

En fait, ce sont les seuls éléments de Z vérifiant cette propriété.

0 est divisible par n’importe quel entier mais ne divise personne. 2.

Il est essentiel que k ∈ Z ; dans ce chapitre à aucun moment k ∈ R. 3.

Si n ∈ Z∗ alors tout diviseur de n est compris entre −|n| et |n|.

En particulier, tout entier relatif non nul admet un nombre fini de diviseur. 4.

Soient a, b ∈ Z alors les propriétés suivantes sont équivalentes a|b ⇐⇒ −a|b ⇐⇒ a|(−b) ⇐⇒ −a|(−b). Il va être important de se familiariser avec ces nouvelles notations et ce nouveau vocabulaire. Voyons quelques exemples. Exemple 2.2.2. 1.

2|8 car 8 = 2 × k avec k = 4 ∈ Z. 2.

6|!21 puisqu’il n’est pas possible de trouver k ∈ Z tel que 21 = 6k. 3.

−124 est bien un multiple de 4 car 4| − 124.

En effet, −121 = 4 × k avec k = −31 ∈ Z. 4.

31 est diviseur de −124 puisque 121 = 31 × k avec k = −4 ∈ Z. Exercices à traiter : 19,26 page 104. Voici un nouveau raisonnement permettant de trouver les solutions entières d’une équation. Exemple 2.2.3.

Déterminons les solutions entières de (E) : x2 − y 2 = 7. 1.

(Analyse) Soit (x; y) un couple de solution de (E), voyons quelles propriétés ce couple doit nécessairement vérifier. x2 − y 2 = 7 ⇐⇒ (x − y)(x + y) = 7. Nous constatons que (x − y) et (x + y) divisent le membre de gauche donc ce sont aussi des diviseurs du membre de droite.

En outre, il facile de déterminer les diviseurs de 7, il s’agit de l’ensemble {−1; 1; 7; −7}.

Nous devons donc résoudre les 4 systèmes d’équations envisageables : ! x + y = −7 x − y = −1 ou ! x + y = −1 x − y = −7 ou ! x+y =1 x−y =7 ou ! x+y =7 x−y =1 CHAPITRE 2.

DIVISIBILITÉ ET CONGRUENCES DANS Z 18 Un simple calcul nous mène à ! ! 2x = −8 2x = −8 ou x − y = −1 x − y = −7 ou ! 2x = 8 x−y =7 ou ! 2x = −8 x−y =1 Les candidats potentiels sont donc (x; y) = (−4; −3) ou (x; y) = (−4; 3) ou (x; y) = (4; −3) ou (x; y) = (4; 3). 2.

(Synthèse) Il ne reste plus qu’à regarder si les couples obtenus sont bien solutions de (E). Ici, c’est bien le cas. " # 3.

(Conclusion) L’ensemble des solutions de (E) est (−4; −3) ; (−4; 3) ; (4; −3) ; (4; 3) . Remarque.

Le raisonnement précédant est un procédé d’analyse/synthèse.

D’abord, nous supposons que les solutions de problèmes existent et cherchons à obtenir une liste réduite de candidats.

Ensuite, nous regardons parmi ces candidats lesquels sont solutions pour enfin conclure. Exercices à traiter : 29 et 35 page 104. Essayons maintenant de voir comment se comporte la propriété de division. Proposition 5 (Transitivité de la divisiblité).

Soient a, b, c ∈ Z.

Si a|b et b|c alors a|c. Démonstration.

(L’idée de la preuve est à retenir) 1.

But : nous voulons montrer que a|c.

Autrement dit, il faut trouver K ∈ Z tel que c = aK. 2.

Par définition, puisque a|b il existe k ∈ Z tel b = ak.

De même, il existe k ′ ∈ Z tel que c = bk ′ (a priori k est différent de k ′ ).

Par suite, c = bk ′ = (ak)k ′ = akk ′ = aK en posant K = kk ′ ∈ Z donc a|c..... »