$$\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

Math sup : arithmétique sur les entiers relatifs

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 - 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 4 - 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 5 - 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 6 - 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 7 - 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é
pgcd
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 9 - 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 10 - 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é
Enoncé
  1. Démontrer que si deux entiers relatifs sont premiers entre eux, leur somme et leur produit sont premiers entre eux. La réciproque est-elle vraie?
  2. Démontrer que l'on ne change pas le pgcd de deux entiers en multipliant l'un d'entre eux par un entier premier avec l'autre.
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é
Exercice 13 - Le magicien des mathématiques [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Bonjour, je suis le magicien des mathématiques. Je vais deviner votre date de naissance.
Prenez votre jour de naissance. Multipliez le par 31.
Prenez votre mois de naissance. Multiplier le par 12.
Ajoutez ces deux nombres. Combien trouvez-vous? 811 vous me dites?
Et bien vous êtes né un 25 mars!
En plus, c'est vrai. Mais comment a-t-il fait?
Indication
Corrigé
Exercice 14 - 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 15 - 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é
Enoncé
  1. Résoudre le système $$\left\{ \begin{array}{rcl} x\wedge y&=&18\\ x\vee y&=&540 \end{array}\right.$$ avec $(x,y)\in\mathbb N^2$.
  2. Généralisation : trouver une condition nécessaire et suffisante sur $d$ et $m$ pour qu'il existe $(x,y)\in\mathbb N^2$ tels que $x\wedge y=d$ et $x\vee y=m$.
Indication
Corrigé
Exercice 17 - É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é
Exercice 19 - Irrationalité de $\sqrt 2$ [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Le but de cet exercice est de démontrer que $\sqrt 2$ est irrationnel en utilisant l'algorithme d'Euclide. On raisonne par l'absurde et on suppose qu'il existe deux entiers strictement positifs $a$ et $b$ tels que $\sqrt 2=a/b$. On pose $c=\sqrt 2+1$.
  1. Vérifier que $a=b+\frac bc$, puis que $c=2+\frac 1c$.
  2. Démontrer que $\frac bc$ est un entier, et qu'il est égal au reste $r_1$ de la division euclidienne de $a$ par $b$. Quel est le quotient $q_1$ de cette division?
  3. Montrer que dans la division euclidienne de $b$ par $r_1$, le quotient est $q_2=2$ et le reste est $r_2=\frac{r_1}c$.
  4. Soit $n$ un entier supérieur ou égal à 2. Démontrer que l'algorithme d'Euclide appliqué au couple $(a,b)$ comporte au moins $n$ étapes, que le $n$-ième quotient est $q_n=2$, et que le $n$-ième reste est $r_n=\frac{r_{n-1}}c$.
  5. Conclure.
Indication
Corrigé
Nombres premiers
Enoncé
  1. Montrer qu'un entier naturel qui est à la fois un carré et un cube est aussi le carré d'un cube!
  2. Généralisation : soient $a,b,n,m$ des entiers naturels avec $n\wedge m=1$ et $a^n=b^m$. Montrer qu'il existe un entier $c$ tel que $a=c^m$ et $b=c^n$.
Indication
Corrigé
Exercice 21 - 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é
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 23 - Application au calcul de pgcd [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soient $a,b,c\in\mathbb Z^*$ 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 24 - 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$ est $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 26 - 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 27 - Une version faible du théorème de la progression arithmétique [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Démontrer qu'il existe une infinité de nombres premiers de la forme $4k+3$.
Indication
Corrigé
Exercice 28 - 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 29 - Intervalles sans nombres premiers [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $q$ un entier. Trouver un intervalle de longueur $q$ ne contenant pas de nombres premiers.
Indication
Corrigé
Exercice 30 - 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é
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 32 - 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é
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 37 - 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 38 - 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 39 - 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é