19. Trouver un pgcd en fonction de n

Comment trouver le PGCD de deux nombres en fonction de n en Maths expertes ?

Trouver un PGCD qui dépend d'un entier \(n\) est un grand classique du programme d'arithmétique de Terminale. Au premier abord, cela peut sembler complexe, mais la méthode repose toujours sur un principe simple : se débarrasser du \(n\) pour se ramener à des nombres entiers fixes.

Imaginons que l'on cherche \(d\), le PGCD de \(5n+4\) et de \(2n+1\). La propriété fondamentale à utiliser est la suivante : si un nombre \(d\) divise deux nombres, alors il divise n'importe quelle combinaison linéaire de ces deux nombres.

Le but du jeu est de choisir astucieusement les coefficients de cette combinaison linéaire pour éliminer les \(n\). Ici, nous avons \(5n\) d'un côté et \(2n\) de l'autre. En croisant les coefficients (on multiplie le premier par \(2\) et le second par \(5\)) et en faisant une soustraction, les \(n\) disparaissent :

Puisque notre PGCD \(d\) divise \(5n+4\) et \(2n+1\), il divise obligatoirement le résultat de cette combinaison, c'est-à-dire \(3\). Or, \(3\) est un nombre premier. Les seuls diviseurs positifs de \(3\) sont \(1\) et \(3\). On vient donc de prouver que pour n'importe quel entier \(n\), le PGCD vaut soit \(1\), soit \(3\).

Comment utiliser les congruences pour déterminer la valeur exacte du PGCD ?

Savoir que le PGCD vaut \(1\) ou \(3\) n'est pas suffisant. Il faut maintenant déterminer pour quelles valeurs de \(n\) on obtient \(3\), et pour quelles valeurs on obtient \(1\). Pour cela, on utilise les congruences modulo la valeur trouvée (ici modulo \(3\)).

Si le PGCD vaut \(3\), cela signifie que \(3\) divise \(5n+4\) et \(2n+1\). Autrement dit, ces deux expressions doivent être congrues à \(0\) modulo \(3\). Faisons une disjonction des cas (un petit tableau mental) selon les restes possibles de \(n\) modulo \(3\) :

• Si \(n \equiv 0 \ [3]\) : alors \(5n+4 \equiv 0+4 \equiv 1 \ [3]\). Ce n'est pas un multiple de \(3\), donc le PGCD n'est pas \(3\).
• Si \(n \equiv 1 \ [3]\) : alors \(5n+4 \equiv 5(1)+4 \equiv 9 \equiv 0 \ [3]\). On vérifie aussi la deuxième expression : \(2n+1 \equiv 2(1)+1 \equiv 3 \equiv 0 \ [3]\). Ça marche !
• Si \(n \equiv 2 \ [3]\) : alors \(5n+4 \equiv 5(2)+4 \equiv 14 \equiv 2 \ [3]\). Ça ne marche pas.

La conclusion est donc très précise : \(d = 3\) si et seulement si \(n \equiv 1 \ [3]\) (c'est-à-dire si \(n = 3k+1\)). Dans tous les autres cas, le PGCD vaut \(1\).

Quels sont les pièges classiques des exercices de PGCD en Terminale ?

Les 6 exercices interactifs de cette page sont conçus pour te faire maîtriser cette méthode et t'apprendre à contourner les pièges fréquents en devoir surveillé :

La simplification directe (Exercice 2) : Parfois, en cherchant à éliminer les \(n\), ta combinaison linéaire donnera directement \(1\). C'est une excellente nouvelle ! D'après le théorème de Bézout, cela signifie que tes deux expressions sont premières entre elles pour tout \(n\). Le PGCD sera donc toujours égal à \(1\), sans avoir besoin de tester les congruences.

Les combinaisons évidentes (Exercices 3 et 4) : Il n'est pas toujours nécessaire de croiser les coefficients en multipliant les deux expressions. Si tu cherches le PGCD de \(3n+7\) et \(n\), il suffit de soustraire \(3\) fois la deuxième expression à la première pour trouver \(7\). Reste simple avant d'être calculatoire.

La présence de puissances (Exercice 6) : C'est le grand classique des Maths expertes. Si on te demande le PGCD de \(n^2+2n+3\) et de \(n+1\), une simple combinaison linéaire linéaire ne suffira pas. La ruse consiste à utiliser la division euclidienne (ou l'algorithme d'Euclide). Tu devras remarquer que \(n^2+2n+3\) s'écrit \((n+1)^2 + 2\). Le PGCD de \(a\) et \(b\) étant égal au PGCD de \(b\) et du reste \(r\), tu te ramèneras instantanément au PGCD de \(n+1\) et de \(2\). Un gain de temps immense !

Prends un brouillon, applique ces méthodes sur les exercices ci-dessous et valide tes réponses pas à pas !