icone-math-OS-Exos
exercice 1 facile

On observe que, pour tout couple \left(a,b\right) d’entiers naturels :

    \begin{eqnarray*}a^{4}+4b^{4} & = & \left(a^{2}+2b^{2}\right)^{2}-4a^{2}b^{2}\\& = & \left(a^{2}+2ab+2b^{2}\right)\left(a^{2}-2ab+2b^{2}\right)\end{eqnarray*}


En particulier, pour a=125 et b=4 :

    \begin{eqnarray*}125^{4}+4\times4^{4} & = & \left(125^{2}+2\times125\times4+2\times4^{2}\right)\left(125^{2}-2\times125\times4+2\times4^{2}\right)\\& = & \left(15\thinspace625+1\thinspace000+32\right)\left(15\thinspace625-1\thinspace000+32\right)\\& = & 16\thinspace657\times14\thinspace657\end{eqnarray*}


Bref, l’entier 244\thinspace141\thinspace649=125^{4}+4^{5} est composé.

exercice 2 facile

Comme p est impair, alors p-1 et p+1 sont deux nombres pairs consécutifs, ce qui impose à l’un d’eux (seulement) d’être multiple de 4. Donc p^{2}-1 est multiple de 8.

Comme 24=3\times8 et vu que 3 et 8 sont premiers entre eux, il reste à prouver que p^{2}-1 est multiple de 3.

Mais comme p\geqslant5, alors en particulier 3\nmid p et donc de deux choses l’une :

  • soit p\equiv1\pmod{3}
  • soit p\equiv-1\pmod{3}

Dans les deux cas : p^{2}\equiv1\pmod{3}, ce qui permet de conclure.

exercice 3 facile

Notons \sigma\left(x\right) la somme des diviseurs positifs de x, pour tout entier x\geqslant1.

La condition “x et y sont amicaux” équivaut à \sigma\left(x\right)=\sigma\left(y\right)=x+y. On constate que :

    \begin{eqnarray*}a+b & = & 2^{n}\left(pq+r\right)\\& = & 2^{n}\left(2\times9\times2^{2n-1}-3\times2^{n}-3\times2^{n-1}\right)\end{eqnarray*}


c’est-à-dire :

    \begin{eqnarray*}a+b & = & 9\times2^{3n}-3\times2^{2n}-3\times2^{2n-1}\\& = & 9\left(2^{3n}-2^{2n-1}\right)\\& = & 9\times2^{2n-1}\left(2^{n+1}-1\right)\end{eqnarray*}

Comme p et q sont premiers et distincts, alors les diviseurs de a sont :

  • les 2^{k} pour 0\leqslant k\leqslant n
  • les 2^{k}p pour 0\leqslant k\leqslant n
  • les 2^{k}q pour 0\leqslant k\leqslant n
  • les 2^{k}pq pour 0\leqslant k\leqslant n

Leur somme est donc :

    \begin{eqnarray*}\sigma\left(a\right) & = & \left(1+p+q+pq\right)\left(\sum_{k=0}^{n}2^{k}\right)\\& = & \left(1+p\right)\left(1+q\right)\left(2^{n+1}-1\right)\end{eqnarray*}

Quant aux diviseurs de b, et vu que r est premier, ce sont :

  • les 2^{k} pour 0\leqslant k\leqslant n
  • les 2^{k}r pour 0\leqslant k\leqslant n

d’où leur somme :

    \begin{eqnarray*}\sigma\left(b\right) & = & \left(1+r\right)\sum_{k=0}^{n}2^{k}\\& = & \left(1+r\right)\left(2^{n+1}-1\right)\end{eqnarray*}


Mais il est clair que \left(1+p\right)\left(1+q\right)=1+r.

Donc :

    \begin{eqnarray*}\sigma\left(a\right) & = & \sigma\left(b\right)\\& = & 9\times2^{2n-1}\left(2^{n+1}-1\right)\\& = & a+b\end{eqnarray*}


comme souhaité.

L’une des clefs de cet exercice est l’identité remarquable :

({1)   \[\left(1+a\right)\left(1+b\right)\left(1+c\right)=1+a+b+c+ab+ac+bc+abc}\]


L’autre étant l’égalité :

({2)   \[7\times11\times13=1001}\]


En effet, la condition :

    \[a+b+c+ab+bc+ca+abc=1000\]


