Cours : Arithmétique et problèmes de codage

Rappels sur la récurrence

Les ensembles de nombres

À retenir

Le plus petit ensemble de nombres est l’ensemble des entiers naturels que l’on note $\mathbb N$. Cet ensemble contient les entiers nuls et positifs : $\mathbb {N}=\lbrace0\ ; 1\ ; 2\ ; …\rbrace$

L’ensemble des entiers naturels privés de zéro, aussi appelé l’ensemble des entiers naturels non nuls, est noté $\mathbb N^*$.

Cet ensemble contient les entiers strictement positifs : $\mathbb N^*=\lbrace 1\ ; 2\ ; …\rbrace$

L’ensemble des entiers relatifs est noté $\mathbb Z$. Il contient tous les entiers, c’est-à-dire les entiers positifs, négatifs et zéro : $\mathbb {Z}=\lbrace …\ ; -2\ ; -1\ ; 0\ ; 1\ ; 2\ ; …\rbrace$

L’ensemble des entiers relatifs non nuls se note $\mathbb Z^*$ . Cet ensemble contient tous les entiers négatifs et positifs mais est privé de zéro : $\mathbb {Z}=\lbrace …\ ; -2\ ; -1\ ; 1\ ; 2\ ; …\rbrace$

Les ensembles de nombres sont inclus les uns dans les autres : ici, l’ensemble des entiers naturels est inclus dans l’ensemble des entiers relatifs : $\mathbb N \subset\mathbb Z$

Astuce

Il existe une autre notation pour signifier qu’un ensemble est privé de zéro ou d’une autre valeur. $$\begin{aligned}\begin {aligned}\mathbb N^*&=\mathbb N\backslash{0}\\ \mathbb Z^*&=\mathbb Z\backslash{0}\end {aligned} \end{aligned}$$

Raisonnement par récurrence

Le principe de récurrence est souvent expliqué à l’aide de la métaphore de l’échelle : si on peut se placer d’abord sur un barreau d’une échelle, et si on peut ensuite passer d’un barreau quelconque à son suivant, alors on peut gravir tous les barreaux de cette échelle.

Méthode : raisonnement par récurrence

Soit :

• $P$ une proposition
• $n$ et $n_0\in \mathbb N$
• $n\geq n_0$

Pour démontrer que $P(n)$ est vraie :

• initialisation : on vérifie si $P(n_0)$ est vraie. Lorsqu’on y est parvenu, on dit qu’on a initialisé la récurrence ;
• hérédité : on suppose que $P(n)$ est vraie pour un entier $n$ et on cherche à prouver que $P(n+1)$ est vraie. Lorsqu’on a réussi, on a prouvé que $P(n)$ est héréditaire.

Attention

L’hérédité n’est à prouver que pour un entier naturel. Si on écrit « on suppose que $P(n)$ est vraie pour un entier $n$ quelconque », on admet dès cette étape que la relation est vraie pour tous les entiers, ce qui n’aurait pas de sens !

• Conclusion $P(n_0)$ est vraie $P(n+1)$ est vraie Donc $P(n)$ est vraie pour tout $n$.

Exemple

Démontrer que $n(n+1)(2n+1)$ est divisible par 3 pour tout entier naturel $n$.

• Initialisation :

On appelle $P(n)$, la proposition : $n(n+1)(2n+1)$ est divisible par $3$ pour tout entier naturel $n$.

Pour $n=0$, on a $0(0+1)(2\times0+1)=0$

Or 0 est divisible par 3. Donc $P(n)$ est vraie pour $n=0$.

• Hérédité :

Supposons que $P(n)$ soit vraie à un certain rang $k$.

Cela revient à dire que $k(k+1)(2k+1)$ est divisible par 3.

Montrons que la proposition est vraie au rang suivant $P(k+1)$, c’est-à-dire que

$(k+1)(k+2)(2k+3)$ est divisible par $3$.

Commençons par réécrire l’hypothèse de récurrence à l’aide d’un peu de calcul :

$$\begin{array}{rl} &k(k+1)(2k+1)\\ =&(k^2+k)(2k+1)\\ =&2k^3+3k^2+k \end{array}$$

Réécrivons à présent l’expression obtenue à $P(k+1)$ pour retrouver $k$ et isoler un facteur 3 :

$$\begin{array}{ll} &(k+1)(k+2)(2k+3)\\ =&(k+1)(2k^2+7k+6)\\ =&2k^3+9k^2+13k+6\\ =&(2k^3+3k^2+k)+(6k^2+12k+6)\\ =&(2k^3+3k^2+k)+3(2k^2+4k+2) \end{array}$$

D’après notre hypothèse de récurrence, $k(k+1)(2k+1)$ est divisible par 3.

Donc il existe un entier $k'$ tel que $\dfrac{k(k+1)(2k+1)}{3}=k'\Leftrightarrow k(k+1)(2k+1)=3k'$ soit $2k^3+3k^2+k=3k'$

On obtient donc :

$$\begin{array}{rl} &(k+1)(k+2)(2k+3)\\ =&(2k^3+3k^2+k)+3(2k^2+4k+2)\\ =&3k'+3(2k^2+4k+2)\\ =&3(k'+2k^2+4k+2) \end{array}$$

Donc $P(n+1)$ est vraie : la proposition est héréditaire.

• Conclusion :

$P(n)$ est vraie pour $n=0$ et $P(n+1)$ est vraie. $P(n)$ est donc héréditaire pour tout entier naturel $n$ positif.

On peut conclure que $n(n+1)(2n+1)$ est divisible par 3 pour tout $n\geq0$.

Fonction partie entière

Définition

Fonction partie entière :

Tout réel peut être encadré par deux entiers relatifs ; on dit que, pour tout réel $x$, il existe un unique entier relatif $n$ tel que $x$ soit compris entre $n$ inclus et $n+1$ exclu : $n\leq x < n+1$

