Exercices corrigés - pgcd, ppcm, nombres premiers entre eux

Supposons que $\ln(a)/\ln(b)$ est rationnel et soit $p,q\geq 1$ avec $p\wedge q=1$ tel que $\frac{\ln(a)}{\ln(b)}=\frac pq$. Ceci entraîne que $\ln(a^q)=\ln(b^p)$ et donc, par injectivité de la fonction $\ln$, que $a^q=b^p$. Ainsi, $a|b^p$. Mais ceci contredit que $a\wedge b=1$.

Remarquons d'abord que si $a$ ou $b$ est nul, c'est trivial. On suppose donc que $a\neq 0$ et $b\neq 0$, et on écrit ces réels sous forme de fraction irréductible, $a=\frac{p_1}{q_1}$ et $b=\frac{p_2}{q_2}$, avec $q_1,q_2>0$ et $p_1\wedge q_1=1$, $p_2\wedge q_2=1$. On a alors $$a+b=\frac{p_1q_2+p_2q_1}{q_1q_2}\in\mathbb Z.$$ On en déduit que $q_1|(p_1q_2+p_2q_1)$. Or, on sait déjà que $q_1|p_2q_1$. On a donc $q_1|p_1q_2$. De plus, puisque $q_1\wedge p_1=1$, le théorème de Gauss nous dit que $q_1|q_2$. Par symétrie, on a aussi $q_2|q_1$, et donc $q_1=q_2=q$. Le produit $ab$ vaut alors $$ab=\frac{p_1p_2}{q^2},$$ et donc $q|p_1p_2$. Ceci implique (toujours par le lemme de Gauss) que $q|p_1$ et comme $q\wedge p_1=1$, on a $q\wedge p_1=q=1$. Ainsi, $a$ et $b$ sont des entiers.

Les nombres de position de chaque roue, 47, 53, 59, 61, 64, 65, 67, 69, 71 et 73, sont des nombres premiers entre eux. Avant de revenir à la position initiale, il faut que chaque roue ait fait un ou plusieurs tours complets. Ainsi, il faut que le nombre de caractères entré soit un multiple de 47, et un multiple de 53, etc... Puisque les nombres sont premiers entre eux, le plus petit nombre de caractères à entrer avant de revenir à la position initiale, qui est le plus petit multiple commun de 47, 53, 59, 61, 64, 65, 67, 69, 71 et 73, est : $$47\times 53\times 59\times 61\times 64\times 65\times 67\times 69\times 71\times 73.$$ Ce nombre vaut $893 622 318 929 520 969$ : c'est énorme!

On va appliquer l'algorithme d'Euclide. Pour cela, on cherche la congruence modulo 15 de $2^{445}+7$. Or, $2^4\equiv 1\ [15]$. On remarque ensuite que $445=4*111+1$. Ainsi, $2^{445}=2\times (2^{4})^{111}\equiv 2\times1\ [15]$. D'où on déduit finalement $$2^{445}+7\equiv 9\ [15].$$ Ainsi, appliquant l'algorithme d'Euclide, le pgcd cherché est aussi le pgcd de 9 et 15, c'est-à-dire 3.

L'équation $au+bv=x$ a toujours une solution $(u_0,v_0)$ dans $\mathbb Z^2$ d'après le théorème de Bezout. De plus, l'ensemble des solutions est constitué par les couples $(u_k,v_k)$ avec $u_k=u_0+kb$, $v_k=v_0-ka$, $k\in\mathbb Z$. Puisque $(u_k)_{k\in\mathbb Z}$ est croissante, tend vers $-\infty$ en $-\infty$ et vers $+\infty$ en $+\infty$, il existe un entier $k$ tel que $u_{k-1}\leq 0\leq u_k$. Montrons que $v_k\geq 0$. Pour cela, on écrit $$x=au_k+bv_k=a(u_{k-1}+b)+bv_k$$ soit $$bv_k=x-ab-au_{k-1}.$$ Puisque $x-ab\geq 0$ et $au_{k-1}\leq 0$, on en déduit $bv_k\geq 0$, ou encore $v_k\geq 0$.

