L'essentiel à connaître
L'arithmétique modulaire, souvent appelée "arithmétique de l'horloge", s'intéresse aux restes des divisions euclidiennes. On dit que deux entiers a et b sont congrus modulo n si leur différence est un multiple de n. En d'autres termes, ils ont le même reste dans la division par n. C'est un outil puissant qui permet de travailler sur des ensembles finis (les restes possibles entre 0 et n-1), transformant des problèmes de nombres infinis en calculs cycliques simples.
Au cœur de cette discipline se trouve le calcul du PGCD (Plus Grand Commun Diviseur). L'algorithme d'Euclide est la méthode de référence pour le trouver rapidement. Cette notion est inséparable de l'identité de Bézout, qui affirme que pour deux nombres a et b, il existe toujours des entiers x et y tels que ax + by = PGCD(a, b). Ces fondements permettent de définir l'inverse modulaire, une opération cruciale où l'on cherche un nombre qui, multiplié par un autre, donne 1 modulo n.
Définition : Soit n un entier naturel. On dit que a ≡ b [n] si et seulement s'il existe un entier k tel que a - b = k * n.
À retenir : Le calcul modulaire conserve l'addition et la multiplication : si a ≡ b [n] et c ≡ d [n], alors (a+c) ≡ (b+d) [n] et (a*c) ≡ (b*d) [n].
Les points clés
L'application la plus célèbre aujourd'hui est la cryptographie asymétrique, notamment l'algorithme RSA. Il repose sur la difficulté de factoriser de très grands nombres premiers. En utilisant les propriétés des puissances modulaires (Petit Théorème de Fermat), on peut chiffrer un message avec une clé publique tout le monde connaît, alors que seul le détenteur de la clé privée peut le déchiffrer. Sans l'arithmétique modulaire, nos transactions bancaires et nos emails ne seraient pas sécurisés.
Il existe également des outils comme le Théorème des Restes Chinois, qui permet de résoudre des systèmes d'équations de congruences. C'est une technique ancestrale mais toujours utilisée en informatique pour accélérer certains calculs sur de très grands nombres en les décomposant en plusieurs petits calculs indépendants. Comprendre ces mécanismes, c'est comprendre comment les ordinateurs gèrent la sécurité et la précision des données.
Formule : Petit Théorème de Fermat : Si p est un nombre premier et a n'est pas divisible par p, alors a^(p-1) ≡ 1 [p].
Piège classique : Attention, on ne peut pas diviser de chaque côté d'une congruence comme dans une égalité classique ! Pour "diviser", il faut multiplier par l'inverse modulaire, qui n'existe que si le nombre est premier avec le modulo.
Quiz : Teste tes connaissances
Question 1 : Quelle est la valeur de 17 modulo 5 ?
Réponse : B. En divisant 17 par 5, on obtient 3 (le quotient) car 5 * 3 = 15. Le reste est donc 17 - 15 = 2. On écrit 17 ≡ 2 [5].
Question 2 : Si a ≡ 3 [7], à quoi est congru a² modulo 7 ?
Réponse : C. Grâce aux propriétés de la multiplication modulaire, a² ≡ 3² [7], donc a² ≡ 9 [7]. Puisque 9 = 7 * 1 + 2, on a 9 ≡ 2 [7].
Question 3 : Quel algorithme permet de calculer efficacement le PGCD de deux nombres ?
Réponse : A. L'algorithme d'Euclide procède par divisions successives : PGCD(a, b) = PGCD(b, reste de a/b). C'est l'un des algorithmes les plus anciens et les plus efficaces.
Question 4 : Que dit l'identité de Bézout pour deux entiers a et b de PGCD d ?
Réponse : D. C'est un théorème fondamental. Si d=1, on dit que a et b sont premiers entre eux, et l'identité ax + by = 1 permet de trouver l'inverse de a modulo b.
Question 5 : Quelle est la condition pour que l'entier 'a' possèd'un inverse modulo 'n' ?
Réponse : B. L'existence de l'inverse découle de Bézout. Si PGCD(a, n) = 1, alors il existe x tel que ax + ny = 1, ce qui implique ax ≡ 1 [n]. x est alors l'inverse de a.
Question 6 : Selon le Petit Théorème de Fermat, si p = 5 et a = 2, alors 2⁴ est congru à quoi modulo 5 ?
Réponse : C. Le théorème dit que a^(p-1) ≡ 1 [p]. Ici p-1 = 4, donc 2⁴ ≡ 1 [5]. En vérifiant : 2⁴ = 16, et 16 = 3 * 5 + 1.
Question 7 : Dans le système cryptographique RSA, quelle opération mathématique est considérée comme "difficile" à inverser ?
Réponse : A. Multiplier deux nombres premiers est facile pour un ordinateur, mais retrouver les facteurs premiers à partir du résultat est extrêmement long (exponentiel) pour de très grands nombres.
Question 8 : Que vaut le PGCD(48, 18) ?
Réponse : C. 48 = 18 2 + 12 ; 18 = 12 1 + 6 ; 12 = 6 * 2 + 0. Le dernier reste non nul est 6. C'est donc le plus grand diviseur commun.
Question 9 : Quelle est l'utilité du Théorème des Restes Chinois ?
Réponse : B. Il permet de trouver un nombre x satisfaisant plusieurs conditions (ex: x ≡ 2 [3] et x ≡ 3 [5]), à condition que les modulos soient premiers entre eux.
Question 10 : Quel est l'inverse de 3 modulo 7 ?
Réponse : D. On cherche x tel que 3 x ≡ 1 [7]. Testons : 31=3, 3*2=6, 3*3=9≡2, 3*4=12≡5, 3*5=15≡1. Donc 5 est bien l'inverse de 3 modulo 7.
Question 11 : Si n est un nombre premier, combien y a-t-il d'éléments inversibles dans l'ensemble des restes modulo n ?
Réponse : A. Si n est premier, tous les nombres de 1 à n-1 sont premiers avec n. Seul 0 n'est jamais inversible. Il y a donc n-1 éléments inversibles.
Question 12 : Quel est le reste de 10^100 modulo 9 ?
Réponse : C. 10 ≡ 1 [9]. Donc 10^100 ≡ 1^100 [9]. Comme 1 puissance n'importe quoi vaut 1, le reste est 1. Simple et efficace !
Question 13 : Dans RSA, si on connaît la clé publique (n, e), pourquoi ne peut-on pas trouver facilement la clé privée d ?
Réponse : B. d est l'inverse de e modulo φ(n). Pour calculer φ(n) = (p-1)(q-1), il faut connaître p et q. Or, extraire p et q de n=p*q est le problème difficile sur lequel repose la sécurité.
Question 14 : Un nombre est divisible par 9 si et seulement si :
Réponse : A. C'est une application directe des congruences. Comme 10 ≡ 1 [9], alors 10^k ≡ 1^k ≡ 1 [9]. Un nombre s'écrivant Σ a_k * 10^k est donc congru à la somme de ses chiffres Σ a_k modulo 9.
Question 15 : Quel est le résultat de (-1) modulo 10 ?
Réponse : C. Par convention, le reste d'une division euclidienne doit être positif (entre 0 et n-1). On ajoute donc le modulo jusqu'à obtenir un nombre positif : -1 + 10 = 9.
Comment ORBITECH Peut T'aider
ORBITECH AI Academy met à ta disposition des outils concrets pour réviser plus efficacement et progresser à ton rythme.
- Générateur de Quiz : crée des quiz personnalisés pour tester tes connaissances et identifier tes lacunes.
- Générateur d'Exercices : crée des exercices d'entraînement adaptés à ton niveau avec corrections détaillées.
- Calculatrice Scientifique : effectue des calculs avancés avec historique et graphiques de fonctions.
- Générateur de Résumés : transforme tes cours en fiches de révision claires et structurées.
Tous ces outils sont disponibles sur ta plateforme ORBITECH. Connecte-toi et explore ceux qui correspondent le mieux à tes besoins !