Bézout, PGCD, PPCM

  1. Les exercices
  2. Vue compacte

Exercices du dossier Bézout, PGCD, PPCM

Exercice 1465 *

18 novembre 2022 14:49 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Calculer le pgcd des couples

  1. \(\left(120,230\right)\)

  2. \(\left(210,135\right)\)

  3. \(\left(211,112\right)\)


[ID: 3173] [Date de publication: 18 novembre 2022 14:49] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1465
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:50

On applique l’algorithme d’Euclide et on trouve :

  1. \(120\wedge230=10\)

  2. \(210\wedge135=15\)

  3. \(211\wedge112=1\)


Exercice 1466 *

18 novembre 2022 14:50 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Soient \(a,b\) des nombres premiers entre eux. Montrer que :

  1. \(a\wedge \left(a+b\right)=b\wedge \left(a+b\right)=1\).

  2. \(\left(a+b\right)\wedge ab=1\).


[ID: 3175] [Date de publication: 18 novembre 2022 14:50] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1466
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:50

  1. On suppose que \(a\) et \(a+b\) ne sont pas premiers entre eux. Alors soit \(k\) un diviseur commun à \(a\) et \(a+b\) différent de \(1\). Comme \(k\mid a\) et que \(k\mid a+b\), \(k \mid b\) et donc \(k\mid a\wedge b=1\) ce qui n’est pas possible. Donc \(a\wedge \left(a+b\right)=1\). La seconde relation se prouve en échangeant les lettres \(a\) et \(b\) dans la première.

  2. Comme avant, on suppose que \(ab\) et \(a+b\) ne sont pas premiers entre eux. Alors soit \(k\) un diviseur premier commun à \(ab\) et \(a+b\) différent de \(1\). Comme \(k\mid ab\), \(k\mid a\) ou \(k\mid b\). On suppose que \(k\mid a\), alors comme avant, comme \(k\mid a+b\), \(k\mid b\) et donc \(k\mid a\wedge b=1\) ce qui n’est pas possible.


Exercice 1467 *

18 novembre 2022 14:50 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Trouver tous les couples d’entiers naturels \(\left(a,b\right)\in\mathbb{N}^2\) (\(a\leqslant b\)) tels que \(a\wedge b=18\) et \(a+b=360\).


[ID: 3177] [Date de publication: 18 novembre 2022 14:50] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1467
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:50

Soit \(\left(a,b\right)\in\mathbb{N}^2\) un couple solution du problème. Alors il existe \(\left(a',b'\right)\in \mathbb{N}^2\) tel que \(a=18a'\), \(b=18b'\) et \(a'\wedge b'=1\). De plus comme \(a+b=360\), on sait que \(a'+b'=360/18=20\). En résumé, \(\left(a',b'\right)\) est un couple de deux entiers premiers entre eux et de somme \(20\). Les seuls couples à vérifier cette propriété sont \[\left(1,19\right),\left(3,17\right)\left(7,13\right),\left(9,11\right).\] On multiplie ces couples par \(18\) pour retrouver le couple \(\left(a,b\right)\) : \[\left(18,342\right),\left(54,306\right),\left(126,234\right),\left(162,198\right) .\] Réciproquement, chacun de ces couples vérifie les deux conditions.


Exercice 1468 *

18 novembre 2022 14:50 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Trouver tous les couples d’entiers naturels \(\left(a,b\right)\in\mathbb{N}^2\) (\(a\leqslant b\)) tels que \(a\wedge b=18\) et \(ab=126\).


[ID: 3179] [Date de publication: 18 novembre 2022 14:50] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1468
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:50

Soient \(\left(a,b\right)\in\mathbb{N}^2\) un couple solution du problème. Alors il existe \(\left(a',b'\right)\in \mathbb{N}^2\) tel que \(a=18a'\), \(b=18b'\) et \(a'\wedge b'=1\). Comme \(ab=126\), on sait que \(a'b'=7\). Les seuls couples à vérifier cette propriété sont \(\left(1,6\right),\left(2,5\right),\left(3,4\right)\). On multiplie par \(18\) pour retrouver les couples \(\left(a,b\right)\) : \(\left(18,108\right),\left(36,90\right)\),\(\left(54,72\right)\). Réciproquement, chacun de ces couples vérifie les deux conditions.


Une équation diophantienne **

18 novembre 2022 14:50 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Résoudre dans \(\mathbb{Z}\) l’équation \(1665x+1035y=45\).


[ID: 3181] [Date de publication: 18 novembre 2022 14:50] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Une équation diophantienne
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:50