Soit $N$ le nombre de livres. L'information que l'on donne est que le reste dans la division euclidienne de $N$ par $10$ (respectivement par $17$) vaut $3$ (respectivement $2$). Ainsi, il existe $a$ et $b$ des entiers naturels tels que $N=10a+3$ et $N=17b+2$. Faisant la différence, on trouve que $(a,b)$ est une solution de l'équation de Bézout $17b-10a=1$.
On résoud cette équation. Le couple $(a,b)=(5,3)$ est solution, et donc les couples solutions sont les couples $(a,b)$ avec $a=5+17k$ et $b=3+10k$, avec $k\in\mathbb N$ (il n'y a pas de $-$ car l'équation de Bézout comporte déjà un $-$). Ainsi, si $N$ est le nombre de livres, il existe $k\in\mathbb N$ (car le nombre de livres est positif!) tel que $N=53+170k$.
Réciproquement, on vérifie que $53+170k= 10\times (17k+5)+3=17\times(10k+3)+2$. Le nombre minimal de livres possible est 53, les nombres possibles sont ceux de la forme $53+170k$ avec $k\in\mathbb N$. Bien sûr, le nombre minimal de livres possibles aurait pu être trouvé à l'aide d'un tableur.

Les entiers naturels $a$ et $b$ sont solutions de l'équation $24a+45b=903.$ Remarquons que le pgcd de $24$ et $45$ est $3.$ L'équation est donc équivalente à $8a+15b=301.$ On cherche tous les couples $(a,b)\in\mathbb N^2$ solutions de cette équation. On commence par trouver $a_0$ et $b_0$ tel que $8a_0 +15b_0=1.$ Il n'est peut-être pas la peine d'utiliser l'algorithme d'Euclide ici, car on remarque facilement que $$8\times 2+15\times (-1)=1.$$ On en déduit que $$8\times 602+15\times (-301)=301.$$ On sait aussi que $(a,b)$ vérifie $$8a+15b=301.$$ En faisant la différence des deux équations, on trouve $$8\times (a-602)+15\times (b+301)=0\iff 8\times (a-602)=-15\times(b+301).$$ On a donc $8|15\times(b+301)$ et puisque $8$ et $15$ sont premiers entre eux, on a finalement $8|b+301.$ Ainsi, il existe $k\in\mathbb Z$ tel que $b=-301+8k.$ Si on reporte ceci dans l'équation $a-602=-15\times (b+301),$ on trouve $a=602-15k.$
On veut maintenant $b\geq 0.$ Ceci implique $-301+8k\geq 0$ ou encore $k\geq 38.$ On veut aussi $a\geq 0$, ce qui revient à dire $602-15k\geq 0$ ou encore $k\leq 40.$ Finalement, on trouve 3 couples de solutions : $$(32,3),\ (17,11)\textrm{ et }(2,19).$$

En notant $j$ le jour de naissances et $m$ le mois de naissances, on doit résoudre $$12m+31j=811.$$ C'est une équation de Bézout, qu'on peut résoudre "naïvement", mais c'est bien sûr impossible de tête. L'idée est que l'on sait que m est forcément compris entre 1 et 12. On regarde la congruence modulo 31, et on obtient $12m\equiv 811\ [31] \equiv 5\ [31]$. Mais, pour $m$ allant de $1$ à $12$, les entiers $12m$ ont des congruences modulo 31 différentes les unes des autres. Ainsi, on trouve dans l'ordre $12, 24, 5, 17, 29, 10, 22, 3, 15, 27, 8, 20$. Ceci nous donne immédiatement $m=3$, puis, en retournant à l'équation $12m+31j=811$, $j=25$.

Admettons qu'il existe une solution rationnelle $x=p/q$, avec $p\wedge q=1$ et $q>0$. Alors, remplaçant $x$ par $p/q$ dans l'équation et multipliant tout par $q^3$, on obtient : $$p^3-p^2q+pq^2+q^3=0.$$ Puisque $q|p^2q+pq^2+q^3$, on obtient $q|p^3$ et donc $q=1$ puisque $p$ et $q$ sont premiers entre eux. En effectuant le même raisonnement avec $p$, on obtient $p=\pm 1$. Or $1$ et $-1$ ne sont pas solutions de l'équation. Il y a donc contradiction.