L’entier $n$ est appelé partie entière de $x$ et est noté $\text E(x)$. C’est l’entier relatif directement inférieur au réel $x$.

Exemple

• $\text E(3,65)=3$ car $3\leq 3,65 < 4$
• $\text E(-2,9)=-3$ car $-3\leq -2,9 < -2$
• $\text E(6)=6$ car $6\leq 6 < 7$

Définition

Représentation graphique de la fonction partie entière :

La représentation graphique de la fonction partie entière est discontinue sur l’ensemble des réels.

Divisibilité dans ​$\mathbb Z$

Définitions et propriétés

Définition

Divisibilité dans ​$\mathbb Z$ :

Soit $a$ et $b$ des entiers relatifs, $b$ étant non nul.

On dit que $b$ est un diviseur de $a$ lorsqu’il existe un entier relatif $k$ tel que $a=k\times b$.

On peut dire aussi que :

• $a$ est divisible par $b$
• $b$ est un diviseur de $a$
• $a$ est un multiple de $b$
• $b$ divise $a$

À retenir

• Les diviseurs de $1$ sont $-1$ et $1$ .
• $1$ et $-1$ sont des diviseurs de n’importe quel entier relatif.
• $0$ est multiple de n’importe quel entier relatif.
• Les entiers relatifs pairs sont les multiples de $2$, c’est-à-dire ceux qui s’écrivent $2k$ avec $k\in\mathbb Z$.
• Les entiers relatifs impairs sont les entiers qui ne sont pas multiples de 2, c’est-à-dire ceux qui s’écrivent $2k+1$ avec $k\in\mathbb Z$ .

Propriété

Transitivité:

Soit $a$, $b$ et $c$ des entiers relatifs.

Si $b$ divise $a$ et si $c$ divise $b$, alors $c$ divise $a$.

Démonstration

Comme $b$ divise $a$, il existe un entier $k$ tel que $a=b\times k$

Comme $c$ divise $b$, il existe un entier $k'$ tel que $b=c\times k'$

Ainsi,
$\begin{aligned}a&=b\times k\\&=(c\times k')\times k\\&=c\times (k'\times k)\\&=c\times K\end{aligned}$
où $K=kk'$ donc $c$ divise $a$.

Propriété

Combinaisons linéaires entières

Soit $a$, $b$ et $c$ des entiers relatifs.

Si $c$ divise $a$ et $b$, alors pour tous les entiers relatifs $n$ et $n'$, $c$ divise $n\times a+n'\times b$.

À retenir

Autrement dit, si $c$ divise $a$ et $b$, alors il divise toutes les combinaisons linéaires entières de $a$ et $b$​.

Démonstration

Comme $c$ divise $a$ et $b$, il existe deux entiers $k$ et $k'$ tels que $a=k\times c$ et $b=k'\times c$.

Alors :

$\begin{array}{rcl} na+n'b&=&n(kc)+n'(k'c)&\\ &=&(nk+n'k')c&\\ &=&Kc&\end{array}$

où $K=nk+n'k'$

Ainsi $c$ divise $n\times a+n'\times b$.

Division euclidienne

Définition

Division euclidienne :

Soit $a$ et $b$ deux entiers naturels avec $b$ non nul. Il existe un unique couple $(q\ ;r)$ d’entiers naturels tel que :

$a=bq+r$ et $0\leq r < b$

L’entier naturel $a$ est le dividende et $b$ est le diviseur.

L’entier naturel $q$ s’appelle le quotient et $r$ s’appelle le reste de la division euclidienne de $a$ par $b$.

Exemple

• La division euclidienne de 343 par 12 : $343=12\times 28+7$ et $0\leq 7 < 12$
• La division euclidienne de 1526 par 11 : $1526=11\times 138+8$ et $0\leq 8 < 11$

Propriété

Soit $a$ et $b$ deux entiers relatifs avec $b$ non nul. Il existe un unique couple $(q\ ;r)$ avec $q\in \mathbb Z$ et $r\in \mathbb N$, tels que : $a=bq+r$ et $0\leq r<\big|b\big|$

Pour simplifier, la différence entre la division euclidienne dans $\mathbb Z$ et la division euclidienne dans $\mathbb N$, est que dans l’ensemble des entiers relatifs, le $a$ et le $b$ peuvent être négatifs, ce qui implique d’avoir la possibilité d’avoir un quotient négatif. Par contre le reste est toujours positif.

Exemple

• La division euclidienne de $431$ par $-17 :$ $431=-17\times (-25)+6$ avec $0\leq 6<\big|-17\big|$
• La division euclidienne de $-121$ par $-9:$ $-121=-9\times 14+5$ avec $0\leq 5 < \big|-9\big|$

Problèmes de codage

On se sert par exemple de la notion de division euclidienne lorsque qu’on nous attribue notre numéro de sécurité sociale. Ce numéro est constitué de 15 chiffres :

• le premier chiffre est $1$ s’il s’agit d’un homme, $2$ s’il s’agit d’une femme ;
• les deux chiffres suivants sont les deux derniers chiffres de l’année de naissance ;
• viennent ensuite les deux chiffres du mois de naissance ;
• les cinq chiffres suivants désignent le lieu de naissance, département et commune ;
• les trois chiffres d’après désignent le numéro d’inscription sur le registre d’état civil ;
• les deux derniers chiffres enfin résultent d’un calcul.

Voici ce calcul :

Il faut faire la division euclidienne des 13 premiers chiffres par 97. Ensuite on calcule la différence entre 97 et le reste obtenu. On a ainsi les deux derniers chiffres.

Le calcul du numéro de sécurité sociale fait donc appel à la division euclidienne.