peut s’écrire, compte tenu de \left(1\right) et de \left(2\right) :

    \[\left(1+a\right)\left(1+b\right)\left(1+c\right)=7\times11\times13\]

Or, les trois nombres 1+a, 1+b et 1+c sont des entiers supérieurs ou égaux à 2, donc décomposables en produits de facteurs premiers. Si l’un (au moins) d’entre-eux était composé, le produit des trois possèderait au moins quatre facteurs premiers, ce qui est en désaccord avec le membre de droite, produit de seulement trois facteurs.

On voit ainsi que 1+a, 1+b et 1+c sont premiers. Par unicité de la décomposition en facteurs premiers, on a nécessairement :

    \[\left\{ 1+a,1+b,1+c\right\} =\left\{ 7,11,13\right\}\]


c’est-à-dire :

    \[\left\{ a,b,c\right\} =\left\{ 6,10,12\right\}\]


et finalement :

    \[\boxed{a+b+c=28}\]

Soit N un tel entier et 2r le nombre (supposé pair) de ses chiffres décimaux (avec r\geqslant1). Il existe alors des entiers a_{0},\cdots,a_{r 1}\in\left\{ 0,\cdots,9\right\} tels que :

    \[N=a_{0}\thinspace10^{2r-1}+a_{1}\thinspace10^{2r-2}+\cdots+a_{r-1}\thinspace10^{r}+a_{r-1}\thinspace10^{r-1}+\cdots+a_{1}\thinspace10+a_{0}\]


c’est-à-dire :

    \[N=\sum_{i=0}^{r-1}a_{i}\left(10^{i}+10^{2r-1-i}\right)\]


ou encore :

    \[N=\sum_{i=0}^{r-1}a_{i}10^{i}\left(1+10^{2r-2i-1}\right)\]


Or, 10\equiv-1\pmod{11} et donc 10^{k}\equiv-1\pmod{11} pour tout entier naturel impair k impair.

Il s’ensuit que N est multiple de 11 et donc que N ne peut être premier… sauf bien entendu si N=11 (c’est-à-dire si r=1).

On sait que, pour tout couple \left(a,b\right) d’entiers naturels et pour tout entier n\geqslant2 :

    \[a^{n}-b^{n}=\left(a-b\right)\left(a^{n-1}+a^{n-2}b+\cdots+ab^{n-2}+b^{n-1}\right)\qquad\left(\star\right)\]


Soit p\geqslant2 un entier non premier. Il existe donc deux entiers r,s tels que :

    \[p=rs\qquad\text{et}\qquad r,s>1\]


D’après \left(\star\right) :

    \begin{eqnarray*}2^{p}-1 & = & \left(2^{r}\right)^{s}-1\\& = & \left(2^{s}-1\right)\left(2^{\left(r-1\right)s}+\cdots+2^{s}+1\right)\end{eqnarray*}


avec d’une part :

    \[2^{s}-1\geqslant3>1\]


et d’autre part :

    \[2^{\left(r-1\right)s}+\cdots+2^{s}+1\geqslant2^{s}+1\geqslant5>1\]


ce qui montre que 2^{p}-1 n’est pas premier. On a prouvé (par contraposition) que si 2^{p}-1 est premier alors p est premier.

On va chercher d’éventuels nombres premiers dans la “moitié gauche” du triangle de Pascal c’est-à-dire parmi les \binom{n}{p} avec 0\leqslant p\leqslant n/2.

Vue la formule \binom{n}{p}=\binom{n}{n-p}, ceci se fait sans perte de généralité.

Soient n,p deux entiers naturels tels que 2\leqslant p\leqslant n/2.

D’après la formule du pion (on pourra consulter cette vidéo) :

    \[p\binom{n}{p}=n\binom{n-1}{p-1}\]


ce qui prouve que

    \[\binom{n}{p}\mid n\binom{n-1}{p-1}\]


On sait (lemme d’Euclide) que si nombre premier divise un produit d’entiers, il divise nécessairement l’un au moins des facteurs. Donc, si \binom{n}{p} est premier, alors :

    \[\binom{n}{p}\mid n\qquad\text{ou}\qquad\binom{n}{p}\mid\binom{n-1}{p-1}\]