De la relation $u_{n+1}=5u_n-6$, on tire que tout diviseur commun de $u_n$ et de $u_{n+1}$ divise aussi 6. Ainsi, le pgcd de $u_n$ et $u_{n+1}$ ne peut qu'être un élément de $\{1,2,3,6\}$. Par ailleurs, on va démontrer par récurrence sur $n$ que 2 divise $u_n$ et que $3$ ne divise pas $u_n$. C'est bien le cas pour $u_0=14$, et considérons $n\in\mathbb N$ tel que $2$ divise $u_n$ et $3$ ne divise pas $u_n$. Alors, $2|5u_n$ et $2$ divise $6$, donc $2$ divise $u_{n+1}=5u_n-6$. De plus, si on avait $3|u_{n+1}$, alors $3|u_{n+1}+6$ et donc $3|5u_{n}$. De plus, par le théorème de Gauss, puisque $3\wedge 5=1$, on tire $3|u_{n}$, ce qui est une contradiction.
Ainsi, pour tout entier $n$, on a prouvé que $2|u_n$ et $3$ ne divise pas $u_n$. Ainsi, si $d_n$ est le pgcd de $u_n$ et $u_{n+1}$, $2|d_n$ et $3$ ne divise pas $d_n$. Puisque l'on sait déjà que $d_n\in\{1,2,3,6\}$, on a nécessairement $d_n=2$.

On pose $d=x\wedge y$ et on écrit $x=dx'$, $y=dy'$ et $x'\wedge y'=1$. L'équation devient $$d(x'y'+11)=203=7\times 29.$$ On a donc $d=1,7,29$ ou $203$ et on sépare les cas.

• Les cas $d=29$ et $d=203$ ne conduisent pas à une solution, puisqu'on a alors $x'y'=7-11<0$ ou $x'y'=1-11<0$, ce qui est impossible puisque $x'$ et $y'$ sont positifs.
• Pour $d=1$, on a $x'y'=192=2^6\times 3$. Puisque $x'\wedge y'=1$, on obtient que $(x',y')$ est un des couples $(192,1)$, $(3,2^6)$, $(2^6,3)$ ou $(1,192)$.
• Pour $d=7$, on a $x'y'=18=2\times 3^2$. Puisque $x'\wedge y'=1$, on obtient que $(x',y')$ est un des couples $(18,1)$, $(2,9)$, $(9,2)$ ou $(1,18)$.

En remultipliant par $d$, on trouve que l'ensemble des solutions est constitué par les couples $(1,192)$, $(3,64)$, $(7,126)$, $(14,63)$ et leurs symétriques.

Le point de départ de cet exercice est la description de l'ensemble des solutions de l'équation de Bézout. Si $(u_0,v_0)$ est une solution particulière, alors l'ensemble des solutions est $\mathcal S=\{(u_0+kb,v_0-ka):\ k\in\mathbb Z\}$. Démontrons d'abord l'unicité d'une solution $(u,v)$ telle que $2|u|\leq b$ et $2|v|<a$. Si $(u,v)$ et $(u',v')$ sont deux solutions vérifiant cette condition, alors on sait que $v-v'$ est un multiple de $a$. En outre, $|v-v'|\leq |v|+|v'|<\frac a2+\frac a2=a$. Ainsi, on a nécessairement $v=v'$ et donc $u=u'$.
Démontrons maintenant l'existence d'une telle solution. Soit $$A=\{k\in\mathbb Z:\ v_0+ka\leq a/2\}.$$ Alors $A$ est une partie de $\mathbb Z$ non-vide et majorée. Elle possède donc un plus grand élément $\ell$, et on note $u=u_0-\ell b$ et $v=v_0+\ell a$. Alors on sait que $v=v_0+\ell a\leq a/2$ et $v=v_0+(\ell+1)a>a/2$. Cette dernière inégalité donne $$v=v_0+\ell a>\frac{a}{2}-a>-\frac a2.$$ Ainsi, on a $|v|\leq a/2$. Il faut encore démontrer qu'on ne peut pas avoir égalité, c'est-à-dire, puisqu'on a déjà obtenu $v>-a/2$, qu'on ne peut pas avoir $v=a/2$. Si c'était le cas, puisque $a>2$, on aurait $v>1$, et l'égalité $au+bv=1$ s'écrirait encore $2vu+bv=1$. Ainsi, $v|1$ ce qui contredit $v>1$. On a bien démontré que $|v|<a/2$.
D'autre part, on a $au=1-bv$ et donc $$a|u|\leq 1+b|v|.$$ Ceci entraîne que $$2a|u|\leq 2+2b|v|=2-b+b(2|v|+1)\leq 0+ab$$ ce qui donne $|u|\leq b/2$.