Comme \(1665\wedge 1035=45\) cette équation est équivalente à \(37x+23y=1\). Comme \(37\) et \(23\) sont premiers entre eux cette équation admet des solutions par le théorème de Bézout. Une d’entre elles est par exemple donnée par \(x=5\) et \(y=-8\). Les autres s’en déduisent, elles sont de la forme \(\left(5-23k,-8+37k\right)\). En effet, elles sont de la forme \(\left(5+a,-8+b\right)\) avec \(\left(a,b\right)\in\mathbb{Z}^2\). On injecte dans \(37x+23y=1\) et il vient que \(37a+23b=0\). Comme \(23\) et \(37\) sont premiers, on en déduit que \(23\mid a\) et \(37\mid b\). Donc il existe \(k,k'\in \mathbb{Z}\) tels que \(a=23k\) et \(b=37k'\). On injecte dans l’égalité \(37a+23b=0\) et on trouve que \(k=-k'\) d’où la forme des solutions. Réciproquement, toute couple de cette forme est solution de l’équation.


Une seconde équation diophantienne **

18 novembre 2022 14:50 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

On se donne trois entiers non nuls \((A, B, C) \in {\mathbb{Z}^*}^3\), et on considère l’équation diophantienne : \[(E)~:~ Ax + By = C\quad(x, y) \in \mathbb{Z}^{2}\] Résoudre cette équation consiste à déterminer l’ensemble des solutions \(\mathcal{S} = \{(x, y) \in \mathbb{Z}^{2} \mid Ax + By = C\}\).

  1. Notons \(\delta = A \wedge B\). Montrer que si \(\delta\) ne divise pas \(C\), alors \(\mathcal{S} = \varnothing\) ;

  2. On suppose désormais que \(\delta | C\). Il existe trois entiers non nuls \((A', B', C') \in {\mathbb{Z}^*}^3\) tels que \(A = \delta A'\), \(B = \delta B'\) avec \(A' \wedge B' = 1\), et \(C = \delta C'\). Montrer que l’équation \((E)\) a même ensemble de solutions que l’équation \[(E')~:~ A'x + B'y = C'\]

  3. Comment trouver une solution particulière de l’équation \((E')\) ?

  4. En déduire l’ensemble \(\mathcal{S}\) de toutes les solutions ;

  5. Résoudre dans \(\mathbb{Z}\) l’équation \[(E)~:~ 24 x + 20 y = 36\]


[ID: 3183] [Date de publication: 18 novembre 2022 14:50] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Une seconde équation diophantienne
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:50

  1. Par contraposée, si \(\mathcal{S} \neq \varnothing\) alors il existe \(\left(x,y\right)\in\mathbb{Z}^2\) tel que \(Ax+By=C\). Comme \(\delta\mid A\) et \(\delta\mid B\), \(\delta \mid C\).

  2. Soit \(\left(x,y\right)\) une solution de \(\left(E\right)\). Alors \(Ax+By=C\). Comme \(A,B,C\) sont divisibles par \(\delta\), on peut écrire \(A'x+B'y=C'\) et \(\left(x,y\right)\) est solution de \(\left(E'\right)\). Réciproquement, si \(\left(x,y\right)\) est solution de \(\left(E'\right)\) alors \(A'x+B'y=C'\) et en multipliant par \(\delta\), on obtient \(Ax+By=C\) et \(\left(x,y\right)\) est solution de \(\left(E\right)\).

  3. Comme \(A'\) et \(B'\) sont premiers entre eux, on peut déterminer un couple \(\left(u,v\right)\) de coefficients de Bézout tels que \(A'u+B'v=1\). Alors \(\left(C'u,C'v\right)\) est une solution de \(\left(E'\right)\).

  4. On considère une solution particulière \(\left(u,v\right)\) de \(\left(E'\right)\). On cherche une autre solution de \(\left(E'\right)\). On peut l’écrire \(\left(u+a,v+b\right)\) où \(a,b\in\mathbb{Z}\). On doit alors avoir \(A'\left(u+a\right)+B'\left(u+v\right)=C'\) soit \(A'a+B'b=0\). Comme \(A'\wedge B'=1\), on en déduit, grâce au théorème de Gauss, que \(a\) est un multiple de \(B'\) et que \(b\) est un multiple de \(A'\) : \(a=kB'\) et \(b=lA'\). On injecte dans \(A'a+B'b=0\) et on trouve que \(l=-k\). Donc une solution de \(\left(E'\right)\) est de la forme \(\left(u+kB',v-kA'\right)\) où \(k\in\mathbb{Z}\). Réciproquement, on vérifie facilement que tout couple de cette forme est solution de \(\left(E'\right)\). Finalement \(\boxed{\mathscr S= \left\{\left(u+kB',v-kA'\right)|k\in\mathbb{Z}\right\}}\).

  5. On applique les questions précédentes. Les solutions de \(\left(E\right)\) sont celles de \(\left(E'\right)~:~6x+5y=9\). Un couple de coefficients de Bézout pour \(6\) et \(5\) est \(\left(1,-1\right)\). Donc une solution particulière de \(\left(E'\right)\) est \(\left(9,-9\right)\) Les solutions de \(\left(E\right)\) sont les couples \(\boxed{\left(9+5k,-9-6k\right)}\) où \(\left(k,l\right)\in\mathbb{Z}^2\).


Exercice 1471 **

18 novembre 2022 14:50 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Soient \(H_1\) et \(H_2\) deux sous-groupes du groupe \((\mathbb{Z} , +)\). On définit l’ensemble \[H_1 + H_2 = \{h_1 + h_2~|~(h_1, h_2) \in H_1 \times H_2 \}\]

  1. Montrer que \(H_1 + H_2\) est le plus petit (au sens de l’inclusion) sous-groupe de \((\mathbb{Z} , +)\) qui contient la partie \(H_1 \cup H_2\) ;

  2. Déterminer le sous-groupe \(4\mathbb{Z} + 6\mathbb{Z}\) ;

  3. Comment interpréter l’inclusion \(a\mathbb{Z} \cup b\mathbb{Z} \subset c \mathbb{Z}\) en termes de divisibilité ?


[ID: 3185] [Date de publication: 18 novembre 2022 14:50] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1471
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:50

  1. On vérifie facilement que \(H_1+H_2\) est un sous-groupe de \(\left(\mathbb{Z},+\right)\). Il contient de plus clairement \(H_1\) et \(H_2\) et donc \(H_1 \cup H_2\). Montrons que c’est le plus petit sous-groupe de \(\left(\mathbb{Z},+\right)\) à vérifier cette propriété. Soit \(H'\) un sous-groupe de \(\left(\mathbb{Z},+\right)\) qui contient \(H_1 \cup H_2\). Alors \(H'\) doit contenir toutes les sommes \(h_1 + h_2\) avec \(h_1\in H_1\) et \(h_2\in H_2\). Donc \(H\subset H'\).

  2. Déterminons le sous-groupe \(H=4\mathbb{Z} + 6\mathbb{Z}\). Ces élements sont de la forme \(4a+6b\) avec \(a,b\in\mathbb{Z}\). Comme \(4\wedge 6=2\), d’après le théorème de Bézout, il existe \(u,v\in\mathbb{Z}\) tels que \(4u+6v=2\) donc pour tout \(k\in\mathbb{Z}\), \(4uk+6vk=2k\) et \(H\) contient tous les entiers pairs. Réciproquement, tout élément de \(H\) est pair donc \(\boxed{4\mathbb{Z} + 6\mathbb{Z} =2\mathbb{Z}}\).

  3. En suivant le même raisonnement que précédemment, on pourrait montrer que \(a\mathbb{Z}+b\mathbb{Z}=\left(a\wedge b\right)\mathbb{Z}\) donc \(a\mathbb{Z} \cup b\mathbb{Z} \subset c \mathbb{Z}\) si et seulement si \(c\mid a\wedge b\).


Exercice 1472 **

18 novembre 2022 14:50 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Soient deux entiers non nuls \((n, m) \in \left(\mathbb{N}^*\right)^2\). On suppose que \(\sqrt[n]{m} \in \mathbb{Q}\). Montrez qu’alors \(\sqrt[n]{m} \in \mathbb{N}^*\).


[ID: 3187] [Date de publication: 18 novembre 2022 14:50] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1472
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:50

Comme \(\sqrt[n]{m} \in \mathbb{Q}\), il existe deux entiers \((p, q) \in \left(\mathbb{N}^*\right)^2\) tels que \(\sqrt[n]{m} = p / q\) avec \(p \wedge q = 1\). Alors, \(p^n = m q^n\). Mais puisque \(p\) et \(q\) sont premiers entre eux, on sait que \(p^n\) et \(q^n\) sont également premiers entre eux. Puisque \(p^n | mq^n\) avec \(p^n \wedge q^n = 1\), d’après le théorème de Gauss, il vient que \(p^n\) divise \(m\). Donc il existe \(k \in \mathbb{N}^*\) tel que \(m = k p^n\). Mais alors on a \(k = \dfrac{1}{q^n}\) et donc \(q^n = 1\). Par conséquent, \(m = p^n\) et donc \(\sqrt[n]{m} = p\).


Exercice 1473 **

18 novembre 2022 14:50 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Soient deux entiers non nuls \((a, b) \in {\mathbb{Z}^2}\). On note \(\delta = a\wedge b\) leur pgcd et \(\mu = a \vee b\) leur ppcm. Montrez que \[(a + b) \wedge \mu = \delta.\]


[ID: 3189] [Date de publication: 18 novembre 2022 14:50] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1473
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:50

On sait qu’il existe \((a', b') \in \left(\mathbb{Z}^{*}\right)^2\) tels que \(a = \delta a'\), \(b = \delta b'\) et \(a'\wedge b' = 1\). On a de plus \(\delta \mu = ab\) donc \(\mu = \delta a' b'\). Par conséquent, \[(a+b)\wedge \mu = \bigl(\delta(a'+b')\bigr) \wedge (\delta a'b') = \delta \times \bigl((a'+b') \wedge a'b'.\] Mais puisque \(a'\) et \(b'\) sont premiers entre eux, on a également \(a' \wedge (a' + b') = 1\) et \(b' \wedge (a' + b') = 1\) (il suffit d’écrire une relation de Bézout). Donc puisque \(a'\wedge b' = 1\), \(a'b' \wedge (a' + b') = 1\). Finalement, \((a+b)\wedge \mu = \delta\).


Exercice 1474 *

18 novembre 2022 14:50 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Trouver les couples d’entiers \((x, y) \in {\mathbb{N}^*}^2\) vérifiant \[11 x - 5y = 10 \textrm{ et } x \wedge y = 10.\]


[ID: 3191] [Date de publication: 18 novembre 2022 14:50] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1474
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:50

Supposons que \((x, y)\) soit un couple d’entier satisfaisant les hypothèses. Comme \(x \wedge y = 10\), on peut écrire \(x = 10x'\) et \(y=10y'\) avec \(x'\wedge y' = 1\). Alors le couple d’entiers \((x',y')\) vérifie \[11x' - 5y' = 1\] Un couple de Bézout évident est \((x', y') = (1, 2)\). On trouve alors (voir l’exercice [exo_equ_diophantienne]) qu’il existe un entier \(k \in \mathbb{Z}\) tel que \[x' = 1 + 5k \textrm{ et } y' = 2 + 11k\] d’où nécessairement \[x = 10 + 50k \textrm{ et } y = 20 + 100k\] On vérifie réciproquement que tout couple de cette forme convient.


Exercice 1475 *

18 novembre 2022 14:50 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Considérons deux entiers \((a, b) \in \left(\mathbb{Z}^*\right)^2\) premiers entre eux \(a \wedge b = 1\) et un couple de Bézout \((u_0, v_0) \in \mathbb{Z}^{2}\) tel que \(au_0 + bv_0 = 1\). Déterminer l’ensemble de tous les couples de Bézout \((u, v) \in \mathbb{Z}^{2}\) vérifiant \(au + bv = 1\).


[ID: 3193] [Date de publication: 18 novembre 2022 14:50] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1475
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:50

Soit \(\left(u,v\right)\) un couple d’entiers vérifiant la relation \(au+bv=1\). Par soustraction on a \(a(u-u_0) = b(v_0-v)\). Donc \(b\) divise \(a(u-u_0)\). Puisque \(a\) et \(b\) sont premiers entre eux, d’après le lemme de Gauss, \(b\) divise nécessairement \(u-u_0\), donc il existe \(k\in\mathbb Z, u-u_0 = kb\) ou \(u = u_0 + kb\). En remplaçant \(u-u_0\) par \(kb\), on obtient alors \(akb = b(v_0-v)\), d’où \(v = v_0 - ka\).
Réciproquement, les couples \((u_0 + kb, v_0 -ka),k\in\mathbb Z\) sont bien solutions.


Exercice 1476 **

18 novembre 2022 14:50 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Soient deux entiers non nuls \((a, b) \in \left(\mathbb{Z}^*\right)^2\) premiers entre eux. Montrez qu’il existe deux entiers \((u, v) \in \mathbb{Z}^{2}\) tels que \[au + bv = 1 \textrm{ et } \lvert u \rvert < \lvert b \rvert ,~ \lvert v \rvert \leqslant\lvert a \rvert .\]


[ID: 3195] [Date de publication: 18 novembre 2022 14:50] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1476
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:50

Le résultat est faux dans le cas (sans intérêt) où \(a\) et \(b\) sont égaux à \(\pm1\). Dans les autres cas, quitte à changer \(a\) et/ou \(b\) en leurs opposés, on peut toujours supposer \(a\) et \(b\) positifs. Il suffit pour cela de changer le/les signe/s de \(u\) ou \(v\) selon les cas.

On écrit une relation de Bézout \(au_0 + bv_0 = 1\). Reste à avoir \(-b<u<b\) et \(-a<v<a\) en posant \(u = u_0 +kb\) et \(v = v_0 -ka\) (voir l’exercice précédent). On a bien \(au + bv = 1\). Pour avoir \(\vert u \vert < b\), il suffit de prendre \(-b < v < b\) soit \(-1 -\dfrac{u_0}{b} < k < 1 -\dfrac{u_0}{b}\). On choisit \(k\) entier dans un intervalle ouvert de longueur \(2\). On a deux possibilités, sauf lorsque \(\dfrac{u_0}{b}\) est entier (pour \(b=\pm1\)), auquel cas on peut (et on doit) choisir \(k = -\dfrac{u_0}{b}\) et donc \(u=0\) et par suite \(bv = 1\) entraîne bien \(v= \pm1\) et donc \(\lvert v \rvert \leqslant\lvert a \rvert\) puisque dans ce cas on n’a pas \(\lvert a \rvert = 1\).
Lorsque \(\dfrac{u_0}{b}\) n’est pas entier, on a donc deux possibilités pour \((u_1,v_1)\) et \((u_1+b,v_1-b)\) qui vérifient \(\vert u \vert < b\).
Comme \(au + bv = 1\), on a \(0\leqslant au + bv = 1 < ab\). Donc \(ab < -au \leqslant bv < ab -au < ab + ab\) et \(-a < v < 2a\). Deux cas se présentent. Si \(-a < u < a\), alors c’est gagné. Sinon c’est qu’on s’est trompé dans le choix de \(a_1\) et on considère cette fois \(v-a\) qui vérifie \(0\leqslant v-a < a\) et c’est encore gagné.


Exercice 1477

18 novembre 2022 14:50 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Soient \(n\) entiers \((m_1,\dots, m_n) \in {\mathbb{N}^*}^n\) premiers deux à deux entre eux. On pose \(M = m_1\dots m_n\) et \(\forall i \in [1, n ]\), \(M_i = \dfrac{M}{m_i}\).

  1. Montrer que \(\forall i \in [1, n]\), \(m_i \wedge M_i = 1\) et en déduire qu’il existe \(u_i \in \mathbb{Z}\) tel que \(M_i\mu_i \equiv 1 \; [ m_i ]\).

  2. Soient \(n\) entiers \((a_1,\dots, a_n) \in \mathbb{Z}{n}\). On pose \[x = \sum_{j=1}^n a_j M_j \mu_j\] Montrer que \[\begin{cases} x \equiv a_1 \; [ m_1 ] \\ \vdots \\ x \equiv a_n \; [ m_n ] \end{cases}\]

  3. Application : Trouver un entier \(x \in \mathbb N\) tel que \[\begin{cases} x \equiv 3 \; [ 5 ] \\ x \equiv 1 \; [ 6 ] \\ x \equiv 2 \; [ 7 ] \end{cases}\]


[ID: 3197] [Date de publication: 18 novembre 2022 14:50] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1477
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:50

  1. Soit \(i \in [1, n]\). Comme \(\forall j \in [1, n] \setminus \{j\}\), \(m_i \wedge m_j = 1\), \(m_i\) est premier avec le produit \(\prod_{j\neq i} m_j = M_i\). Dans l’anneau \(\mathbb{Z} / m_i \mathbb{Z}\), la classe \(\widehat{M_i}\) est donc inversible. Il existe donc \(\widehat{\tild{ M_i}} \in \mathbb{Z} / m_i \mathbb{Z}\) tel que \(\widehat{M_i}\times \widehat{\tild{M_i}} = \widehat{1}\). En considérant le représentant \(\mu_i\) de la classe \(\widehat{\tild{M_i}}\) dans \([0, m_i - 1]\), on a bien \(\mu_iM_i \equiv 1 \; [ m_i ]\).

  2. Soit \(i \in [1, n]\). Dans l’anneau \(\mathbb{Z} / n \mathbb{Z}\), on a \[\widehat{x} = \sum_{j \neq i} \widehat{a_j}\widehat{M_j} \widehat{\mu_j} + \widehat{a_i}\widehat{\mu_i}\widehat{M_i} = \sum_{j\neq i} \widehat{a_j}\widehat{M_j}\widehat{\mu_j} + \widehat{a_i} = \widehat{a_i}\] En effet, pour \(j\neq i\), \(m_i\) divise \(M_j\) et donc \(\widehat{M_j} = \widehat{0}\). Par conséquent, \(x \equiv a_i \; [ m_i ]\).

  3. On a ici \(m_1 = 5\), \(m_2 = 6\) et \(m_3 = 7\) qui sont premiers deux à deux entre eux. Avec les notations précédentes, on a ici \(M_1 = 42\), \(M_2 = 35\) et \(M_3 = 30\). Dans \(\mathbb{Z} / 5 \mathbb{Z}\), \(\widehat{42} = \widehat{2}\) et on peut prendre par exemple \(\mu_1 = 3\). Dans \(\mathbb{Z} / 6 \mathbb{Z}\), \(\widehat{35} = \widehat{-1}\) et on peut prendre \(\mu_{2} = -1\). Dans \(\mathbb{Z} / 7 \mathbb{Z}\), \(\widehat{30} = \widehat{2}\) et on peut prendre \(\mu_3 = -3\). Alors on trouve une solution (pas forcément le plus petit entier) au système de congruences : \[x = 3\times 42 \times 3 - 1 \times 35 - 3\times 2 \times 30 = 163\]


Exercice 1478

18 novembre 2022 14:50 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Soit un nombre premier \(p \in \mathcal{P}\). Montrer que \[(p-1)! \equiv -1 \; [ p ]\]


[ID: 3199] [Date de publication: 18 novembre 2022 14:50] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1478
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:50

Raisonnons dans l’anneau \((\mathbb{Z} / p \mathbb{Z} , +, \times)\) et calculons la classe de \((p-1)! = (p-1) \times (p-2) \times \cdots \times 1\). Comme \(p\) est un nombre premier, l’ensemble des éléments inversibles de \(\mathbb{Z} / p \mathbb{Z}\) est \(U_p = \mathbb{Z} / p \mathbb{Z} \setminus \{0\}\). La classe de \((p-1)!\) est donc le produit de tous les éléments du groupe \(U_p\). Écrivons \(U_p = S \cup P\) où \(P\) est l’ensemble des éléments qui sont leur propre symétrique (pour la multiplication) et \(S\) est l’ensemble des éléments qui ne sont pas leur propre symétrique. En groupant les éléments de \(S\) deux par deux, leur produit donne \(1\). Donc \[(p-1)! = \prod_{u \in P} u\] Cherchons donc les éléments de \(U_p\) qui sont leur propre symétrique. Soit \(u \in P\), on doit avoir \(u^2 = 1\) donc \((u-1)(u+1) = 0\). Or comme \(\mathbb{Z} / p \mathbb{Z}\) est un corps, on doit avoir \(u = 1\) ou \(u = -1\). Par conséquent, \[(p-1)! = 1 \times (-1) = -1\] et donc \((p-1)! \equiv -1 \; [ p ]\).


Exercice 1479

18 novembre 2022 14:50 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Soit un entier \(n\) dont la décomposition en facteurs premiers s’écrit \(n = p_1^{\alpha_1}\dots p_k^{\alpha_k}\). Déterminer l’ensemble des éléments nilpotents de l’anneau \((\mathbb{Z} / n \mathbb{Z} , +, \times)\).


[ID: 3201] [Date de publication: 18 novembre 2022 14:50] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1479
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:50

Soit \(A \in \mathbb{Z} / n \mathbb{Z}\) un élément nilpotent, et un représentant \(a \in \mathbb{Z}\) de la classe de \(A\). Comme \(A\) est nilpotent, il existe \(p \in \mathbb{N}^*\) tel que \(A^p = 0\) dans \(\mathbb{Z} / n \mathbb{Z}\). Donc \(n\) divise \(a^p\). Comme \(n = p_1^{\alpha_1}\dots p_k^{\alpha_k}\), nécessairement, \(p_1\dots p_k\) divise \(a^p\). En décomposant l’entier \(a\) en facteurs premiers, on voit que nécessairement, chaque nombre premier \(p_1,\dots, p_k\) apparaît dans la décomposition de \(a\). Donc nécessairement, \(p_1\dots p_k\) doit diviser \(a\). Réciproquement, si \(p_1\dots p_k\) divise \(a\), il existe \(k \in \mathbb{Z}\) tel que \(a = k p_1\dots p_k\). Mais alors, en posant \(p = \mathop{\mathrm{ppcm}}(\alpha_1, \dots, \alpha_k)\), on voit que \(n\) divise \(a^p\) et donc \(\widehat{a}\) est nilpotent dans \(\mathbb{Z} / n \mathbb{Z}\). En définitive, les éléments nilpotents de l’anneau \(\mathbb{Z} / n \mathbb{Z}\) sont les classes des entiers multiples de \(p_1\dots p_k\).


Exercice 1480

18 novembre 2022 14:51 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

On dit qu’une fraction \(m/n\) est basique si \(0< m < n\). Considérons les fractions basiques de dénominateur \(12\) : \[{\scriptstyle 0\over\scriptstyle 12}, {\scriptstyle 1\over\scriptstyle 12}, {\scriptstyle 2\over\scriptstyle 12}, {\scriptstyle 3\over\scriptstyle 12}, {\scriptstyle 4\over\scriptstyle 12}, {\scriptstyle 5\over\scriptstyle 12},{\scriptstyle 6\over\scriptstyle 12},{\scriptstyle 7\over\scriptstyle 12},{\scriptstyle 8\over\scriptstyle 12},{\scriptstyle 9\over\scriptstyle 12}, {\scriptstyle 10\over\scriptstyle 12}, {\scriptstyle 11\over\scriptstyle 12}\] Après réduction, et en groupant ces fractions selon leurs dénominateurs, on obtient \[{\scriptstyle 0\over\scriptstyle 12}~;~{\scriptstyle 1\over\scriptstyle 2}~;~{\scriptstyle 1\over\scriptstyle 3},{\scriptstyle 2\over\scriptstyle 3}~;~{\scriptstyle 1\over\scriptstyle 4}, {\scriptstyle 3\over\scriptstyle 4}~;~{\scriptstyle 1\over\scriptstyle 6},{\scriptstyle 5\over\scriptstyle 6}~;~{\scriptstyle 1\over\scriptstyle 12},{\scriptstyle 5\over\scriptstyle 12}, {\scriptstyle 7\over\scriptstyle 12},{\scriptstyle 11\over\scriptstyle 12}\] En s’inspirant de cette idée, montrer que pour tout entier \(m \geqslant 2\), \[\sum_{d / m} \varphi(d) = m\] où \(\varphi\) est l’indicateur d’Euler vu en TD.


[ID: 3203] [Date de publication: 18 novembre 2022 14:51] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1480
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:51

Exercice 1481

18 novembre 2022 14:51 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Trouver le plus petit entier \(n \in \mathbb{N}^{\star}\) tel que le nombre \((\underbrace{1\dots 1}_{n \times } )_{10}\) soit divisible par \(49\).


[ID: 3205] [Date de publication: 18 novembre 2022 14:51] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1481
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:51

Le nombre s’écrit \[1 + 10 + \cdots + 10^{n-1} = \dfrac{10^n - 1}{9}\] Supposons qu’il soit divisible par \(49 = 7^2\). Il existe \(k \in \mathbb N\) tel que \(10^n = 1 + 3^2\times 7^2 \times k\), et nécessairement, on doit avoir \(10^n \equiv 1 \; [ 7 ]\). En examinant les puissances de \(10\) dans \(\mathbb{Z} / 7 \mathbb{Z}\), on voit qu’il est nécessaire que \(n = 6p\). Alors \(10^{6p} = (10^2)^{3p} = 2^{3p} = 8^{p}\) dans \(\mathbb{Z} / 49 \mathbb{Z}\). Mais en examinant les puissances de \(8\) dans \(\mathbb{Z} / 49 \mathbb{Z}\), on voit qu’il est nécessaire que \(p = 7l\) et donc nécessairement, \(n = 42 j\). Réciproquement, si \(n = 42j\), \(10^n - 1\) est divisible par \(7^2\) et par \(3^2\), et donc par \(9 \times 49\) puisque \(7^2\) et \(3^2\) sont premiers entre eux. Il vient donc que \((10^{n} - 1) / 9\) est divisible par \(49\). Le plus petit entier \(n\) vaut donc \(42\).


Exercice 1482 **

18 novembre 2022 14:51 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Soit un entier \(n \in \mathbb{N}^{*}\). Montrer qu’il existe \((a_n,~b_n) \in \mathbb{Z}^{2}\) tels que \((1 + \sqrt{2})^n = a_n + \sqrt{2}b_n\). Montrer ensuite que les entiers \(a_n\) et \(b_n\) sont premiers entre eux.


[ID: 3207] [Date de publication: 18 novembre 2022 14:51] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1482
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:51

Par le binôme : \[(1+\sqrt{2})^n = \sum_{k=0}^n \dbinom{n}{k} \sqrt{2}^k = \sum_{p=0}^{E(n/2)} \dbinom{n}{2p} 2^p + \sqrt{2} \sum_{p=0}^{E((n-1)/2)} \dbinom{n}{2p+1} 2^p\] Il suffit de poser \[a_n = \sum_{p=0}^{E(n/2)} \dbinom{n}{2p}2^p\quad b_n = \sum_{p=0}^{E((n-1)/2)} \dbinom{2}{2p+1} 2^p\] De la même façon, on montre l’existence de \((c_n, d_n) \in \mathbb{Z}^2\) tels que \((\sqrt{2}-1)^n = c_n + \sqrt{d_n}\). En effectuant le produit, \[1 = (\sqrt{2} - 1)^n(\sqrt{2} + 1)^n = a_nc_n + 2b_nd_n + \sqrt{2}(b_nc_n + d_n a_n)\] Mais puisque dans le \(\mathbb{Q}\)-espace vectoriel \(\mathbb{R}\), le système \((1, \sqrt{2})\) est libre, il vient que \(b_nc_n + a_nd_n = 0\) et donc on obtient une relation de Bézout entre les entiers \(a_n\) et \(b_n\) : \[c_n a_n + 2d_nb_n = 1\] ce qui montre que les entiers \(a_n\) et \(b_n\) sont premiers entre eux.


Équation de Pythagore **

18 novembre 2022 14:51 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Le but de cet exercice est de déterminer l’ensemble \(E\) des triplets \((x, y, z) \in \left(\mathbb{N}^{*}\right)^3\) vérifiant l’équation de Pythagore : \[x^2 + y^2 = z^2.\]

  1. Montrer que pour tout couple \((a, b) \in \left(\mathbb{N}^{*}\right)^2\), le triplet \((a^2 - b^2, 2ab, a^2 + b^2)\) appartient à l’ensemble \(E\). Donner \(3\) éléments distincts de l’ensemble \(E\).

  2. On considère un triplet \((x, y, z) \in E\) vérifiant \(x \wedge y = 1\).

    1. Montrer qu’alors \(x\wedge z = 1\) et \(y \wedge z = 1\).

    2. Montrer que les entiers \(x\) et \(y\) ne sont pas de même parité.

    3. On suppose par exemple que \(x\) est impair et que \(y\) est pair. Montrer qu’il existe deux entiers non nuls \((p, q) \in {\mathbb{N}^*}^2\) premiers entre eux tels que \[x = p - q,~ y = p + q,~ y^2 = 4pq\] Montrer de plus que \(p\) et \(q\) sont des carrés parfaits.

  3. En déduire l’ensemble \(E\).


[ID: 3209] [Date de publication: 18 novembre 2022 14:51] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Équation de Pythagore
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:51

  1. Par un calcul simple.

    1. Supposons que \(x\) et \(z\) admettent un diviseur premier commun \(p\). Comme \(p|x\) et que \(p|z\), on a \(p|x^2\) et \(p|z^2\). Mais alors \(p|y^2\) ce qui amène \(p|y\) et alors \(x\wedge y\neq 1\). On montre de même que \(y \wedge z = 1\).

    2. Si \(x\) et \(y\) étaient pairs, \(2 | x\wedge y\), ce qui est impossible. Si on suppose \(x\) impair, et \(y\) impair, alors \(x^2+y^2 \equiv 2 \; [ 4 ]\), ce qui est impossible car \(z^2 \equiv 0 \; [ 4 ]\) (regarder la décomposition de \(z\) en facteurs premiers, et la puissance de \(2\)).

    3. Posons \(p = (z + x)/2\) et \(q = (z-x)/2\). Ce sont des entiers car \(z\) et \(x\) sont impairs. Ils sont positifs car \(z > x\). Comme \(x\wedge z = 1\), d’après Bézout, il existe \((u, v) \in \mathbb{Z}^2\) tels que \(ux + vz = 1\), mais alors \((u+v)p + (v-u)q = 1\) ce qui montre que \(p \wedge q = 1\). Alors \(4pq = z^2 - x^2 = y^2\).

      Comme \(p \wedge q = 1\), ils n’ont pas de facteurs premiers en commun dans leur décomposition. Comme \(pq = y^2/4\) est un carré, tous les exposants dans la décomposition de \(p\) et \(q\) sont pairs, ce qui montre que \(p\) et \(q\) sont des carrés.

  3. Soit \((x, y, z) \in E\). si \(x\wedge y \neq 1\), en posant \(\delta = x \wedge y\), on a \(\delta^2(x'^2 + y'^2) = z^2\) et donc \(\delta^2 / z^2\), par conséquent, il existe \(z'\in\mathbb N\) tel que \(z^2 = \delta^2 z'^2\) (comme \(z^2\) est un carré, \(z^2 / \delta^2\) en est encore un comme on le voit en examinant la décomposition en facteurs premiers). Alors \(x'^2 + y'^2 = z'^2\) avec \(x' \wedge y' = 1\). D’après la question précédente, il existe \((a, b) \in {\mathbb{N}^*}^2\) tels que \((x, y, z) = \delta^2(a^2-b^2, 2ab, a^2 + b^2)\). On a donc montré (avec la première question) que \[E = \{\delta^2(a^2 - b^2, 2ab, a^2 + b^2)~|~(a, b) \in {\mathbb{N}^*}^2,~ \delta \in \mathbb N\}\]


Nombres de Fermat **

18 novembre 2022 14:51 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

On appelle nombres de Fermat, les entiers de la forme \[F_n = 2^{2^n} + 1,\quad n \in \mathbb N.\]

  1. Montrer que pour tout entier \(x \in \mathbb N\) et tout \(p\in\mathbb{N}^*\), l’entier \(x^{2^p} - 1\) est divisible par \(x + 1\).

  2. Montrer que deux nombres de Fermat distincts sont premiers entre eux.


[ID: 3211] [Date de publication: 18 novembre 2022 14:51] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Nombres de Fermat
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:51

  1. On a \(1-\left(x^2\right)^p=\left(1-x^2\right)\sum_{k=0}^{p-1} \left(x^2\right)^k\) de quoi découle le résultat.

  2. Soient deux entiers \(n < m\). Posons \(p = m - n\) et écrivons \[F_m - 2 = 2^{2^m} - 1 = 2^{2^{n+p}} - 1 = 2^{2^n2^p} - 1 = \Bigl(2^{2^n}\Bigr)^{2^p} - 1\] Mais pour tout entier \(x\), l’entier \(x^{2^p} - 1\) est divisible par \(x + 1\). Il existe donc un entier \(q \in \mathbb N\) tel que \[F_m - 2 = (2^{2^n} + 1) q\] c’est-à-dire \[F_m - F_n q = 2.\] Il en résulte que \(F_m \wedge F_n\) est un diviseur de \(2\). Mais puisque les nombres de Fermat sont impairs, le seul diviseur possible est \(1\).


Suite de Fibonacci **

18 novembre 2022 14:51 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

On considère la suite de Fibonacci définie par \[u_0 = 0,~u_1 = 1,~ \textrm{ et } \forall n \in \mathbb N, u_{n+2} = u_{n+1} + u_n\]

  1. Montrer que \(\forall n \geqslant 1\), \(u_{n+1}u_{n-1} - u_n^2 = (-1)^n\).

  2. Montrer que deux termes consécutifs de la suite de Fibonacci sont premiers entre eux.

  3. Montrer que \[\forall n \in \mathbb N,\quad \forall p \in \mathbb{N}^*,\quad u_{n+p} = u_n u_{p-1} + u_{n+1} u_p\] et en déduire que \[u_n \wedge u_p = u_n \wedge u_{n+p}.\]

  4. Montrer que \[\forall (n, m) \in \mathbb{N}^{2},\quad u_n \wedge u_m = u_{n\wedge m}.\]

  5. Montrer que pour tout entier \(n \geqslant 5\), si \(u_n\) est un nombre premier, alors \(n\) est un nombre premier. La réciproque est-elle vraie ?


[ID: 3213] [Date de publication: 18 novembre 2022 14:51] [Catégorie(s): Bézout, PGCD, PPCM ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Suite de Fibonacci
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 14:51

  1. Par récurrence, en écrivant \[u_{n+2}u_n - u_{n+1}^2 = (u_ {n+1}+u_n)u_n - u_{n+1}^2 = u_{n+1}(\underbrace{u_n - u_{n+1}}_{=-u_{n-1}}) + u_n^2 = (-1)^{n+1}.\]

  2. L’identité précédente fournit une identité de Bézout entre \(u_n\) et \(u_{n+1}\).

  3. Par récurrence sur \(p\), en écrivant \(u_{n+p+1} = u_{n+1 + p}\) et en remarquant que \[\begin{aligned} u_{n+p+1} &= u_{n+1}u_{p-1} + u_{n+2}u_p \\ &= u_{n+1} u_{p-1} + (u_{n+1} + u_n) u_p \\ &= u_{n+1}(u_{p-1} + u_p) + u_n u_p \\ &= u_{n+1}u_{p+1} + u_nu_p. \end{aligned}\] De la relation précédente, tout entier qui divise \(u_n\) et \(u_p\) divise \(u_{n+p}\) et tout entier qui divise \(u_n\) et \(u_{n+p}\) divise le produit \(u_{n+1}u_p\), mais comme il est premier avec \(u_{n+1}\), il divise \(u_p\). Donc \[u_n \wedge u_p = u_n \wedge u_{n+p}.\]

  4. Appliquer le résultat précédent en faisant tourner l’algorithme d’Euclide.

  5. Soit \(n\) un entier supérieur à \(5\), tel que \(u_n\) soit premier. Si \(n\) n’était pas premier, on aurait un diviseur propre \(d \geqslant 3\). Mais alors \(u_n\) serait divisible par \(u_d\) avec \(2 \leqslant u_d < u_n\), ce qui est impossible. La réciproque est fausse avec \(n=19\), et \(u_{19} = 5181 = 37 \times 113\).


Les-Mathematiques.net Mathématiques vivantes

Thématiques

;
Success message!