Exercices math sup : Arithmétique

Développons le membre de droite de l'identité que l'on nous demande de démontrer. \begin{eqnarray*} (x-y)\sum_{k=0}^{n-1}x^k y^{n-1-k}&=&\sum_{k=0}^{n-1}x^{k+1}y^{n-1-k}-\sum_{k=0}^{n-1}x^k y^{n-k}\\ &=&\sum_{k=1}^n x^ky^{n-k}-\sum_{k=0}^{n-1}x^k y^{n-k} \end{eqnarray*} en effectuant un changement d'indice dans la première somme. Mais les deux sommes sont identiques, à deux termes près, et on a donc $$(x-y)\sum_{k=0}^{n-1}x^k y^{n-1-k}=x^ny^{n-n}-x^0y^{n-0}=x^n-y^n.$$ Le fait que $609|5^{4n}-2^{4n}$ est alors une application immédiate de cette identité à $x=5^4$ et $y=2^4$, puisque dans ce cas $x-y=609$.

Puisque $n-4$ divise $3n-17$ et que $n-4$ divise $n-4$, $n-4$ divise également $(3n-17)-3(n-4)=-5$. Or les diviseurs dans $\mathbb Z$ de $-5$ sont $-5,-1,1,5$. Les valeurs possibles de $n-4$ sont donc ces valeurs, et donc on a $n\in \{-1,3,5,9\}$.
Réciproquement, si $n=-1$, alors $n-4=-5$ divise $3n-17=-20$. Si $n=3$, $n-4=-1$ divise $3n-17=-8$. Si $n=5$, $n-4=1$ divise $3n-17=-2$. Si $n=9$, $n-4=5$ divise $3n-17=10$.
En conclusion, les valeurs de $n$ qui conviennent sont $-1,3,5$ et $9$.

Soit $S_n$ la somme des $n$ premiers entiers. Elle vaut $\frac{n(n+1)}2$. Si $n$ est impair, autrement dit si $n+1$ est pair, alors $(n+1)/2$ est un entier, et $n|S_n$. Le reste est donc 0. Si maintenant $n=2k$ est pair, alors $$S_n=\frac{2k(2k+1)}2=\frac{(2k)^2}{2}+k=k\times 2k+k=k\times n+n/2$$ Le reste est donc $n/2$.

La division euclidienne s'écrit $a-1=bq+r$, avec $0\leq r\leq b-1$. On multiplie ensuite tout par $b^n$ et on trouve $ab^n-b^n=b^{n+1}q+rb^n$, puis on se ramène à $$ab^n-1=b^{n+1}q+rb^n+b^n-1=b^{n+1}q+r'$$ où $r'=rb^n+b^n-1$. On remarque que $0\leq r'\leq (b-1)b^n+b^n-1=b^{n+1}-1$. On a donc écrit la division euclidienne de $ab^n-1$ par $b^{n+1}$, le quotient est $q$ et le reste est $rb^n+b^n-1$.

On raisonne par récurrence sur $n$. La propriété est clairement vérifiée si $n=1$, car $5!=120=40\times 3$. Supposons la propriété vraie au rang $n$, et prouvons la au rang $n+1$. On a \begin{align*} (5n+5)!&=(5n)!(5n+1)(5n+2)(5n+3)(5n+4)(5n+5)\\ &= (5n)! 5(n+1)(5n+1)(5n+2)(5n+3)(5n+4) \end{align*} et $$40^{n+1} (n+1)!=40^n n!\times 40(n+1).$$ Puisque par hypothèse de récurrence, $40^n n!|(5n)!$, il suffit de prouver que $40(n+1)|5(n+1)(5n+1)(5n+2)(5n+3)(5n+4)$, ou encore $8|(5n+1)(5n+2)(5n+3)(5n+4)$. Mais $5n+1,5n+2,5n+3,5n+4$ sont quatre entiers consécutifs. Deux sont pairs, et l'un des ces deux entiers pairs est même divisible par 4. Donc 8 divise bien leur produit.

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.

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.

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.

Soit $n\geq 1$ et $I=\{n!+2,n!+3,\dots,n!+n\}$. Prenons un entier $m=n!+k$ dans $I$. Alors $k$ est un diviseur strict de $m$, puisque $1<k<m$, et $k|k$, $k|n!$ puisque $k\leq n$, donc $k|m$. Ainsi, $I$ est un intervalle de $(n-1)$ entiers ne comportant pas de nombres premiers. Si on a choisi $n=q+1$, alors on a répondu au problème posé par l'énoncé.

