$$\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 - Divisibilité et congruence

Divisibilité - 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.
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 - 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é
Exercice 8 - Suite récurrente linéaire [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Démontrer que, pour tout entier $n\geq 0$, $(3-\sqrt{5})^n+(3+\sqrt{5})^n$ est divisible par $2^n$.
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 10 - 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é
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 12 - Division de puissances [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Démontrer que $13$ divise $3^{126}+5^{126}$.
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é
Enoncé
On cherche à trouver les solutions modulo $n$ de l'équation $ax\equiv b\ [n]$, où $a,b,c$ sont trois entiers naturels (supérieurs ou égaux à 1). On note $d=a\wedge n$.
  1. Justifier que l'équation admet une solution si et seulement si $d$ divise $b$.
  2. Dans cette question, on suppose que $d$ divise $b$. On note $x_0$ une solution et on pose $n=dn'$.
    1. Démontrer que l'ensemble des solutions de l'équation est $\{x_0+qn';\ q\in\mathbb Z\}.$
    2. En déduire que l'équation admet exactement $d$ solutions modulo $n$.
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 17 - Une suite arithmético-géométrique [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
On considère la suite $(u_n)$ d'entiers naturels définie par $u_0=14$ et $u_{n+1}=5u_n-6$.
  1. Quelle conjecture peut-on émettre sur les deux derniers chiffres de $(u_n)$?
  2. Montrer que pour tout entier naturel $n$, $u_{n+2}\equiv u_n\ [4]$. En déduire que pour tout entier naturel $k$, on a $u_{2k}\equiv 2\ [4]$ et $u_{2k+1}\equiv 0\ [4]$.
    1. Montrer que pour tout entier naturel $n$, on a $2u_n=5^{n+2}+3$.
    2. En déduire que pour tout entier naturel $n$, on a $2u_n\equiv 28\ [100]$.
  3. Valider la conjecture émise à la première question.
Indication
Corrigé
Exercice 18 - 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 19 - 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 20 - Points à coordonnées entières sur un cercle de l'espace [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Dans l'espace muni d'un repère orthonormé $(O;\vec i,\vec j,\vec k)$ on considère le point $F$ de coordonnées $(0,0,1/4)$ et $\mathcal P$ le plan d'équation $z=-1/4$. Pour un point $M$ du plan, on note $H$ le projeté orthogonal de $M$ sur $\mathcal P$ et $\mathcal E$ l'ensemble des points $M$ tels que $MH=MF$.
  1. Démontrer que $\mathcal E$ a pour équation $x^2+y^2=z$.
  2. Soit $x,y$ des entiers. Démontrer que $7|x^2+y^2$ si et seulement si $7|x$ et $7|y$.
  3. Existe-t-il des points qui appartiennent à l'intersection de $\mathcal E$ et du plan $z=98$ dont toutes les coordonnées sont des entiers? Si oui, les déterminer.
Indication
Corrigé
Exercice 21 - Congruences simultanée - Problème du cuisiner chinois [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
  1. Soient $n,m,c$ trois entiers tels que $n\wedge m=1$. Montrer que l'équation $nx\equiv c\ [m]$ admet une unique solution modulo $m$.
  2. Soient $n,m,a,b$ quatre entiers avec $n\wedge m=1$. Montrer que le système $$\left\{\begin{array}{rcl}x&\equiv&a\ [n]\\x&\equiv&b\ [m].\end{array}\right.$$ admet une unique solution modulo $nm$.
  3. Un phare émet un signal jaune toutes les 15 secondes et un signal rouge toutes les 28 secondes. On aperçoit le signal jaune 2 secondes après minuit et le rouge 8 secondes après minuit. A quelle heure verra-t-on pour la première fois les deux signaux émis en même temps ?
  4. Une bande de 17 pirates s'est emparée d'un butin composé de pièces d'or d'égale valeur. Ils décident de se les partager également et de donner le reste au cuisinier chinois. Celui-ci recevrait alors trois pièces. Mais les pirates se querellent et six d'entre eux sont tués. Le cuisinier recevrait alors quatre pièces. Dans un naufrage ultérieur, seuls le butin, six pirates et le cuisinier sont sauvés et le partage laisserait cinq pièces d'or à ce dernier. Quelle est alors la fortune minimale que peut espérer le cuisinier quand il décide d'empoisonner le reste des pirates?
Indication
Corrigé
Exercice 22 - Coefficients binomiaux [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
  1. Soit $n\geq 1$. Montrer que $(n+1)|\dbinom{2n}{n}$.
  2. Soit $p\geq 2$ premier. Montrer que $p|\dbinom{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]$.
  4. (Plus difficile). Déduire de 2. que, pour tout $N\in\mathbb N^*$, pour tout $j\in\mathbb N^*$, pour tous $(x_1,\dots,x_N)\in\mathbb Z^N$, on a $$\left(\sum_{i=1}^N x_i\right)^{p^j}\equiv \sum_{i=1}^N x_i^{p^j}\ [p].$$
Indication
Corrigé
Exercice 23 - Méthodes de codage basées sur les congruences [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
On note $\mathcal A=\{A,B,C,\dots,Z\}$ l'alphabet, $\mathcal E=\{0,1,2,\dots,25\}$ l'ensemble des 26 premiers entiers naturels, et $g$ la bijection naturelle de $\mathcal A$ sur $\mathcal E$ consistant à numéroter les lettres : $$g(A)=0,\ g(B)=1,\ g(C)=2,\dots, g(Z)=25.$$
  1. Pour tout entier $x$ de $\mathcal E$, on note $f(x)$ le reste de la division euclidienne de $35x$ par $26$.
    1. Montrer que l'on définit ainsi une bijection de $\mathcal E$ sur $\mathcal E$.
    2. On convient de coder un mot quelconque de la façon suivante : on remplace chaque lettre $\alpha$ du mot par la lettre $\beta$ dont le numéro $g(\beta)$ est tel que $g(\beta)=f(x)$, où $x=g(\alpha)$. Comment se code le mot OUI? Montrer que cette méthode de codage est sans ambigüité (deux mots sont distincts ont des codages différents). Quel est le mot dont la codage est $NWN$?
    3. On veut généraliser en remplaçant $35 x$ par $ax+b$, avec $a$ et $b$ entiers naturels et $a\neq 0$. Quelle(s) hypothèse(s) doit-on faire sur $a$ et $b$ pour que la même méthode s'applique?
  2. Pour tout couple d'entiers $(x,y)$ de $\mathcal E\times\mathcal E$, on note $f(x,y)$ et $h(x,y)$ les uniques entiers de $\mathcal E$ tels que $$f(x,y)\equiv 5x+17y\ [26]\textrm{ et }h(x,y)\equiv 4x+15y\ [26].$$
    1. Justifier que l'application $f\times h$ est une bijection de $\mathcal E\times\mathcal E$ sur $\mathcal E\times\mathcal E$.
    2. On convient de coder tout mot contenant un nombre \emph{pair} de lettres de la façon suivante : en partant de la gauche vers la droite, on remplace chaque couple de lettres successives $(\alpha,\beta)$ par le couple $(\gamma,\delta)$ dont les numéros $s=g(\gamma)$, $t=g(\delta)$ sont donnés par $$s=f(x,y)\textrm{ et }t=h(x,y),\textrm{ où }x=g(\alpha)\textrm{ et }y=g(\beta)\textrm{ sont les numéros de $\alpha$ et $\beta$}.$$ Comment se code le mot ENFANT? Le codage d'une lettre dépend-il de la place de cette lettre dans le mot? Démontrer que le principe de codage est sans ambigüité, et que tout mot d'un nombre pair de lettres est le codage d'un et d'un seul mot. Quel est le mot dont le codage est XMEO?
    3. On voudrait généraliser cette méthode de codage à un alphabet comprenant $m$ lettres, en considérant les fonctions $$f(x,y)\equiv ax+by\ [m]\textrm{ et }h(x,y)\equiv cx+dy\ [m],$$ avec $a,b,c,d$ des entiers naturels. Donner une condition sur $a,b,c,d$ et $m$ assurant que la méthode de codage fonctionne encore.
Indication
Corrigé
Exercice 24 - Équations du second degré [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Résoudre, dans $\mathbb Z^2$, les équations diophantiennes suivantes :
  1. $xy=2x+3y$.
  2. $x^2-y^2-x+3y=30$.
  3. $x^2-5y^2=3$.
Indication
Corrigé