Capes : arithmétique

Déterminer, suivant les puissances de $n\in\mathbb N$, le reste de la division euclidienne de $2^n$ par $5$.
Quel est le reste de la division par 5 de $1357^{2013}$?

Exercice 2

- La preuve par neuf [Signaler une erreur] [Ajouter à ma feuille d'exos]

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]$.

Exercice 3

- Pile de livres [Signaler une erreur] [Ajouter à ma feuille d'exos]

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?

Exercice 4

- Algorithme pour compter le nombre de nombres premiers inférieurs à un entier $n$ [Signaler une erreur] [Ajouter à ma feuille d'exos]

É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.
Écrire une fonction $\textrm{estpremier}(p)$ d'argument un entier naturel $p$, renvoyant $1$ si $p$ est premier, et renvoyant $0$ sinon.
Écrire une fonction $\phi(n)$ d'argument un entier naturel $n$ et renvoyant le nombre de nombres premiers inférieurs ou égaux à $n$.

Exercice 5

- Inversibles de $\mathbb Z/n\mathbb Z$. [Signaler une erreur] [Ajouter à ma feuille d'exos]

Est-ce que $\overline{18}$ est inversible dans $\mathbb Z/49\mathbb Z$? Si oui, quel est son inverse?
Est-ce que $\overline{42}$ est inversible dans $\mathbb Z/135\mathbb Z$? Si oui, quel est son inverse?

Exercice 6

- Points à coordonnées entières sur une droite rationnelle [Signaler une erreur] [Ajouter à ma feuille d'exos]

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.

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$.
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$.
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?

Exercice 7

- Un code correcteur d'erreurs : le numéro INSEE [Signaler une erreur] [Ajouter à ma feuille d'exos]

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

Vérifier la clé de votre numéro INSEE.
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.
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.
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.
Justifier l'utilité de la clé de contrôle à la fin du numéro INSEE. Quels autres nombres que 97 aurait-on pu choisir?

Exercice 8

- Méthodes de codage basées sur les congruences [Signaler une erreur] [Ajouter à ma feuille d'exos]

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

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?
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 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.

1. Il suffit de remarquer que 35 est inversible modulo 26. En effet, il est premier avec 26, et l'utilisation de l'algorithme d'Euclide conduit à la relation $$1=3\times 35-4\times 26.$$ Son inverse modulo 26 est donc $3$, et pour tout $a$ dans $\mathcal E$, l'équation $f(x)=a$ a pour seule solution le nombre de $\mathcal E$ congru à $3a$ modulo 26. En effet, si $35x\equiv a\ [26]$, alors $3\times 35 x\equiv 3a\ [26]$ et donc $x\equiv 3a\ [26]$.
2. Le principe est le suivant. On remplace une lettre par le nombre correspondant. On code ce nombre en utilisant $f$. On transcrit le nombre obtenu par la lettre correspondante. Ainsi, à $O$ est associé $14$, transformé par $f$ en $22$, qui donne $W$. De même, $U$ est transformé en 20, lui-même transformé en 24, à qui est associé $Y$, et $I$ est transformé en $U$. Ainsi, le mot OUI se code $WYU$. Pour prouver que le codage est sans ambigüité, il suffit de prouver que l'application qui à une lettre associe son codage est injective. Mais cette application s'écrit $g^{-1}\circ f\circ g$. C'est une composée d'applications bijectives, elle est elle-même bijecive, donc injective.
  Pour trouver le mot dont le codage est $NWN$, il faut inverser l'application précédente. Mais on a déjà observé à la première question qu'on inversait $f$ en considérant l'application qui à $x$ de $\mathcal E$ associe le reste dans la division euclidienne de $3x$ par 26. En procédant comme ci-dessus, on trouve que le mot initial est NON.
3. Tout fonctionne exactement de la même façon, pourvu que l'application qui à $x$ associe le reste de $ax+b$ soit inversible modulo 26. Ceci est possible si et seulement si $a$ est inversible modulo 26, c'est-à-dire si et seulement si $a$ est premier avec 26.
1. Puisque $\mathcal E\times\mathcal E$ est un ensemble fini, il suffit de prouver que $f\times h$ est une injection pour prouver que c'est une bijection. Autrement dit, pour tous couples $(x,y)$ et $(x',y')$ de $\mathcal E\times\mathcal E$ vérifiant $$\left\{ \begin{array}{rcl} 5x+17y&\equiv&5x'+17y'\ [26]\\ 4x+15y&\equiv&4x'+15y'\ [26] \end{array}\right.$$ on veut prouver que $x=x'$ et $y=y'$. Mais, si on fait $4(L1)-5(L2)$, on trouve : $$-7y=-7y'\ [26].$$ De même, si on fait $15(L1)-17(L2)$, on trouve $$7x\equiv7x'\ [26].$$ Comme $7$ est inversible modulo 26 (il est premier avec 26), ceci entraîne que $x=x'$ et $y=y'$, et donc que $f\times h$ est injective.
2. On découpe le mot par couple de deux lettres. On commence par coder EN. On a $x=4$ et $y=13$, d'où $f(x,y)=7$ et $h(x,y)=3$. Ainsi, EN se code en HD. De même, FA se code en ZU et NT se code en YZ. Le codage du mot ENFANT est donc HDZUYZ. Le codage d'une lettre dépend de sa place dans le mot, puisqu'on code des binômes de deux lettres ensemble.
  Pour prouver que le codage est sans ambigüité et que tout mot d'un nombre pair de lettres est le codage d'un mot, il suffit de vérifier que le codage de deux lettres est sans ambigüité et que tout mot de deux lettres est le codage d'un autre mot de deux lettres. Mais c'est exactement le sens de la question précédente.
  Pour trouver le mot dont le codage est XMEO, il faut déjà inverser l'application $f\times g$. Autrement dit, étant donné $(a,b)\in\mathcal E\times\mathcal E$, on veut trouver $(x,y)\in\mathcal E\times\mathcal E$ tel que $$\left\{ \begin{array}{rcl} 5x+17y&\equiv&a\ [26]\\ 4x+15y&\equiv&b\ [26] \end{array}\right.$$ En effectuant les mêmes opérations que ci-dessus, on trouve $$-7y\equiv 4a-5b\ [26] \textrm{ et }7x=15a-17b\ [26].$$ On inverse maintenant $-7$ (c'est-à-dire encore 19) modulo 26, et l'algorithme d'Euclide donne $$1=-8\times 26+11\times 19.$$ Ainsi, on obtient $$y\equiv 44a-55b\equiv 18a-3b\equiv 18a+23b\ [26].$$ On fait de même avec 7, dont un inverse est 15, et on trouve $$x\equiv 17a+5b\ [26].$$ On décode ensuite par bloc de $2$. Pour XM, on a $a=23$, $b=12$, et donc $x=9$, $y=14$, on trouve JO, et pour EO, on trouve IE. Le mot décodé est donc JOIE.
3. On veut trouver une condition portant sur $a,b,c,d$ et $m$ pour que le système $$\left\{ \begin{array}{rcl} ax+by&\equiv&s\ [m]\\ cx+dy&\equiv&t\ [m] \end{array}\right.$$ admette toujours au plus une solution. Mais, si on raisonne comme ci-dessus, ce système entraîne $$(ad-bc)x\equiv bs-dt\ [m]\textrm{ et }(ad-bc)y\equiv at-cs\ [m].$$ On voit que si $ad-bc$ est inversible modulo $m$, autrement dit si $ad-bc$ et $m$ sont premiers entre eux, alors on a toujours au plus une solution (et donc en fait exactement une solution, car on travaille avec une application allant d'un ensemble fini dans lui-même). Donc si $ad-bc$ est premier avec $m$, cette méthode de codage continue de fonctionner.

Exercice 9

- Équations du second degré [Signaler une erreur] [Ajouter à ma feuille d'exos]

Résoudre

$x^2+x+\overline 7=\overline 0$ dans $\mathbb Z/13\mathbb Z$.
$x^2-\overline 4x+\overline 3=\overline 0$ dans $\mathbb Z/12\mathbb Z$.

Exercice 10

- Indicateur d'Euler [Signaler une erreur] [Ajouter à ma feuille d'exos]

Pour $n\geq 1$ un entier, on définit l'indicateur d'Euler de $n$ par : $$\phi(n)=\textrm{card}\{1\leq k\leq n;\ k\textrm{ est premier avec }n\}.$$

Calculer $\phi(p)$ lorsque $p$ est un nombre premier.
Calculer $\phi(p^\alpha)$, où $p$ est premier et $\alpha\geq 1$.
Que signifie $\phi(n)$ pour l'anneau $\mathbb Z/n\mathbb Z$?
En déduire que si $n\wedge m=1$, alors $\phi(nm)=\phi(n)\phi(m)$.
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).$