Devoir surveillé — Arithmétique dans l'ensemble des entiers relatifs

Soit $b⩾2$ un entier. On admet le théorème de la numération en base $b$ : pour tout $n\in {\mathbb{N}}^{\ast }$, il existe un unique entier $k⩾1$ et un unique $k$-uplet de chiffres $(a_{k-1},\dots ,a_1,a_0)$, éléments de $\{0,1,\dots ,b-1\}$ avec $a_{k-1}\mathrm{\ne }0$, tels que

$$n=\sum _{i=0}^{k-1}{a}_i{b}^i\mathrm{.}$$

On note alors $n={\overline{a_{k-1}\cdots a_1{a}_0}}^{(b)}$, et l'on dit que $n$ s'écrit avec $k$ chiffres en base $b$. On admet aussi la variante à longueur imposée : si $0⩽n<b^k$, il existe un unique $k$-uplet $(a_{k-1},\dots ,a_0)$ de chiffres, cette fois sans condition sur $a_{k-1}$, vérifiant l'égalité ci-dessus.

1. (0,75 pt) Écrire $2026$ dans les deux bases suivantes, en présentant la suite des divisions euclidiennes effectuées.

2. (0,5 pt) Déterminer l'entier $b⩾2$ tel que ${\overline{213}}^{(b)}=81$.

3. (0,75 pt) Soient $n\in {\mathbb{N}}^{\ast }$ et $k\in {\mathbb{N}}^{\ast }$. Démontrer que $n$ s'écrit avec exactement $k$ chiffres en base $b$ si et seulement si $b^{k-1}⩽n<b^k$. Contrôler alors le nombre de chiffres obtenus à la question 1.

4. On dispose d'une balance à deux plateaux et de quatre masses, que l'on peut poser indifféremment sur l'un ou l'autre plateau. On souhaite pouvoir peser tout objet dont la masse est un nombre entier de grammes compris entre $1$ et $40$.

a. (0,75 pt) Démontrer que tout entier $m$ tel que $-40⩽m⩽40$ s'écrit de manière unique

$$m={\epsilon }_0+3{\epsilon }_1+9{\epsilon }_2+27{\epsilon }_3,{\epsilon }_i\in \{-1,0,1\}\mathrm{.}$$

On pourra appliquer le théorème admis à l'entier $m+40$ en base $3$, après avoir remarqué que $40=1+3+9+27$.

b. (0,25 pt) En déduire les quatre masses à choisir, et décrire la pesée d'un objet de $22$ grammes.

Dans tout l'exercice, $a$ et $b$ désignent deux entiers tels que $a⩾2$, $b⩾2$ et $a\wedge b=1$. On dit qu'un entier $n\in \mathbb{N}$ est accessible lorsqu'il existe $(x,y)\in {\mathbb{N}}^2$ tel que

$$n=ax+by\mathrm{.}$$

Attention : les coefficients $x$ et $y$ sont ici astreints à être positifs ou nuls, ce qui change tout par rapport à une équation diophantienne ordinaire.

1. (0,5 pt) Dans cette question seulement, $a=3$ et $b=5$. Dresser la liste des entiers accessibles compris entre $0$ et $12$, puis celle des entiers inaccessibles de cet intervalle. Quel est le plus grand entier inaccessible que l'on obtient ?

2. (0,75 pt) Soit $n\in \mathbb{Z}$. Démontrer qu'il existe un unique entier $x_n$ tel que

$$0⩽x_n⩽b-1\text{et}b\mid n-a{x}_n\mathrm{.}$$

On précisera où l'hypothèse $a\wedge b=1$ intervient.

Dans les questions 3., 4. et 5., on note $x_n$ l'entier fourni par la question 2.

3. (0,75 pt) Démontrer que $n$ est accessible si et seulement si $n-a{x}_n⩾0$.

4. (0,5 pt) Démontrer que $x_{ab-a-b}=b-1$, puis que l'entier $ab-a-b$ n'est pas accessible.

5. (0,5 pt) Démontrer que tout entier $n>ab-a-b$ est accessible. Application : déterminer le plus grand entier inaccessible pour $a=7$ et $b=11$, et écrire $60$ sous la forme $7x+11y$ avec $(x,y)\in {\mathbb{N}}^2$.