La première éventualité est exclue car :

    \[\binom{n}{p}\geqslant\binom{n}{2}=\frac{n\left(n-1\right)}{2}>n\]


et la seconde aussi car sinon, il existerait un entier k\in\mathbb{N}^{\star} tel que :

    \[\binom{n-1}{p-1}=k\binom{n}{p}\]


c’est-à-dire :

    \[\frac{\left(n-1\right)!}{\left(p-1\right)!\thinspace\left(n-p\right)!}=k\thinspace\frac{n!}{p!\thinspace\left(n-p\right)!}\]


ou encore : p=kn, ce qui est absurde. Finalement, si 1\leqslant p\leqslant n/2, alors la seule possibilité pour que l’entier \binom{n}{p} soit premier est : p=1 et n premier.

En conclusion, les seuls couples \left(n,p\right)\in\mathbb{N}^{2} pour lesquels \binom{n}{p} est premier sont les \left(1,n\right) et les \left(n-1,n\right) avec n premier.

Soit p un nombre premier et soit k un entier tel que 1\leqslant k\leqslant p-1. D’après la formule du pion :

    \[k\binom{p}{k}=p\binom{p-1}{k-1}\]


et donc :

    \[p\mid k\binom{p}{k}\qquad\left(\heartsuit\right)\]


Mais k et p sont premiers entre eux (car k n’est clairement pas multiple de p et, vu que p est premier, les seuls entiers non premiers avec p sont ses multiples), donc d’après le théorème de Gauss :

    \[p\mid\binom{p}{k}\]


On peut, tout aussi bien, invoquer le lemme d’Euclide : comme p est premier, alors d’après \left(\heartsuit\right), on voit que p\mid k ou p\mid\binom{p}{k}, la première éventualité étant exclue.

Ensuite, on prouve par récurrence que, pour tout n\in\mathbb{N} :

    \[n^{p}\equiv n\pmod{p}\]


C’est vrai pour n=0, de manière évidente.

Supposons cette congruence vraie pour un certain n\in\mathbb{N}. Alors, d’après la formule du binôme :

    \begin{eqnarray*}\left(n+1\right)^{p} & = & \sum_{k=0}^{p}\binom{p}{k}n^{k}\\& = & n^{p}+1+\sum_{k=1}^{p-1}\binom{p}{k}n^{k}\end{eqnarray*}


et donc, d’après ce qui précède :

    \[\left(n+1\right)^{p}\equiv n^{p}+1\pmod{p}\]


Enfin, grâce à l’hypothèse de récurrence, on parvient à :

    \[\left(n+1\right)^{p}\equiv n+1\pmod{p}\]


comme souhaité.

exercice 9 difficile

On observe que, pour tout n\geqslant1 :

    \[\prod_{k=0}^{n-1}\left(2^{2^{k}}+1\right)=\prod_{k=0}^{n-1}\frac{\left(2^{2^{k}}+1\right)\left(2^{2^{k}}-1\right)}{2^{2^{k}}-1}=\prod_{k=0}^{n 1}\frac{2^{2^{k+1}}-1}{2^{2^{k}}-1}\]


soit, après simplification de ce produit télescopique :

    \[\prod_{k=0}^{n-1}F_{k}=2^{2^{n}}-1\]


c’est-à-dire :

    \[\boxed{\prod_{k=0}^{n-1}F_{k}=F_{n}-2}\]


Maintenant, supposons que deux nombres de Fermat, disons F_{k} et F_{n} pour 0\leqslant k<n, ne soient pas premiers entre eux et soit d>1 un diviseur commun. D’après la relation ci-dessus, on voit que d\mid2 et donc d=2. Mais ceci est absurde car les nombres de Fermat sont des entiers impairs.

On a prouvé par l’absurde que les entiers F_{k} sont deux à deux premiers entre eux.

Remarque

Si l’on note q_{k} le plus petit facteur premier de F_{k}, alors l’application \mathbb{N}\rightarrow\mathbb{P},\thinspace k\mapsto q_{k} est injective, d’après cette dernière propriété. On retrouve ainsi le fait que l’ensemble des nombres premiers est infini.


Si un point n’est pas clair ou vous paraît insuffisamment détaillé, n’hésitez pas à poster un commentaire ou à me joindre via le formulaire de contact.

Partager cet article
  •  
  •  
  •  
  •  

Laisser un commentaire

Fermer le menu