Décomposons $a$ et $b$ en produit de facteurs premiers : $$a=\prod_{i=1}^r p_i^{\alpha_i},\ b=\prod_{i=1}^r p_i^{\beta_i}.$$ On a donc $$a^2=\prod_{i=1}^r p_i^{2\alpha_i},\ b^2=\prod_{i=1}^r p_i^{2\beta_i}.$$ La condition $a^2|b^2$ se traduit par, pour tout $i=1,\dots,r$, $2\alpha_i\leq 2\beta_i$. Mais ceci entraîne que $\alpha_i\leq\beta_i$ et donc que $a|b$.

1. Détaillons d'abord ce que signifie la question. Soit $n$ un entier qui est à la fois un carré et un cube, i.e. $n=a^2$ et $n=b^3$. On veut prouver que c'est le carré d'un cube, c'est-à-dire qu'il existe un entier $c$ tel que $n=(c^3)^2=c^6$. Décomposons $n$, $a$ et $b$ en produit de facteurs premiers : \begin{eqnarray*} n&=&p_1^{n_1}\dots p_r^{n_r}\\ a&=&p_1^{\alpha_1}\dots p_r^{\alpha_r}\\ b&=&p_1^{\beta_1}\dots p_r^{\beta_r}\\ \end{eqnarray*} Par unicité de la décomposition en produit de facteurs premiers, puisque $n=a^2$, on a $n_i=2\alpha_i$, et puisque $n=b^3$, on a $n_i=3\beta_i$ pour tout $i\in\{1,\dots,r\}$. Ainsi chaque $n_i$ est multiple de 2 et de 3. C'est donc aussi un multiple de 6 et $n_i=6\gamma_i$. Posons alors $$c=p_1^{\gamma_1}\dots p_r^{\gamma_r}.$$ Alors $c^6=n$.
2. Décomposons $a$ et $b$ en produit de facteurs premiers, $a=p_1^{\alpha_1}\dots p_r^{\alpha_r}$ et $b=p_1^{\beta_1}\dots p_r^{\beta_r}$. L'égalité $a^p=b^q$ se traduit par $p\alpha_j=q\beta_j$ pour tout $j=1,\dots,r$. On a donc $q|p\alpha_j$ et puisque $p\wedge q=1$, on obtient $q|\alpha_j$. Ecrivons $\alpha_j=q\gamma_j$ et reportons. On trouve $pq\gamma_j=q\beta_j$ soit $\beta_j=p\gamma_j$. Ainsi, si on pose $c=p_1^{\gamma_1}\dots p_r^{\gamma_r}$ on a bien $n=c^{pq}$.

Décomposons $a,b$ et $ab$ en produit de facteurs premiers, $a=p_1^{\alpha_1}\dots p_r^{\alpha_r}$ et $b=p_1^{\beta_1}\dots p_r^{\beta_r}$, $ab=p_1^{2\gamma_1}\dots p_r^{2\gamma_r}$ (on a utilisé que $ab$ est un carré parfait). Bien sûr, pour tout $j$, on a la relation $2\gamma_j=\alpha_j+\beta_j$. De plus, puisque $a\wedge b=1$, si $\alpha_j$ est non-nul, alors $\beta_j=0$, et réciproquement. On a alors ou bien $\alpha_j=2\gamma_j$ et $\beta_j=0$, ou bien $\beta_j=2\gamma_j$ et $\alpha_j=0$. Dans tous les cas, $\alpha_j$ et $\beta_j$ sont tous les deux pairs. Ainsi, $a$ et $b$ sont des carrés parfaits.

