Exercices corrigés - Divisibilité et congruence

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.

Posons $u_n=(3-\sqrt{5})^n+(3+\sqrt{5})^n$. L'idée est de prouver que la suite $(u_n)$ vérifie une relation de récurrence d'ordre 2. En effet, elle est de la forme $u_n=r_1^n+r_2^n$. D'après la théorie des suites récurrentes linéaires, $(u_n)$ vérifie l'équation de récurrence linéaire dont l'équation caractéristique associée est $$X^2-(r_1+r_2)X+r_1r_2=0\iff X^2-6X+4=0.$$ Autrement dit, on a $u_{n+2}=6u_{n+1}-4u_n$. Bien sûr, on peut vérifier directement que la suite $(u_n)$ satisfait cette condition de récurrence.
On prouve alors par récurrence sur $n$ que $2^n$ divise $u_n$. C'est vrai pour $n=0$, car $u_0=2$ et pour $n=1$, car $u_1=6$. Supposons que $2^n|u_n$ et $2^{n+1}|u_{n+1}$. Alors, écrivant $u_n=k2^n$ et $u_{n+1}=l2^{n+1}$, on a $$u_{n+2}=2\times 3\times l2^{n+1}-2^2\times k2^n=2^{n+2}(3l-k).$$ Ceci prouve le résultat demandé.

Notons, pour $k\geq 1$, $\mathcal P(k)$ l'hypothèse suivante : "tout entier $n\geq 1$ qui est le produit de $k$ entiers distincts possède au moins $\frac{k(k-1)}2+1$ diviseurs distincts". Prouvons par récurrence sur $k$ que, pour tout $k\geq 1$, $\mathcal P(k)$ est vraie.
Initialisation : $\mathcal P(1)$ est vraie, car $n$ admet alors au moins un diviseur (lui-même), et si $k=1$, $\frac{k(k-1)}2+1=1$.
Hérédité : soit $k\geq 1$ tel que $\mathcal P(k)$ est vraie et prouvons $\mathcal P(k+1)$. Soit $n$ un produit de $k+1$ entiers distincts. Alors $n$ s'écrit $n=a_1 a_2\cdots a_{k+1}$ où $a_1<a_2<\dots<a_{k+1}$. Posons $m=n/a_{k+1}$. Alors $m$ est le produit de $k$ entiers distincts, et donc $m$ admet au moins $\frac{k(k-1)}2$ diviseurs distincts. De plus, si $d$ est un diviseur de $m$, alors $da_{k+1}$ est un diviseur de $n$. Notons $A$ les diviseurs de $m$ et $B=\{a_{k+1}d;\ d\in A\}$. Alors, puisque $a_1<a_{k+1}$, ..., $a_k<a_{k+1}$, les élements $a_1,\dots,a_k$ ne sont pas éléments de $B$ alors qu'ils sont éléments de $A$. On sait aussi que $A$ et $B$ ont le même cardinal. Dans $B$, il y a donc au moins $k$ éléments qui ne sont pas dans $A$ (puisque dans $A$, il y a au moins $k$ éléments qui ne sont pas dans $B$). Ainsi, on a trouvé au moins $k$ diviseurs supplémentaires de $n$. Ainsi, $n$ possède au moins $$\frac{k(k-1)}2+k=\frac{k(k+1)}2$$ diviseurs. Ceci prouve que $\mathcal P(k+1)$ est vraie.
Conclusion : par le principe de récurrence, $\mathcal P(k)$ est vraie pour tout entier $k$.

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].$$

On va commencer par étudier les puissances de $3$ modulo $13$. On commence par remarquer que $$3^1\equiv 3\ [13],\quad 3^2\equiv 9\ [13],\ 3^3\equiv 1\ [13].$$ On sait donc que, puisque $126=3*42$, $3^{126}\equiv (3^3)^{42}\ [13]$, et donc $3^{126}\equiv 1\ [13]$. De même, on a $$5^1\equiv 5\ [13],\quad 5^2\equiv 12\ [13],\quad 5^3\equiv 8\ [13],\quad 5^4\equiv 1[13].$$ Par un raisonnement similaire, et utilisant que $126=31*4+2$, on trouve $$5^{126}\equiv 5^2\ [13]\textrm{ soit }5^{126}\equiv 12\ [13].$$ On en déduit que $$3^{126}+5^{126}\equiv 0\ [13],$$ ce qui signifie bien que $13$ divise $3^{126}+5^{126}$.

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.

Soit $a\in\mathbb Z$. Pour $j\geq 1$, on pose $$\mathcal P_j: "a^{p^j}\equiv a\ [p]."$$ On prouve par récurrence que $\mathcal P_j$ est vraie pour tout $j\geq 1$.
Initialisation : $\mathcal P_1$ est vraie d'après le petit théorème de Fermat.
Hérédité : Soit $j\geq 1$ tel que $a^{p^j}\equiv a\ [j]$. Alors par le petit théorème de Fermat appliqué à $b=a^{p^j}$, on trouve que \begin{align*} a^{p^{j+1}}&=b^p\\ &\equiv b\ [p]\\ &\equiv a^{p^j}\ [p]\\ &\equiv a\ [p]. \end{align*} Ainsi, $\mathcal P_{j+1}$ est vraie.
On en déduit alors que : \begin{align*} \left(\sum_{i=1}^N x_i\right)^{p^j}&\equiv \sum_{i=1}^n x_i\ [p]\\ &\equiv \sum_{i=1}^N x_i^{p^j}\ [p] \end{align*} en alignant la propriété précédente une première fois avec $a=\sum_{i=1}^N x_i$ et une deuxième fois avec $a=x_i$, $i=1,\dots,N.$