Arithmétique et problèmes de codage : cours Tle S

Introduction :

Ce premier cours de spécialité concerne l’arithmétique et les problèmes de codage.

Nous commencerons par quelques rappels. Ils porteront sur les notations des ensembles de nombre, ainsi que sur le raisonnement par récurrence, une nouvelle notion d’arithmétique qui est abordée dans le programme général de terminale. En deuxième partie, nous verrons la fonction partie entière qui nous amènera à la divisibilité dans $\mathbb Z$ avec la division euclidienne.

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

Métaphore de l’échelle pour la 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.

Représentation graphique de la fonction partie entière

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.

Cours : Arithmétique et problèmes de codage

Rappels sur la récurrence

Les ensembles de nombres

Raisonnement par récurrence

Fonction partie entière

Divisibilité dans ​Z\mathbb ZZ

Définitions et propriétés

Division euclidienne

Problèmes de codage

Contenus encyclopédiques liés : Idéal pour approfondir tes connaissances !

Divisibilité dans $\mathbb Z$