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

Capes : arithmétique

Pour réviser
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é
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é
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 4 - 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é
Exercice 5 - Inversibles de $\mathbb Z/n\mathbb Z$. [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
  1. Est-ce que $\overline{18}$ est inversible dans $\mathbb Z/49\mathbb Z$? Si oui, quel est son inverse?
  2. Est-ce que $\overline{42}$ est inversible dans $\mathbb Z/135\mathbb Z$? Si oui, quel est son inverse?
Corrigé
Pour progresser
Exercice 6 - 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é
Exercice 7 - 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é
Exercice 8 - 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 9 - Équations du second degré [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Résoudre
  1. $x^2+x+\overline 7=\overline 0$ dans $\mathbb Z/13\mathbb Z$.
  2. $x^2-\overline 4x+\overline 3=\overline 0$ dans $\mathbb Z/12\mathbb Z$.
Indication
Corrigé
Enoncé
Pour $n\geq 1$ un entier, on définit l'\emph{indicateur d'Euler} de $n$ par : $$\phi(n)=\textrm{card}\{1\leq k\leq n;\ k\textrm{ est premier avec }n\}.$$
  1. Calculer $\phi(p)$ lorsque $p$ est un nombre premier.
  2. Calculer $\phi(p^\alpha)$, où $p$ est premier et $\alpha\geq 1$.
  3. Que signifie $\phi(n)$ pour l'anneau $\mathbb Z/n\mathbb Z$?
  4. En déduire que si $n\wedge m=1$, alors $\phi(nm)=\phi(n)\phi(m)$.
  5. Déduire des questions précédentes une formule pour calculer $\phi(n)$ pour tout entier $n$.
    1. Soit $d$ un diviseur de $n$. On pose $$A_d=\left\{1\leq k\leq n;\ k\wedge n=d\right\}.$$ Quel est le cardinal de $A_d$?
    2. En déduire que $n=\sum_{d|n}\phi(d).$
Indication
Corrigé