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

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+kb$, $v_k=v-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+k)+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.

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 $(192,1)$.
• 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.