On s'intéresse aux couples formés d'une puissance de $2$ et d'une puissance de $3$ qui diffèrent de $1$. On se limite au cas où c'est la puissance de $3$ qui est la plus grande, c'est-à-dire à l'équation

$$(E):3^x-2^y=1,(x,y)\in ({\mathbb{N}}^{\ast }{)}^2\mathrm{.}$$

1. (0,5 pt) Lemme. Soient $s$ et $t$ deux entiers naturels tels que $2^t-2^s=2$. Démontrer que $s=1$ et $t=2$.

2. (0,25 pt) Vérifier que $(1,1)$ et $(2,3)$ sont solutions de $(E)$.

3. (0,75 pt) Soit $(x,y)$ une solution de $(E)$ telle que $y⩾2$. Démontrer que $x$ est pair.

4. (1 pt) Soit $(x,y)$ une solution de $(E)$ telle que $y⩾2$. On écrit $x=2m$ avec $m\in {\mathbb{N}}^{\ast }$. Démontrer que $3^m-1$ et $3^m+1$ sont deux puissances de $2$, puis déterminer $m$. Conclure en donnant l'ensemble des solutions de $(E)$.

5. (0,5 pt) Résoudre dans $({\mathbb{N}}^{\ast }{)}^2$ l'équation $x^2=2^y+1$.

On note $\mathcal{P}$ l'ensemble des nombres premiers et, pour $p\in \mathcal{P}$ et $n\in {\mathbb{N}}^{\ast }$, $v_p(n)$ la valuation $p$-adique de $n$. On utilisera librement les résultats du cours suivants : $v_p(mn)=v_p(m)+v_p(n)$ ; deux entiers de ${\mathbb{N}}^{\ast }$ ayant les mêmes valuations $p$-adiques pour tout $p\in \mathcal{P}$ sont égaux ; un entier de ${\mathbb{N}}^{\ast }$ est un carré parfait si et seulement si toutes ses valuations $p$-adiques sont paires ; pour $d,n\in {\mathbb{N}}^{\ast }$, $d\mid n$ si et seulement si $v_p(d)⩽v_p(n)$ pour tout $p\in \mathcal{P}$ ; enfin $v_p(m\wedge n)=\min (v_p(m),v_p(n))$ et $v_p(m\vee n)=\max (v_p(m),v_p(n))$.

Un entier $c\in {\mathbb{N}}^{\ast }$ est dit sans facteur carré lorsque $v_p(c)⩽1$ pour tout $p\in \mathcal{P}$, autrement dit lorsqu'aucun carré d'entier supérieur ou égal à $2$ ne divise $c$.

1. (0,5 pt) Donner la liste des entiers sans facteur carré compris entre $1$ et $20$. Décomposer $720$ et $2646$ en produits de facteurs premiers, et dire si ces deux entiers sont sans facteur carré.

2. (1,25 pt) Démontrer que tout $n\in {\mathbb{N}}^{\ast }$ s'écrit de manière unique

$$n=a^{2}b,a\in {\mathbb{N}}^{\ast },b\in {\mathbb{N}}^{\ast }\text{ sans facteur carr}\acute{\text{e}}\mathrm{.}$$

L'entier $b$ est appelé la partie sans facteur carré de $n$.

3. (0,5 pt) Expliciter cette écriture pour $n=720$, puis pour $n=2646$.

4. (1 pt) Soient $m$ et $n$ deux éléments de ${\mathbb{N}}^{\ast }$, de parties sans facteur carré respectives $b$ et $b^{\mathrm{\prime }}$. Démontrer que la partie sans facteur carré de $mn$ vaut

$$\frac{b\vee b^{\mathrm{\prime }}}{b\wedge b^{\mathrm{\prime }}}\mathrm{.}$$

En déduire que $mn$ est un carré parfait si et seulement si $b=b^{\mathrm{\prime }}$.

5. (0,75 pt) Soit $n\in {\mathbb{N}}^{\ast }$, écrit $n=a^{2}b$ comme à la question 2. Démontrer que les diviseurs de $n$ qui sont des carrés parfaits sont exactement les entiers $k^2$ où $k$ décrit l'ensemble des diviseurs positifs de $a$. Combien $2646$ possède-t-il de diviseurs qui sont des carrés parfaits ? Les expliciter.