Remarquons d'abord que $45^{42}$ se décompose en facteurs premiers sous la forme $3^{84}5^{42}$. Ainsi, un entier $n$ dont le produit des diviseurs est égal à $45^{42}$ est forcément de la forme $3^p5^q$. Maintenant, les diviseurs d'un tel entier sont tous les nombres de la forme $3^k 5^l$ avec $0\leq k\leq p$ et $0\leq l\leq q$. Ainsi, le produit de ces diviseurs est égal à \begin{eqnarray*} \prod_{k=0}^p \prod_{l=0}^q 3^k 5^l&=&\prod_{k=0}^p \left(3^{k(q+1)}\prod_{l=0}^q 5^l\right)\\ &=&\prod_{k=0}^p \left(3^{k(q+1)}5^{\frac{q(q+1)}2}\right)\\ &=&3^{\frac{p(p+1)(q+1)}2}5^{\frac{q(q+1)(p+1)}2}. \end{eqnarray*} $p$ et $q$ sont donc solutions du système $$\left\{ \begin{array}{rcl} p(p+1)(q+1)&=&168\\ q(q+1)(p+1)&=&84. \end{array} \right.$$ Si on fait le quotient de ces deux équations, on obtient $p=2q$, ce qui donne encore $$q(q+1)(2q+1)=84.$$ La seule solution est $q=3$ et donc $p=6$. Ainsi, il y a un unique entier naturel dont le produit des diviseurs est $45^{42}$. Il s'agit de $3^65^3$.

Puisque $6=2\times 3$ avec $2\wedge 3=1$, il suffit de prouver que $n(n+2)(7n-5)$ est divisible par $2$ et est divisible par $3$. Commençons par la divisibilité par $2$. On va raisonner par disjonction de cas. Si $n\equiv 0\ [2]$, alors clairement $n(n+2)(7n+5)\equiv 0\ [2]$. Si $n\equiv 1\ [2]$, alors $7n-5\equiv 2\ [2]$ et donc $7n+5\equiv 0\ [2]$. A nouveau, on a $n(n+2)(7n+5)\equiv 0\ [2]$.
Étudions maintenant la divisibilité par $3$. On raisonne encore par disjonction de cas, le cas $n\equiv 0\ [3]$ se traite comme précédemment. Si $n\equiv 1\ [3]$, on conclut en utilisant que $n+2\equiv 0\ [3]$ et si $n\equiv 2\ [3]$, on conclut en remarquant que $7n-5\equiv 9\ [3]$ et donc $7n-5\equiv 0\ [3]$.

On développe $n^3+(n+1)^3+(n+2)^3$ : $$n^3+(n+1)^3+(n+2)^3=3n^3+9n^2+15n+9=9(n^2+1)+3n(n^2+5).$$ Il suffit donc de démontrer que $9|3n(n^2+5)$ ou encore que $3|n(n^2+5)$. Si $n\equiv 0\ [3]$, c'est bien sûr vrai. Si $n\equiv 1\ [3]$, on a $n^2\equiv 1\ [3]$ et donc $n^2+5\equiv 6\equiv 0\ [3]$. Si $n\equiv 2\ [3]$, alors $n^2+5\equiv 4+5\equiv 9\equiv 0\ [3]$. Dans tous les cas, $3n(n^2+5)$ est divisible par 9.

Puisque $a\equiv b\ [n]$, il existe $k\in\mathbb Z$ tel que $a=b+kn$. Mettons ceci à la puissance $n$. On en déduit que \begin{eqnarray*} a^n&=&(b+kn)^n\\ &=&\sum_{j=0}^n \binom n j b^{n-j}k^j n^j\\ &=& b^n+\binom n1 b^{n-1}kn+\sum_{j=2}^n \binom n j b^{n-j}k^j n^j\\ &=&b^n +b^{n-1}k n^2+n^2\sum_{j=2}^n \binom nj b^{n-j}k^j n^{j-2}. \end{eqnarray*} Puisque pour tout $j\geq 2$, $\binom nj b^{n-j}k^jn^{j-2}$ est un entier, on en déduit que $a^n=b^n+\ell n^2$ avec $\ell\in\mathbb Z$ et donc que $a^n\equiv b^n\ [n^2]$.

Le point crucial est que $10$ est congru à 1 modulo 9. Ainsi, $10^2=10\times 10\equiv 1\times 1=1[9]$, et une récurrence facile montre que pour tout entier $k$, alors $10^k$ est congru à 1 modulo 9. Notons $x=\overline{a_n\dots a_0}$. Alors on a : \begin{eqnarray*} x&\equiv&10^n a_n+10^{n-1}a_{n-1}+\dots+10 a_1+a_0\ [9]\\ &\equiv& a_n +a_{n-1}+\dots +a_0\ [9]. \end{eqnarray*} La deuxième partie de l'exercice s'en déduit aisément. En effet, on écrit que $$xy=z\implies xy\equiv z\ [9]\implies \left(\sum_{i=0}^n a_i\right)\left(\sum_{i=0}^m b_i\right)\equiv\left(\sum_{i=0}^p c_i\right)\ [9].$$

Notons, pour $n\in\mathbb N$, la propriété $\mathcal P(n)=$"$3^{2n+1} + 2^{4n+2}$ est divisible par $7$". Prouvons par récurrence que pour tout $n\in\mathbb N$, $\mathcal P(n)$ est vérifiée.
Initialisation : On a $3^1+2^2=7$ qui est bien divisible par 7.
Hérédité : Soit $n\in\mathbb N$ tel que $\mathcal P(n)$ est vraie. Remarquons que $3^2\equiv 2\ [7]$ et que $2^4\equiv 2\ [7]$. Alors, on écrit (modulo 7) : \begin{eqnarray*} 3^{2n+3}+2^{4n+6}&\equiv&3^2 3^{2n+1}+2^4 2^{4n+2}\ [7]\\ &\equiv& 2 \times 3^{2n+1}+2\times 2^{4n+2}\ [7]\\ &\equiv& 2\times (3^{2n+1}+2^{4n+2})\ [7]\\ &\equiv& 2\times 0\ [7]\\ &\equiv& 0\ [7]. \end{eqnarray*} Ainsi, $7$ divise $3^{2n+3}+2^{4n+6}$ et donc $\mathcal P(n+1)$ est vraie.
En conclusion, par le principe de récurrence, $\mathcal P(n)$ est vraie pour tout $n\in\mathbb N$.

Soit $x$ une solution du système. Puisque $x\equiv 1\ [5]$, il existe $k\in\mathbb Z$ tel que $x=1+5k$. Reportant dans la deuxième équation, on trouve $1+5k\equiv 2\ [11]$ soit $5k\equiv 1\ [11]$. Multiplions ceci par $2$. Puisque $10\equiv -1\ [11]$, on obtient $$-k\equiv 2\ [11]\iff k\equiv -2\ [11].$$ Il existe donc $\ell\in\mathbb Z$ tel que $k=-2+11\ell$. Finalement, on a prouvé que si $x$ est solution, alors $x=1-10+55\ell=-9+55\ell$, $\ell\in\mathbb Z$.
Réciproquement, si $x=-9+55\ell$, $\ell\in\mathbb Z$, on écrit $x=1+5\times (-2+11\ell)$ puis $x=2+11\times(-1+5\ell)$ pour prouver que $x$ est bien solution du système.

Écrivons un tel nombre $n=a_1\dots a_p a_p\dots a_1$, c'est-à-dire \begin{eqnarray*} n&=&10^{2p-1}a_1+10^{2p-2}a_2+\dots+10^p a_p+10^{p-1}a_{p}+10 a_2+a_1\\ &=&\sum_{k=1}^p (10^{k-1}+10^{2p-k})a_k. \end{eqnarray*} Remarquons ensuite que $10=-1\textrm{ (mod }11)$, et donc $10^k=(-1)^k\textrm{ (mod }11)$. On obtient donc \begin{eqnarray*} 10^{k-1}+10^{2p-k}&=&(-1)^{k-1}+(-1)^{2p-k}\textrm{ (mod }11)\\ &=&(-1)^{k-1}+(-1)^k\textrm{ (mod }11)\\ &=&0\textrm{ (mod }11) \end{eqnarray*} Ainsi, chaque terme $(10^{k-1}+10^{2p-k})a_k$ est congru à 0 modulo 11. Il en est de même pour $n$.

Commençons par écrire un tableau décrivant les carrés modulo 7. $$\begin{array}{c|c|c|c|c|c|c|c} x\ [7]&0&1&2&3&4&5&6\\ \hline x^2\ [7]&0&1&4&2&2&4&1\\ \end{array}$$ On distingue alors 4 cas :

• Si $a^2=0$ modulo 7, alors $a^2+b^2=0$ modulo 7 si et seulement si $b=0$ modulo 7 : c'est le cas où $a$ et $b$ sont tous les deux divisibles par 7.
• Si $a^2=1$ modulo 7, pour que $7|a^2+b^2$, il faudrait que $b^2=6$ modulo 7, ce qui est impossible.
• Si $a^2=2$ modulo 7, pour que $7|a^2+b^2$, il faudrait que $b^2=5$ modulo 7, ce qui est impossible.
• Si $a^2=4$ modulo 7, pour que $7|a^2+b^2$, il faudrait que $b^2=3$ modulo 7, ce qui est impossible.

Ainsi la seule possibilité est bien que $a$ et $b$ soient divisibles par 7.