$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Exercices corrigés - Nombres premiers - décomposition en produit de facteurs premiers

Nombres premiers
Exercice 1 - Algorithme pour compter le nombre de nombres premiers inférieurs à un entier $n$ [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
  1. Écrire une fonction $\textrm{divise}(p,q)$ d'argument deux entiers naturels non nuls $p$ et $q$ et renvoyant True si $p$ divise $q$, et False sinon.
  2. Écrire une fonction $\textrm{estpremier}(p)$ d'argument un entier naturel $p$, renvoyant $1$ si $p$ est premier, et renvoyant $0$ sinon.
  3. Écrire une fonction $\phi(n)$ d'argument un entier naturel $n$ et renvoyant le nombre de nombres premiers inférieurs ou égaux à $n$.
Corrigé
Enoncé
  1. Soit $q$ un entier impair. Démontrer que, pour tout $x\in\mathbb R$, $$x^q+1=(x+1)(x^{q-1}-x^{q-2}+\dots+1).$$
  2. Soit $m\in\mathbb N^*$ tel que $2^m+1$ soit premier. Montrer que $m=2^n$, où $n\in\mathbb N$.
Indication
Corrigé
Exercice 3 - Le magicien des mathématiques [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Bonjour, je suis le magicien des mathématiques. Vous allez choisir un nombre, effectuer une suite d'opérations, et je vais deviner le résultat.
  • Vous : "Incroyable, impossible!"
  • Moi : "Si! Tenez, choisissez un nombre premier différent de 2 et 3. Élevez-le au carré, ajoutez 17, divisez par 12, et rappelez-vous le reste!"
  • Vous : "Ouh, la,la, c'est compliqué! Ca y est!"
  • Moi : "C'est 6, n'est-ce pas!"
  • Vous : "Incroyable! Mais comment avez-vous fait?"
Et vous, saurez-vous déjouer le tour du magicien des mathématiques?
Indication
Corrigé
Enoncé
Soient $a,n\geq 2$ des entiers.
  1. Montrer que si $a^n-1$ est premier, alors $a=2$ et $n$ est premier.
  2. On note $M_n=2^n-1$ le $n$-ième nombre de Mersenne. Vérifier que $M_{11}$ n'est pas premier.
Indication
Corrigé
Exercice 5 - Premiers dans un intervalle [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $n\in\mathbb N$ vérifiant $10\leq n\leq 120$. Démontrer que $n$ est premier si et seulement s'il existe un entier $a\in\mathbb Z$ tel que $an\equiv 1[210].$
Indication
Corrigé
Exercice 6 - Une version faible du théorème de la progression arithmétique [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
  1. Démontrer que si un entier naturel est congru à $3$ modulo $4$, il admet un facteur premier congru à $3$ modulo $4$.
  2. Démontrer qu'il existe une infinité de nombres premiers de la forme $4k+3$.
Indication
Corrigé
Exercice 7 - Intervalles sans nombres premiers [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $q\geq 1$ un entier. Trouver un intervalle de longueur $q$ ne contenant pas de nombres premiers.
Indication
Corrigé
Application de la décomposition en produit de facteurs premiers
Exercice 8 - Divisibilité et puissance [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $a,b\in\mathbb N^*$ tels que $a^2|b^2$. Démontrer que $a|b$.
Indication
Corrigé
Enoncé
  1. Montrer qu'un entier naturel qui est à la fois un carré et un cube est aussi un entier à la puissance $6$.
  2. Généralisation : soient $a,b,p,q,n$ des entiers naturels avec $p\wedge q=1$ et $n=a^p=b^q$. Montrer qu'il existe un entier naturel $c$ tel que $n=c^{pq}$.
Indication
Corrigé
Exercice 10 - Le produit est un carré parfait [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soient $a$ et $b$ deux entiers premiers entre eux tels que leur produit $ab$ est un carré parfait. Montrer que $a$ et $b$ sont deux carrés parfaits.
Indication
Corrigé
Exercice 11 - Irrationalité du logarithme décimal de $2$ [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Démontrer que $\log_{10}2$ est irrationnel.
Indication
Corrigé
Exercice 12 - Application au calcul de pgcd [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soient $a,b,c\in\mathbb N^*$ et soit $n\in\mathbb N^*$.
  1. Démontrer que $c|ab\implies c|(a\wedge c)(b\wedge c)$.
  2. Démontrer que $(a\wedge b)^n=a^n \wedge b^n$.
  3. (Plus difficile) Calculer $(a^2+ab+b^2)\wedge ab$.
Indication
Corrigé
Exercice 13 - Nombre de diviseurs d'un entier [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $n$ un nombre entier, $n=p_1^{\alpha_1}\dots p_r^{\alpha_r}$ sa décomposition en produit de facteurs premiers. On note $d(n)$ le nombre de diviseurs de $n$.
  1. Montrer que $d(n)=\prod_{i=1}^r (\alpha_i+1)$.
  2. Montrer que $n$ est un carré parfait si et seulement si $d(n)$ est impair.
  3. Montrer que $\prod_{d|n}d=\sqrt{n}^{d(n)}$.
Indication
Corrigé
Enoncé
Soit $n\geq 1$ un entier et $p\geq 2$ un nombre premier. Soit aussi $N$ tel que $p^N\geq n$.
  1. Soit $u\geq 1$ un entier. Combien-y-a-t-il de multiples de $u$ dans $\{1,\dots,n\}$?
  2. Soit $k\geq 1$ et $A_k=\big \{l\in\{1,\dots,n\}:\ \nu_p(l)=k\big\}$. Calculer le cardinal de $A_k$.
  3. En déduire la formule de Legendre : $$\nu_p(n!)=\sum_{k=1}^N \left\lfloor \frac n{p^k}\right\rfloor.$$
  4. Par combien de zéros se termine le nombre $1000!\ $?
Indication
Corrigé
Exercice 15 - Produit des diviseurs d'un entier [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Déterminer tous les entiers naturels dont le produit des diviseurs (positifs) est égal à $45^{42}$.
Indication
Corrigé
Exercice 16 - Théorème de Kurshchak [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $n\geq 2$ un entier et $S_n=\sum_{i=1}^n \frac 1i$. Démontrer que $S_n$ n'est jamais un entier.
Indication
Corrigé
Petits problèmes avec des nombres premiers
Exercice 17 - Nombres puissants consécutifs [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
On dit qu'un entier naturel $n$ est un nombre puissant si, pour tbut diviseur premier $p$ de $n$, alors $p^2$ divise $n$. L'objectif de cet exercice est de démontrer qu'il existe une infinité de couples d'entiers naturels consécutifs puissants. Pour cela, on considère l'équation $(E)$ suivante, dont les inconnues $x$ et $y$ sont des entiers naturels : \[x^2-8y^2=1.\] On considère aussi la matrice $A=\begin{pmatrix}3&8\\1&3\end{pmatrix}$. On définit deux suites d'entiers naturels $(x_n)$ et $(y_n)$ par \[x_0=1,\ y_0=0,\ \textrm{ et pour tout entier naturel }n,\ \begin{pmatrix}x_{n+1}\\ y_{n+1}\end{pmatrix}=A\begin{pmatrix}x_n\\y_n\end{pmatrix}.\]
  1. Démontrer que, pour tout entier naturel $n$, $x_n>0$ et le couple $(x_n;y_n)$ est une solution de $(E)$.
  2. Démontrer que la suite $(x_n)$ est strictement croissante.
  3. En déduire que l'équation $(E)$ admet une infinité de solutions.
  4. Soit $a$ et $b$ deux entiers naturels et $n=a^2b^3$. Démontrer que $n$ est un nombre puissant.
  5. Montrer que si $(x,y)$ est un couple solution de $(E)$, alors $x^2-1$ et $x^2$ sont des entiers consécutifs puissants.
  6. En déduire qu'il existe une infinité de couples de nombres entiers consécutifs puissants.
  7. Écrire une fonction puissant(N) qui détermine un couple d'entiers consécutifs puissants qui sont tous deux supérieurs ou égaux à $N$.
Indication
Corrigé
Exercice 18 - Un code correcteur d'erreurs : le numéro INSEE [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Le numéro INSEE d'un individu est composé de 13 chiffres et d'une clé de contrôle de deux chiffres. Le premier chiffre est 1 pour les hommes, 2 pour les femmes. Les chiffres suivants sont les deux derniers chiffres de l'année de naissance, les deux suivants le mois de naissance, les deux suivants le département de naissance, les trois suivants la commune de naissance, les trois suivants le numéro d'inscription sur le registre de l'état-civil et les deux derniers sont une \emph{clé de contrôle} $C$. En notant $A$ le nombre formé des 13 premiers chiffres, on a $C=97-r$ où $r$ est le reste de la division euclidienne de $A$ par $97$.
  1. Vérifier la clé de votre numéro INSEE.
  2. Montrer que 97 est premier.
    On note $A_t=100A+C$ le numéro INSEE tout entier (c'est donc un nombre de 15 chiffres). Soit également $\tilde{A}_t$ un nombre obtenu à partir de $A_t$ en changeant un chiffre et un seul. On note $\tilde A$ les 13 premiers chiffres de $\tilde A_t$ et $\tilde C$ les deux derniers.
  3. On suppose que le changement de chiffre s'est effectué sur la clé $C$. Montrer que $\tilde C$ n'est pas la clé de contrôle de $\tilde A$. En déduire que $\tilde A_t$ n'est pas un numéro INSEE valide.
  4. On suppose que le changement de chiffre s'est effectué sur $A$ et que $\tilde C$ est la clé de contrôle de $\tilde A$.
    1. Montrer que $97$ divise $\tilde A-A$.
    2. Montrer que $|A-\tilde A|=a\times 10^n$, où $a$ et $n$ sont des entiers naturels avec $1\leq a\leq 9$.
    3. Conclure que $\tilde A_t$ n'est pas un numéro INSEE valide.
  5. Justifier l'utilité de la clé de contrôle à la fin du numéro INSEE. Quels autres nombres que 97 aurait-on pu choisir?
Indication
Corrigé
Enoncé
Soit $n$ un entier naturel. On note $\sigma(n)$ la somme des diviseurs positifs de $n$. On dit que $n$ est parfait si $\sigma(n)=2n$.
  1. Les nombres $6,28,32$ sont-ils parfaits?
  2. Soit $n$ un entier supérieur ou égal à $2$.
    1. Montrer que $\sigma(n)\geq n+1$.
    2. Démontrer que $n$ est premier si et seulement si $\sigma(n)=n+1$.
  3. Soit $a$ et $b$ deux entiers naturels non nuls, $a=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ et $b=q_1^{\beta_1}\cdots q_s^{\beta_s}$ leurs décompositions respectives en produits de facteurs premiers, avec $\alpha_i,\beta_j\geq 1$. On suppose de plus que $a$ et $b$ sont premiers entre eux.
    1. Que dire des $p_i$ et des $q_j$?
    2. Comment s'écrit un diviseur de $a$? un diviseur de $b$? un diviseur de $ab$?
    3. En déduire que l'application \begin{eqnarray*} \phi:\{\textrm{diviseurs de }a\}\times\{\textrm{diviseurs de }b\}&\to&\{\textrm{diviseurs de }ab\}\\ (m,n)&\mapsto&mn \end{eqnarray*} est une bijection, puis que $\sigma(a)\sigma(b)=\sigma(ab)$.
  4. Soit $p$ un nombre premier tel que $2^p-1$ soit premier. On note $E_p=2^{p-1}(2^p-1)$.
    1. Calculer $\sigma(2^{p-1})$ puis $\sigma(2^p-1)$.
    2. En déduire que $E_p$ est un nombre parfait.
  5. Dans cette question $n$ désigne un nombre parfait pair, $n=2^a b$ où $b$ est impair.
    1. Justifier que $\sigma(n)=2^{a+1}b$ puis que $2^{a+1}b=\sigma(b)(2^{a+1}-1)$.
    2. Démontrer que $2^{a+1}-1$ et $2^{a+1}$ sont premiers entre eux. En déduire que $2^{a+1}-1$ divise $b$. Par la suite, nous noterons $b=(2^{a+1}-1)c$.
    3. Démontrer que $$\sigma(b)=2^{a+1}c,\ n=2^a(2^{a+1}-1)c,\ \sigma(n)=2^{a+1}(2^{a+1}-1)c.$$
    4. On suppose que $c>1$. Démontrer qu'on a alors $\sigma(b)\geq 2^{a+1}c+1$. En déduire que $c=1$.
    5. Démontrer que $b$ est premier.
Indication
Corrigé