Algèbre et démonstrations : six exercices originaux

Choisir une méthode

• L’énoncé porte sur tous les entiers n à partir d’une valeur donnée : envisagez une récurrence. Vérifiez d’abord si une preuve directe serait plus simple.
• Vous cherchez $\operatorname{pgcd}(a,b)$, ou des entiers u et v tels que $au+bv=\operatorname{pgcd}(a,b)$ : utilisez l’algorithme d’Euclide, puis remontez les égalités.
• Vous cherchez toutes les solutions entières de $ax+by=c$ : vérifiez d’abord la condition de divisibilité liée au pgcd.
• Vous cherchez un reste ou les solutions d’une congruence : réduisez modulo m et vérifiez l’inversibilité avant de diviser.
• Vous calculez un quotient de complexes : multipliez par le conjugué du dénominateur. Pour les puissances et les racines, la forme trigonométrique est souvent plus pratique.

Les entiers appartiennent à $\mathbb{Z}$. La notation $a \mid b$ signifie que $b=ak$ pour un entier k. Les modules utilisés dans les congruences sont des entiers strictement supérieurs à 1.

1 Démontrer par récurrence

Pour démontrer $P(n)$ pour tout entier $n\ge n_{0}$, établissez $P(n_{0})$, puis montrez que $P(k)$ implique $P(k+1)$ pour un entier $k\ge n_{0}$ arbitraire. L’hypothèse de récurrence sert uniquement à établir cette implication; elle ne permet pas de supposer la conclusion vraie.

Pour une démonstration résolue complète, révisez la méthode de récurrence, puis vérifiez le premier rang et l’initialisation.

Vérifiez votre preuve. Avez-vous précisé le premier rang, formulé et utilisé l’hypothèse, puis obtenu l’expression attendue au rang $k+1$? Quelques vérifications numériques peuvent révéler une erreur, mais ne prouvent pas un énoncé portant sur une infinité d’entiers.

2 Plus grand commun diviseur et identité de Bézout

Pour deux entiers a et b non tous deux nuls, $\operatorname{pgcd}(a,b)$ est leur plus grand diviseur commun positif. L’identité de Bézout affirme qu’il existe des entiers $u,v$ tels que $au+bv=\operatorname{pgcd}(a,b)$.

L’algorithme d’Euclide repose sur la propriété suivante : si $a=qb+r$, alors $\operatorname{pgcd}(a,b)=\operatorname{pgcd}(b,r)$. En effet, tout diviseur de a et b divise $r=a-qb$; réciproquement, tout diviseur de b et r divise $a=qb+r$.

Exemple résolu

Calculons $\operatorname{pgcd}(252,198)$ et trouvons une identité de Bézout :

Le dernier reste non nul est 18. Remontons les égalités :

Ainsi, $\operatorname{pgcd}(252,198)=18$, avec $u=4$ et $v=-5$. Vérification numérique : $1008-990=18$.

3 Équations diophantiennes linéaires

Résoudre une équation diophantienne linéaire $ax+by=c$ consiste à chercher des solutions entières $x,y$. Pour $a,b$ entiers strictement positifs et $d=\operatorname{pgcd}(a,b)$, il existe des solutions si et seulement si $d \mid c$.

Nécessité. Puisque d divise a et b, il divise toute combinaison entière $ax+by$ et doit donc diviser c.

Suffisance. Si $d \mid c$, multipliez une identité de Bézout $au+bv=d$ par l’entier $c/d$ pour obtenir une solution.

À partir d’une solution $(x_{0},y_{0})$, toutes les solutions sont

Pour justifier que cette liste est complète, soustrayez les équations de deux solutions, puis divisez par d. Les coefficients obtenus étant premiers entre eux, $b/d$ divise $x-x_{0}$. La substitution impose alors la variation indiquée pour y.

Exemple résolu

Résolvons $14x+21y=35$. Le pgcd vaut 7 et divise 35. Après division par 7, l’équation devient $2x+3y=5$. Une solution est $(1,1)$, donc toutes les solutions sont

La substitution donne $2(1+3t)+3(1-2t)=5$. Si l’on impose aussi $x\ge 0$ et $y\ge 0$, les contraintes $t\ge -1/3$ et $t\le 1/2$ ne permettent que $t=0$. La seule solution à coordonnées non négatives est donc $(1,1)$.

4 Congruences et simplifications autorisées

La relation $a\equiv b \pmod{m}$ signifie que $m \mid (a-b)$. Les congruences sont compatibles avec l’addition et la multiplication. La division exige une précaution : a possède un inverse multiplicatif modulo m si et seulement si $\operatorname{pgcd}(a,m)=1$.

Plus généralement, $ax\equiv b \pmod{m}$ admet une solution si et seulement si $\operatorname{pgcd}(a,m)$ divise b. Si $d=\operatorname{pgcd}(a,m)$ divise b et $d=m$, tout entier x est une solution. Si d divise b et $d<m$, divisez a, b et m par d pour obtenir une congruence équivalente modulo $m/d>1$. Conserver le module initial après cette simplification peut faire perdre des solutions.

Exemple résolu

Résolvons $7x\equiv 5 \pmod{12}$. Comme $7\times 7=49\equiv 1 \pmod{12}$, multiplions par 7 :

Vérification : $7\times 11-5=72$ est un multiple de 12. Toutes les solutions entières sont $x=11+12t$, $t\in \mathbb{Z}$.

Attention à la simplification. La congruence $2x\equiv 2 \pmod{6}$ se réduit correctement en $x\equiv 1 \pmod{3}$. Modulo 6, elle possède deux classes de solutions, représentées par 1 et 4. Écrire uniquement $x\equiv 1 \pmod{6}$ fait perdre une solution.

5 Calcul complexe et racines

Un nombre complexe s’écrit $z=a+bi$, avec $a,b$ réels et $i^{2}=-1$. Son conjugué est $\overline{z}=a-bi$ et son module est $\lvert z\rvert=\sqrt{a^2+b^2}$. Ainsi, $z\overline{z}=\lvert z\rvert^2$.

Pour les puissances et les racines, révisez les formes algébrique et trigonométrique, la formule de Moivre et la recherche de toutes les racines. Utilisez ces méthodes dans l’exercice 6 ci-dessous.

Exemple résolu

Simplifions $(2-i)/(1+i)$. Multiplions le numérateur et le dénominateur par $1-i$ :

Pour vérifier, multipliez le résultat par $1+i$ : vous retrouvez $2-i$. Pour un calcul de racines, vérifiez également leur nombre, leur caractère distinct et leur module.

Six exercices originaux

Essayez de les résoudre avant de lire les corrigés. Le barème proposé sert à l’autoévaluation; ce n’est pas un barème officiel de Waterloo.

Pour aller plus loin : MATH135 de Waterloo, automne 2009

Ces évaluations de Waterloo datent de l’automne 2009. Choisissez des questions sur les notions de votre cours actuel.

Liens directs utiles :

• Premier test : question 2 pour la récurrence; question 5(a) pour l’algorithme d’Euclide et une identité de Bézout. Corrigé officiel.
• Examen final : question 2(b) pour les équations en nombres entiers; question 3(b) pour les systèmes de congruences; question 7 pour les nombres complexes. Corrigé officiel.

Essayez une question avant d’ouvrir son corrigé. Comparez les raisonnements, puis reprenez toute étape que vous ne pouviez pas justifier seul.

Choisir la prochaine étape

Partez d’une notion ou de l’un de ces exercices. Si vous avez une tentative de solution, vous pouvez l’utiliser pour montrer ce qui vous bloque. Obtenir de l’aide en démonstrations et en mathématiques discrètes.