20. Prouver que deux nombres sont premiers entre eux

Comment savoir si deux nombres sont premiers entre eux en Terminale ?

En spécialité Maths expertes, l'arithmétique occupe une place centrale. L'une des compétences fondamentales est de vérifier si deux entiers sont premiers entre eux. La règle d'or est simple : deux nombres sont dits premiers entre eux si, et seulement si, leur Plus Grand Commun Diviseur (PGCD) est égal à 1. Autrement dit, ils n'ont aucun diviseur commun positif autre que 1.

Pour le démontrer, la méthode classique de la décomposition en facteurs premiers peut vite devenir une vraie galère avec de grands nombres. C'est là qu'intervient une méthode beaucoup plus rapide, systématique, et exigée au baccalauréat : l'algorithme d'Euclide.

Comment utiliser l'algorithme d'Euclide pour trouver le PGCD ?

Dans la vidéo de cours, nous t'expliquons comment appliquer l'algorithme d'Euclide, une technique redoutable qui prend littéralement une minute. Le principe est de réaliser une suite de divisions euclidiennes. À chaque nouvelle étape, le diviseur de la division précédente devient le nouveau dividende, et le reste précédent devient le nouveau diviseur.

Prenons l'exemple détaillé dans la vidéo pour montrer que \(71\) et \(60\) sont premiers entre eux. On effectue les divisions euclidiennes successives :

• On divise \(71\) par \(60\) : il y va 1 fois, et il reste 11. Ce qui s'écrit \(71 = 60 \times 1 + 11\).
• On fait ensuite "coulisser" les nombres : le diviseur \(60\) prend la place du \(71\), et le reste \(11\) prend la place du \(60\). On divise alors \(60\) par \(11\) : il y va 5 fois car \(11 \times 5 = 55\), et il reste 5. L'égalité est donc \(60 = 11 \times 5 + 5\).
• On recommence en décalant encore : le \(11\) glisse à la place du dividende et le \(5\) devient le diviseur. On a \(11 = 5 \times 2 + 1\).
• On décale une dernière fois : on divise \(5\) par \(1\). Il y va 5 fois et le reste est 0, soit \(5 = 1 \times 5 + 0\).

On s'arrête dès que l'on obtient un reste nul ! Le théorème d'Euclide nous affirme alors que le PGCD est tout simplement le dernier reste non nul. Ici, il s'agit de \(1\). On conclut donc que \(\text{PGCD}(71; 60) = 1\), ce qui prouve bien que \(71\) et \(60\) sont premiers entre eux.

Quelles sont les autres méthodes pour prouver que deux nombres sont premiers entre eux en Maths expertes ?

L'algorithme d'Euclide est parfait pour des valeurs numériques, mais le programme te demande aussi de savoir travailler avec des expressions littérales (qui dépendent d'un entier \(n\)). C'est tout l'enjeu des 6 exercices interactifs proposés sur cette page.

Voici ce que tu vas travailler et les pièges classiques à éviter pour réussir ta série d'exercices :

• Exercices 1 et 2 : Tu vas pratiquer l'algorithme d'Euclide sur des entiers donnés. Le piège classique est l'erreur de calcul mental lors de la recherche du reste, ou la confusion entre le quotient et le reste au moment de "coulisser" les valeurs.
• Exercice 3 : Tu devras manipuler les propriétés des diviseurs. Si un entier divise \(m\) et \(n\), alors il divise leur somme \(m+n\). L'astuce est de restreindre les valeurs possibles de ce diviseur lorsque la somme aboutit sur un nombre premier.
• Exercice 4 : Tu vas utiliser une combinaison linéaire pour éliminer l'inconnue \(n\) (une introduction logique au théorème de Bézout). L'objectif est de multiplier les deux expressions par les bons coefficients pour que les termes en \(n\) s'annulent parfaitement lors d'une soustraction.
• Exercice 5 : Cet exercice mêle arithmétique et suites récurrentes. Tu devras identifier une combinaison linéaire entre les termes \(u_{n+1}\) et \(u_n\) pour prouver que leur PGCD ne peut être que 1.
• Exercice 6 : Une très belle application qui associe la division euclidienne et les congruences. L'erreur fréquente ici est d'oublier les règles de compatibilité des puissances modulo 3. Reste concentré sur tes restes !

À toi de jouer ! Prends un brouillon, effectue tes calculs et remplis les champs de réponse pour vérifier que tu maîtrises cette compétence incontournable.