Ce problème construit et fait fonctionner le système de chiffrement RSA, publié en 1977 et encore utilisé aujourd'hui pour sécuriser les communications. Le principe est le suivant. Alice choisit deux nombres premiers distincts $p$ et $q$, calcule $n=pq$, puis un exposant $e$ premier avec $(p-1)(q-1)$. Elle publie le couple $(n,e)$, sa clé publique, et garde secrets $p$, $q$ et un exposant $d$ que la partie A apprend à construire. Pour lui envoyer un message, codé par un entier $m$ tel que $0⩽m<n$, Bob calcule et transmet le reste $c$ de $m^e$ dans la division euclidienne par $n$. Alice, elle, retrouve $m$ en calculant le reste de $c^d$ modulo $n$. Toute la question est de comprendre pourquoi cela fonctionne, et pourquoi un tiers ne peut pas en faire autant.

Dans les parties A et C, on prend $p=7$, $q=13$, donc $n=91$, et $e=5$. On rappelle le corollaire du lemme de Gauss vu en cours, utilisable librement : si deux entiers premiers entre eux divisent tous les deux un entier $A$, alors leur produit divise $A$.

Partie A — Fabrication de la clé privée

A.1. (0,75 pt) Calculer $(p-1)(q-1)$. Appliquer l'algorithme d'Euclide à ce nombre et à $e=5$, en présentant toutes les divisions, puis remonter les calculs pour déterminer un couple $(d,k)\in {\mathbb{Z}}^2$ tel que

$$ed-k(p-1)(q-1)=1,1⩽d⩽(p-1)(q-1)-1.$$

A.2. (0,5 pt) Vérifier que $ed-1$ est un multiple de $p-1$ et un multiple de $q-1$, en donnant les deux quotients.

Partie B — Le théorème de déchiffrement

Dans toute cette partie, $p$ et $q$ désignent deux nombres premiers distincts, $n=pq$, et $e$, $d$ deux entiers naturels non nuls tels que

$$ed\equiv 1[(p-1)(q-1)]\mathrm{.}$$

B.1. (0,25 pt) Justifier que $p-1$ divise $ed-1$ et que $q-1$ divise $ed-1$.

B.2. (1 pt) Démontrer que, pour tout $a\in \mathbb{Z}$, $a^{ed}\equiv a[p]$. On distinguera le cas où $p$ divise $a$ et celui où il ne le divise pas.

B.3. (0,25 pt) Énoncer le résultat analogue modulo $q$ et justifier qu'il s'obtient sans nouveau calcul.

B.4. (1 pt) En déduire que $a^{ed}\equiv a[n]$ pour tout $a\in \mathbb{Z}$. On justifiera soigneusement l'hypothèse de primalité entre eux qui autorise le passage de $p$ et $q$ à $n$.

Partie C — Chiffrer, déchiffrer, attaquer

On revient à $p=7$, $q=13$, $n=91$, $e=5$ et à l'exposant $d$ de la partie A.

C.1. (0,5 pt) Bob veut transmettre le message $m=3$. Calculer le chiffré $c$, reste de $m^e$ dans la division euclidienne par $91$.

C.2. (1,25 pt) Alice déchiffre. Calculer le reste de $c^d$ dans la division euclidienne par $91$, en passant par les congruences modulo $7$ et modulo $13$, et vérifier qu'on retrouve bien $m$. On n'effectuera aucun calcul sur de grands nombres.

C.3. (0,75 pt) Ève intercepte $c$ et connaît la clé publique $(91,5)$. Expliquer comment elle retrouve $m$, et mener effectivement l'attaque. Expliquer ensuite pourquoi cette attaque devient irréalisable lorsque $n$ compte $600$ chiffres.

C.4. (0,75 pt) On suppose maintenant qu'Alice, par imprudence, publie $n$ et $(p-1)(q-1)$ sans publier $p$ ni $q$. Démontrer qu'Ève peut alors retrouver $p$ et $q$, et le faire pour $n=91$ et $(p-1)(q-1)=72$. Que faut-il en conclure sur ce qui doit rester secret ?