Nombres premiers

  1. Les exercices
  2. Vue compacte

Exercices du dossier Nombres premiers

Petit théorème de Fermat *

18 novembre 2022 15:33 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Soit \(p\) un nombre premier.

  1. Montrer que \(\forall k\in\llbracket 1,p-1\rrbracket, \quad p\mid\dbinom{p}{k}\).

  2. En déduire le petit théorème de Fermat : \[\forall n\in\mathbb{Z},\quad p\mid n^p-n.\]


[ID: 3215] [Date de publication: 18 novembre 2022 15:33] [Catégorie(s): Nombres premiers ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Petit théorème de Fermat
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 15:34

  1. Soit \(k\in\llbracket 1,p-1\rrbracket\). On sait que \(A_p^k=k!\dbinom{p}{k}\). Mais \(p\mid A_p^k=p\left(p-1\right)\dots\left(p-n+1\right)\) donc comme \(p\) est premier \(p\mid k!\) ou \(p\mid\dbinom{p}{k}\). Si \(p\mid k!\) alors \(p\) divise un des entiers \(1,2,\dots,k<p\) ce qui n’est pas possible et prouve la propriété.

  2. On effectue un raisonnement par récurrence. Si \(n=0\) alors la propriété est vérifiée. Soit \(n\in\mathbb{N}\). On la suppose vraie au rang \(n\) : \(p\mid n^p-n\) et on montre que \(p\mid \left(n+1\right)^p-\left(n+1\right)\). On utilise la formule du binôme  : \[\begin{aligned} \left(n+1\right)^p-\left(n+1\right)= \sum_{k=0}^{p} \dbinom{p}{k}n^k-\left(n+1\right)=n^p-n+ \sum_{k=1}^{p-1} \dbinom{p}{k}n^k.\end{aligned}\] Comme \(p\mid n^p-n\) et que \(p\mid\dbinom{p}{k}\) pour \(k\in\llbracket 1,p-1\rrbracket\), on sait que \(p\mid\left(n+1\right)^p-\left(n+1\right)\) et le petit théorème de Fermat est prouvée par récurrence pour \(n\geqslant 0\). Si \(n<0\) et si \(p=2\) alors \(n^2-n=n\left(n-1\right)\) est clairement divisible par \(2\). Si \(p>2\), comme \(p\) est premier il est impair et en notant \(m=-n\), on a \(n^p-n=-m^p+m=-\left(m^p-m\right)\) qui est divisible par \(p\).


Exercice 1487 **

18 novembre 2022 15:34 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Soit \(n \in \mathbb N\). Montrer que \[2^n - 1 \textrm{ premier } \Rightarrow n \textrm{ premier }\]


[ID: 3217] [Date de publication: 18 novembre 2022 15:34] [Catégorie(s): Nombres premiers ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1487
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 15:34

Soit \(p\) et \(q\) deux entiers naturels. On a \(2^{pq} - 1 = \left( 2^p\right)^q - 1^q = \left( 2^p - 1\right) \left( 2^{p(q-1)} + 2^{p(q-2)} + \ldots + 2^p + 1 \right)\). Si on prend \(p\) et \(q\) plus grands que \(1\), alors \(2^p - 1 \geqslant 3\) et la somme \(2^{p(q-1)} + 2^{p(q-2)} + \ldots + 2^p + 1\) comporte \(q\) termes tous plus grands que \(1\). Donc \(2^{pq} - 1\) est composé. En résumé, si \(pq\) est composé, alors \(2^{pq} - 1\) est composé. Par contraposée, si \(2^n - 1\) est premier, alors \(n\) est premier.


Exercice 1488 **

18 novembre 2022 15:34 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Montrer que le nombre \(n^4-n^2+16\) avec \(n\in\mathbb{Z}\) est composé.


[ID: 3219] [Date de publication: 18 novembre 2022 15:34] [Catégorie(s): Nombres premiers ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1488
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 15:34

On factorise : \(n^4-n^2+16=\left(n^2 +4\right)^2-9n^2=\left(n^2-3n+4\right)\left(n^2+3n+4\right)\). Les deux trinômes \(x^2-3x+4\) et \(x^2+3x+4\) ne s’annulent pas sur \(\mathbb{R}\) et donc pas sur \(\mathbb{Z}\). On vérifie qu’il en est de même des trinômes \(x^2-3x+4\pm 1\) et \(x^2+3x+4\pm 1\). Le nombre \(n^4-n^2+16\) est donc bien composé.


Exercice 1489 **

18 novembre 2022 15:34 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

  1. Prouver que pour tout \(x\in\mathbb{C}\) et \(p\in\mathbb{N}\), \[x^p+1=\left(x+1\right)\left(1-x+x^2+\dots+x^{p-1}\right)\]

  2. Soit \(a\in \mathbb{N}\) et \(n\in \mathbb{N}\) tels que \(a^n+1\) est premier.

    1. Montrer qu’il existe \(k\in\mathbb{N}\) tel que \(n=2^k\).

    2. Que penser de l’affirmation : \(\forall n\in\mathbb{N}, \quad 2^{2^n}+1\) est premier ?


[ID: 3221] [Date de publication: 18 novembre 2022 15:34] [Catégorie(s): Nombres premiers ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1489
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 15:34

  1. On développe la seconde partie de l’égalité et on simplifie par télescopage.

    1. On va effectuer un raisonnement par contraposée. On suppose que \(n\) n’est de la forme \(n=2^k\) pour aucun \(k\in\mathbb{N}\). Alors \(n\) est de la forme \(pq\) avec \(p>2\) premier et \(q\in\mathbb{N}\). On écrit alors \[a^n+1=a^{pq}+1=\left(a^q\right)^p+1=\left(a^q+1\right)\left(1-a^q+\left(a^q\right)^2-\dots+\left(a^q\right)^{p-1}\right)\] et on remarque que les deux facteurs de ce produit sont strictement plus grand que \(1\). Donc \(a^n+1\) n’est pas premier.

    2. Avec un logiciel de calcul formel, on montre que \(2^{2^5}+1=641\times 6700417\).


Exercice 1490 **

18 novembre 2022 15:34 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

À la suite d’un hold-up, on interroge quatre témoins qui ont vu les malfaiteurs s’enfuir en voiture : Antonin dit que le numéro d’immatriculation comporte quatre chiffres. Bébert, que les deux premiers chiffres sont identiques. Corentin que les deux derniers chiffres sont identiques. Dudule le matheux a remarqué que le nombre en question est un carré parfait. Quel est ce numéro d’immatriculation ?


[ID: 3223] [Date de publication: 18 novembre 2022 15:34] [Catégorie(s): Nombres premiers ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1490
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 15:34

Le numéro d’immatriculation s’écrit \(N = \overline{aabb} = 11\times100a+11b = 11(100a+b)\). Donc \(11\mid N\). Comme \(N\) est un carré parfait, l’exposant de \(11\) dans la décomposition de \(N\) en facteurs premiers est pair. Donc \(11^2 = 121\) divise \(N\) : soit \(N = 121k\). Comme \(N\) est un carré parfait, \(k\) l’est aussi (regarder sa décomposition en facteurs premiers). Donc \(N = 121M^2\) avec \(M\in\mathbb N\). Les essais pour \(M\) variant de \(1\) à \(9\) montrent que seul \(M=8\) convient, et alors \(N = 7744 =88^2\).
Remarque : On pourrait aller plus vite en remarquant qu’un nombre dont les deux derniers chiffres sont impairs n’est jamais un carré parfait. Mais c’est un autre exercice...


Exercice 1491 ***

18 novembre 2022 15:34 — Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces

Au cours d’un congrès de mathématiques, des mathématiciens (en nombre \(n\)) sont logés dans les \(n\) chambres d’un hôtel. Ils décident (dans des circonstances qui restent a déterminer), de s’attribuer le numéro de leur chambre. Avant que la horde ne se mette à envahir l’hôtel toutes leurs chambres sont fermées. Le mathématicien numéro \(k\) doit changer l’état (ouvert/fermé) des chambres qui portent un numéro multiple du sien.

  1. Quel est le nombre de portes qui seront ouvertes après le passage des mathématiciens ?

  2. Démontrer que \(\sum_{k=1}^n\left\lfloor \dfrac nk \right\rfloor - \lfloor \sqrt n \rfloor\) est un entier pair (On rappelle que \(\lfloor x \rfloor\) désigne la partie entière de \(x\)).


[ID: 3225] [Date de publication: 18 novembre 2022 15:34] [Catégorie(s): Nombres premiers ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 3 ] [Auteur(s): Emmanuel Vieillard-Baron Alain Soyeur François Capaces ]
Solution

Exercice 1491
Par Emmanuel Vieillard-Baron Alain Soyeur François Capaces le 18 novembre 2022 15:34

  1. Plaçons nous du point de vue d’une porte. Elle sera ouverte après le passage des mathématiciens si son état (ouvert/fermé) a été modifié par un nombre impair de mathématiciens (et fermée sinon). Autrement dit elle sera ouverte in fine si son numéro \(m\) admet un nombre impair de diviseurs (positifs). On décompose \(m\) en facteurs premiers : \(m = \prod_{p \in \mathbb{P}} p^{\nu_p(m)}\). Les diviseurs \(d\) de \(m\) s’écrivent donc \(d = \prod_{p \in \mathbb{P}} p^{\nu_p(d)}\) avec \(\forall\,p \in \mathbb{P}, \;\nu_p(d)\leqslant\nu_p(m)\). Pour chaque choix de nombre premier \(p\) divisant \(m\) on a \(\nu_p(m)+1\) puissances de \(p\) qui divisent \(m\), à savoir \(1, p, p^2,\ldots,p^{\nu_p(m)}\) il y a donc un total de \(\prod_{p \in \mathbb{P}}(\nu_p(m)+1)\) diviseurs de \(m\). Maintenant un produit de facteurs est impair si et seulement si chacun des facteurs est impairs, donc dans notre cas on doit avoir tous les \(\nu_p(m)+1\) impairs c’est-à-dire tous les \(\nu_p(m)\) pairs ce qui signifie que \(m\) est un carré parfait.
    Une autre façon de voir : Si \(d\) est un diviseur de \(m\) alors \({\scriptstyle m\over\scriptstyle d}\) est aussi un diviseur de \(m\). On peut ainsi regrouper les diviseurs de \(m\) deux par deux, sauf si, par extraordinaire, \(m\) et \({\scriptstyle m\over\scriptstyle d}\) sont égaux, c’est-à-dire lorsque \(m = d^2\) donc lorsque \(m\) est un carré parfait.
    Notre problème devient donc : Combien y a-t-il de carrés parfaits entre \(1\) et \(n\) ? Il y en a \(\lfloor \sqrt n \rfloor\).

  2. Plaçons nous du point de vue du mathématicien numéro \(k\). Il change l’état (ouvert/fermé) des portes \(k, 2k, \ldots\). De combien de portes change-t-il l’état ? En \(n\) combien de fois \(k\) ? Il va \(\left\lfloor \dfrac nk \right\rfloor\). Il y a donc eu au total \(\sum_{k=1}^n\left\lfloor \dfrac nk \right\rfloor\) changement d’état. Si on enlève les \(\lfloor \sqrt n \rfloor\) portes exceptionnelles, toutes les portes ont changé un nombre pair de fois. C’est bien dire que \(\sum_{k=1}^n\left\lfloor \dfrac nk \right\rfloor - \lfloor \sqrt n \rfloor\) est un entier pair.


Les-Mathematiques.net Mathématiques vivantes

Thématiques

;
Success message!