$$\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 math sup : Arithmétique

Divisibilité et division euclidienne
Exercice 1 - Comprendre la division euclidienne [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
  1. Déterminer les entiers positifs $a$ et $b$ sachant que $a<4000$ et que la division euclidienne de $a$ par $b$ donne un quotient de 82 et un reste de 47.
  2. Déterminer le quotient et le reste de la division euclidienne de $2^{2013}+562$ par $4$.
  3. Quand on divise un nombre par 12, le reste est 8. Quand on divise ce même nombre par 10, on augmente le quotient de $1$ et le reste devient 2. Quel est ce nombre?
  4. Démontrer que sur la droite $y=\frac 34x+\frac 18$, il n'y a pas de points à coordonnées entières.
Indication
Corrigé
Exercice 2 - Divisibilité et identité remarquable [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Démontrer que, pour tous $x,y\in \mathbb R$ et tout $n\in\mathbb N\backslash\{0\}$, on a $$x^n-y^n=(x-y)\sum_{k=0}^{n-1}x^k y^{n-1-k}.$$ En déduire que $609|5^{4n}-2^{4n}.$
Indication
Corrigé
Exercice 3 - Une relation de divisibilité [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Déterminer les entiers relatifs $n$ tels que $n-4$ divise $3n-17$.
Indication
Corrigé
Enoncé
Soit $n\geq 1$ un entier. Déterminer le reste dans la division euclidienne par $n$ de la somme des $n$ premiers entiers strictement positifs.
Indication
Corrigé
Exercice 5 - Division euclidienne avec de grands nombres [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soient $a,b,n$ trois entiers supérieurs ou égaux à 1. On note $q$ le quotient de la division euclidienne de $a-1$ par $b$, et $r$ le reste. Déterminer le quotient et le reste de la division euclidienne de $ab^n-1$ par $b^{n+1}$.
Indication
Corrigé
Exercice 6 - Grands nombres divisibles [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Montrer que pour tout entier $n\geq 1$, $40^n n!|(5n)!$.
Indication
Corrigé
Exercice 7 - Équations diophantiennes du second degré résolues par factorisation [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Résoudre les équations d'inconnues $(x,y)\in\mathbb N^2$ :
  1. $x^2-y^2=7$;
  2. $9x^2-y^2=32$.
Indication
Corrigé
Enoncé
Soit $b\geq 2$ un entier. On souhaite démontrer que tout entier $n\geq 1$ s'écrit uniquement $$n=\sum_{k=0}^p a_k b^k$$ avec $p\geq 0$, $a_k\in\{0,\dots,b-1\}$ et $a_p\geq 1$.
  1. Existence : démontrer l'existence en procédant par récurrence forte. Pour l'hérédité, on pourra utiliser la division euclidienne de $n$ par $b$.
  2. Unicité : on suppose que $n$ admet deux décompositions distinctes \[ n=\sum_{k=0}^p a_k b^k\textrm{ et }n=\sum_{k=0}^{p'}a'_k b^k. \] On peut supposer $p\geq p'$. Quitte à compléter la suite $a'_k$ par $a'_{p'+1}=\dots=a'_p=0$, on peut supposer que $p=p'$. Soit $\ell\in\{0,\dots,p\}$ le plus grand possible tel que $a_\ell\neq a'_\ell$.
    1. Vérifier que $(a_\ell-a'_\ell)b^\ell=\sum_{k=0}^{\ell-1}(a'_k-a_k)b^k$.
    2. Démontrer que, pour toute suite finie $c_0,\dots,c_{\ell-1}$ avec $0\leq c_k\leq b-1$, on a \[\sum_{k=0}^{\ell-1}c_k b^k < b^\ell. \]
    3. Conclure.
  3. Donner l'écriture de 37 (écrit en base 10) en base 2, puis en base 3.
Indication
Corrigé
Exercice 9 - Une équation de type Fermat [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Le but de l'exercice est de résoudre l'équation $2^k=a^2+b^2$, avec $k\in\mathbb N$, $a,b\in\mathbb N^*$.
  1. Démontrer que si $N,a$ et $b$ sont des entiers tels que $N=a^2+b^2$ et $N$ est un multiple de $4$, alors $a$ et $b$ sont pairs.
  2. En déduire que l'équation $2^{2n}=a^2+b^2$, $n\in\mathbb N$, $a,b\in\mathbb N^*$ n'admet pas de solutions.
  3. Démontrer que l'équation $2^{2n+1}=a^2+b^2$, $n\in\mathbb N$, $a,b\in\mathbb N^*$ admet une unique solution que l'on précisera.
Indication
Corrigé
Pgcd, ppcm et nombres premiers entre eux
Exercice 10 - Pour bien commencer... [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
  1. Quels sont les diviseurs communs à 390 et 525?
  2. Calculer $(3^{123}-5)\wedge 25$.
  3. Soit $n\in\mathbb Z$. Démontrer que $6|n(n+1)(n+2)$.
Indication
Corrigé
Exercice 11 - Des équations de Bezout [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Résoudre les équations suivantes dans $\mathbb Z^2$ :
  1. $2x+5y=3$;
  2. $323x-391y=612$;
  3. $162x+207y=27$;
  4. $221x+247y=15$.
Indication
Corrigé
Exercice 12 - Irrationnalité d'un quotient de logarithmes [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $a,b\geq 2$ deux entiers premiers entre eux. Démontrer que $\ln(a)/\ln(b)$ est irrationnel.
Indication
Corrigé
Exercice 13 - Rationnels qui sont entiers [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soient $a$ et $b$ deux rationnels tels que $a+b$ et $a\times b$ sont des entiers. Prouver que $a$ et $b$ sont des entiers.
Indication
Corrigé
Exercice 14 - Points à coordonnées entières sur une droite rationnelle [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Le plan est muni d'un repère $(O,\vec i,\vec j)$. On considère 4 entiers relatifs non nuls $m,n,p$ et $q$ tels que $\textrm{pgcd}(m,n)=\textrm{pgcd}(p,q)=1$. Le but de l'exercice est de déterminer une condition nécessaire et suffisante portant sur $m,n,p,q$ pour que la droite $\Delta$ d'équation $y=\frac mn x-\frac pq$ comporte au moins un point dont les coordonnées sont deux entiers relatifs.
  1. On suppose dans cette question que la droite $\Delta$ comporte un point de coordonnées $(x_0,y_0)$ où $x_0$, $y_0$ sont des entiers relatifs.
    1. Démontrer que $q$ divise le produit $np$.
    2. En déduire que $q$ divise $n$.
  2. Réciproquement, on suppose que $q$ divise $n$ et on souhaite trouver un couple $(x_0,y_0)$ d'entiers relatifs tels que $y_0=\frac mnx_0-\frac pq$.
    1. On pose $n=qr$, où $r$ est un entier relatif non nul. Démontrer que l'on peut trouver deux entiers relatifs $u$ et $v$ tels que $qru-mv=1$.
    2. En déduire qu'il existe un couple $(x_0,y_0)$ d'entiers relatifs tels que $y_0=\frac mn x_0-\frac pq$.
  3. On donne l'algorithme suivant :


    Variables :
      m,n,p,q entiers relatifs non nuls tels que pgcd(m,n)=pgcd(p,q)=1
      x entier naturel
    Algorithme
      Si q divise n alors
         x prend la valeur 0
         Tant que (mx/n - p/q) n'est pas un entier et (-mx/n-p/q) n'est pas un entier faire
             x prend la valeur x+1
         Fin Tant Que
         Si (mx/n-p/q) est entier alors Afficher x, mx/n-p/q
         Sinon Afficher -x,-mx/n-p/q
         Fin Si
      Sinon Afficher "Pas de solutions"
      Fin Si.

    Justifier que cet algorithme se termine. Que permet-il d'obtenir?

Indication
Corrigé
Enoncé
Soient $n\in\mathbb Z$. Calculer les pgcd suivants : $$\begin{array}{lll} \mathbf 1.\ (n^2+n)\wedge (2n+1)&\quad\quad&\mathbf 2.\ (15n^2+8n+6)\wedge(30n^2+21n+13)\\ \end{array} $$
Indication
Corrigé
Enoncé
J'ai une pile de livres. Lorsque je les range par 10, il m'en reste 3. Lorsque je les range par 17, il m'en reste 2. Quel est le nombre minimum de livres que je possède? Quels sont tous les nombres possibles?
Indication
Corrigé
Exercice 17 - Pas de solutions rationnelles [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Montrer que l'équation $x^3-x^2+x+1=0$ n'a pas de solutions dans $\mathbb Q$.
Indication
Corrigé
Exercice 18 - Termes consécutifs d'une suite [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $(u_n)$ la suite d'entiers définie par $u_0=14$ et $u_{n+1}=5u_n-6$. Démontrer que le pgcd de deux termes consécutifs de la suite est constant. Préciser sa valeur.
Indication
Corrigé
Exercice 19 - pgcd et somme ou produit prescrits [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
  1. Déterminer les couples d'entiers naturels de pgcd 18 et de somme 360.
  2. Déterminer les couples d'entiers naturels de pgcd 18 et de produit 6480.
Indication
Corrigé
Exercice 20 - Équation avec pgcd et ppcm [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Trouver tous les couples d'entiers $(x,y)\in\mathbb N^2$ tels que $x\vee y+11(x\wedge y)=203$.
Indication
Corrigé
Enoncé
Soient $a,m,n\in\mathbb N^*$ avec $a\geq 2$ et $m\leq n$. On note $d=(a^n-1)\wedge (a^m-1)$ et $r$ le reste dans la division euclidienne de $n$ par $m$.
  1. Montrer que $a^n\equiv a^r\ [a^m-1]$.
  2. En déduire que $d=(a^r-1)\wedge (a^m-1)$, puis que $d=a^{n\wedge m}-1$.
  3. A quelle condition $a^m-1|a^n-1$?
Indication
Corrigé
Nombres premiers et décomposition en produit de facteurs premiers
Exercice 22 - 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é
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 25 - 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 26 - 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é
Exercice 27 - 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 29 - 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 30 - 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 31 - 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 33 - 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é
Congruences
Enoncé
  1. Déterminer, suivant les puissances de $n\in\mathbb N$, le reste de la division euclidienne de $2^n$ par $5$.
  2. Quel est le reste de la division par 5 de $1357^{2013}$?
Indication
Corrigé
Exercice 35 - Un entier divisible par $6$ [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Démontrer que pour tout $n\in\mathbb Z$, $n(n+2)(7n-5)$ est divisible par $6$.
Indication
Corrigé
Enoncé
Soit $n\in\mathbb N$ et $a=n^5-n$.
  1. Démontrer que $a$ est divisible par $5$.
  2. En remarquant que $a=n(n-1)(n+1)(n^2+1)$, démontrer que $a$ est divisible par $2$ et par $3$.
  3. Démontrer que $a$ est divisible par $30$.
Indication
Corrigé
Exercice 37 - Somme de trois cubes consécutifs [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Démontrer que la somme de trois cubes consécutifs est toujours divisible par 9.
Indication
Corrigé
Exercice 38 - Deux équations avec des congruences [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
  1. Déterminer les entiers naturels $n$ tels que $5^n\equiv -1\ [13]$.
  2. Déterminer les entiers naturels $n$ tels que 13 divise $5^{2n}+5^n$.
Indication
Corrigé
Exercice 39 - Puissance et congruence [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $a,b\in\mathbb Z$ et $n\geq 2$. On suppose que $a\equiv b\ [n]$. Démontrer que $a^n\equiv b^n\ [n^2]$.
Indication
Corrigé
Enoncé
Montrer que tout entier naturel est congru modulo 9 à la somme des chiffres de son écriture décimale. En déduire que, quels que soient les entiers naturels $x=\overline{a_n\dots a_0}$, $y=\overline{b_m\dots b_0}$ et $z=\overline{c_p\dots c_0}$, si $xy=z$, alors $\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]$.
Indication
Corrigé
Exercice 41 - Résolution d'équations diophantiennes en raisonnant modulo un entier [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Résoudre les équations suivantes dans $\mathbb Z^2$ :
  1. $x^2-5y^2=3$ (on raisonnera modulo $5$);
  2. $15x^2-8y^2=9$ (on raisonnera modulo $5$).
Indication
Corrigé
Enoncé
Démontrer que, pour tout entier naturel $n$, $3^{2n+1} + 2^{4n+2}$ est divisible par 7.
Indication
Corrigé
Enoncé
Soit $m$ un entier naturel non-nul, et soit $(r_i)$ la suite d'entiers définie par $r_0=1$ et $r_{i+1}$ est le reste de la division euclidienne de $10r_i$ par $m$.
  1. Démontrer que, pour tout entier naturel $a=\overline{a_n\dots a_0}$ en écriture décimale, on a $a\equiv\sum_{i=0}^n a_ir_i\ [m]$.
  2. En déduire des critères simples permettant de reconnaitre sur l'écriture décimale d'un réel s'il est ou non divisible par 3, par 9, par 10, par 11.
Indication
Corrigé
Exercice 44 - Équations de congruence du premier degré [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Résoudre les équations suivantes :
  1. $5x\equiv 3\ [17]$;
  2. $10x\equiv 6\ [34]$;
  3. $10x \equiv 5\ [34]$.
Indication
Corrigé
Exercice 45 - Un système de congruences [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Résoudre le système suivant, d'inconnue $x\in\mathbb Z$ : $$\left\{ \begin{array}{rcl} x&\equiv&1\ [5]\\ x&\equiv&2\ [11]. \end{array}\right.$$
Indication
Corrigé
Enoncé
Un nombre palindrome est un nombre qui se lit indifféremment de gauche à droite ou de droite à gauche. Par exemple, 2002, 12321 sont des nombres palindromes. Prouver qu'un nombre palindrome ayant un nombre pair de chiffres est divisible par 11
Indication
Corrigé
Exercice 47 - Une équation diophantienne [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Le but de l'exercice est de déterminer tous les couples d'entiers $(m,n)\in\mathbb N^2$ tels que $2^m-3^n=1$.
  1. Déterminer le reste de la division euclidienne de $3^n$ par $8$ (on distinguera les cas $n$ pair et $n$ impair).
  2. En déduire que si $(m,n)\in\mathbb N^2$ est solution de $2^m-3^n=1$, alors $m\leq 2$.
  3. Déterminer toutes les solutions de l'équation.
Indication
Corrigé
Exercice 48 - Somme de deux carrés divisible par 7 [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $a$ et $b$ deux entiers tels que $a^2+b^2$ soit divisible par $7$. Démontrer que $a$ et $b$ sont divisibles par $7$.
Indication
Corrigé
Exercice 49 - Coefficients binomiaux [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
  1. Soit $n\geq 1$. Montrer que $(n+1)|\binom{2n}{n}$.
  2. Soit $p\geq 2$ premier. Montrer que $p|\binom{p}{k}$ pour $k\in\{1,\dots,p-1\}$.
  3. En déduire une preuve du petit théorème de Fermat : si $n\geq 1$ et $p$ est premier, $n^p\equiv n\ [p]$.
Indication
Corrigé