Arithmétique et problèmes de codage

Rappels sur la récurrence

Définitions : les ensembles de nombres

• $\mathbb {N}=\lbrace0\ ; 1\ ; 2\ ; …\rbrace$ est l’ensemble des entiers naturels ; c’est le plus petit ensemble de nombres ;
• $\mathbb N^*=\lbrace 1\ ; 2\ ; …\rbrace$

où $\mathbb N^*$ est l’ensemble des entiers naturels privés de zéro ;

• $\mathbb {Z}=\lbrace …\ ; -2\ ; -1\ ; 0\ ; 1\ ; 2\ ; …\rbrace$ est l’ensemble des entiers relatifs ;
• $\mathbb {Z}=\lbrace …\ ; -2\ ; -1\ ; 1\ ; 2\ ; …\rbrace$

où $\mathbb Z^*$ est l’ensemble des entiers relatifs non nuls.

Méthode : raisonnement par récurrence

Pour démontrer par récurrence qu’une proposition $P(n)$ est vraie pour tout entier naturel $n$ supérieur ou égal à un entier naturel $n_0$ fixé, on procède en trois étapes :

• Initialisation : on vérifie si $P(n_0)$ est vraie, c’est-à-dire que la proposition est vraie pour le premier indice $n_0$. On dit qu’on a initialisé la récurrence.
• Hérédité : on suppose que pour un entier $n>n_0$, $P(n)$ est vraie. Sous cette hypothèse, dite de récurrence, on démontre que la proposition $P(n+1)$ est vraie. On a ainsi prouvé que l’hypothèse de récurrence « $P_n$ vraie » est héréditaire.

Attention : cette étape est à faire pour un entier $n$ sinon on admet dès la démonstration ce qu’on veut justement démontrer.

• Conclusion : lorsque les deux premières étapes ont été réalisées, on conclut : par récurrence, la proposition est vraie pour tout entier naturel $n(n > n_0)$.

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 ≤ x < n+1$$

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

La fonction partie entière est discontinue sur l’ensemble des réels.

Divisibilité dans $\mathbb Z$

Définitions : diviseurs et multiples

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$
• Conséquences de cette définition :
• 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é : la transitivité

Soit $a,b$ et $c$ des entiers relatifs. Si $b$ divise $a$ et si $c$ divise $b$, alors $c$ divise $a$.

Démontration :

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

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{aligned}\begin{array}{rclrr} na+n'b&=&n(kc)+n'(k'c)&\\ &=&(nk+n'k')c&\\ &=&Kc& \end{array}\end{aligned}$

Où $K=nk+'k'$

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

Division euclidienne

Définitions : 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$.

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

• Autrement dit, la différence entre la division euclidienne dans et la division euclidienne dans , 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.