Médaille
N°1 pour apprendre & réviser du collège au lycée.

Arithmétique et problèmes de codage

Déjà plus de

1 million

d'inscrits !

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 Z\mathbb Z avec la division euclidienne.

Rappels sur la récurrence

Les ensembles de nombres

bannière à retenir

À retenir

Le plus petit ensemble de nombres est l’ensemble des entiers naturels que l’on note N\mathbb N. Cet ensemble contient les entiers nuls et positifs : N={0 ;1 ;2 ;}\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é N\mathbb N^*.

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

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

L’ensemble des entiers relatifs non nuls se note Z*\mathbb Z^* . Cet ensemble contient tous les entiers négatifs et positifs mais est privé de zéro : Z={ ;2 ;1 ;1 ;2 ;}\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 : NZ\mathbb N \subset\mathbb Z

bannière astuce

Astuce

Il existe une autre notation pour signifier qu’un ensemble est privé de zéro ou d’une autre valeur. N*=N\{0}Z*=Z\{0}\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 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 :

  • PP une proposition
  • nn et n0Nn_0\in \mathbb N
  • nn0n\geq n_0

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

  • initialisation : on vérifie si P(n0)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)P(n) est vraie pour un entier nn et on cherche à prouver que P(n+1)P(n+1) est vraie. Lorsqu’on a réussi, on a prouvé que P(n)P(n) est héréditaire.
bannière attention

Attention

L’hérédité n’est à prouver que pour un entier naturel. Si on écrit « on suppose que P(n)P(n) est vraie pour un entier nn 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(n0)P(n_0) est vraie P(n+1)P(n+1) est vraie Donc P(n)P(n) est vraie pour tout nn.
bannière exemple

Exemple

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

  • Initialisation :

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

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

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

  • Hérédité :

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

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

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

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

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

k(k+1)(2k+1)=(k2+k)(2k+1)=2k3+3k2+k\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)P(k+1) pour retrouver kk et isoler un facteur 3 :

(k+1)(k+2)(2k+3)=(k+1)(2k2+7k+6)=2k3+9k2+13k+6=(2k3+3k2+k)+(6k2+12k+6)=(2k3+3k2+k)+3(2k2+4k+2)\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)k(k+1)(2k+1) est divisible par 3.

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

On obtient donc :

(k+1)(k+2)(2k+3)=(2k3+3k2+k)+3(2k2+4k+2)=3k+3(2k2+4k+2)=3(k+2k2+4k+2)\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)P(n+1) est vraie : la proposition est héréditaire.

  • Conclusion :

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

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

Fonction partie entière

bannière definition

Définition

Fonction partie entière :

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

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

bannière exemple

Exemple

  • E(3,65)=3\text E(3,65)=3 car 33,65<43\leq 3,65 < 4
  • E(2,9)=3\text E(-2,9)=-3 car 32,9<2-3\leq -2,9 < -2
  • E(6)=6\text E(6)=6 car 66<76\leq 6 < 7
bannière definition

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 Représentation graphique de la fonction partie entière

Divisibilité dans ​Z\mathbb Z

Définitions et propriétés

bannière definition

Définition

Divisibilité dans ​Z\mathbb Z :

Soit aa et bb des entiers relatifs, bb étant non nul.

On dit que bb est un diviseur de aa lorsqu’il existe un entier relatif kk tel que a=k×ba=k\times b.

On peut dire aussi que :

  • aa est divisible par bb
  • bb est un diviseur de aa
  • aa est un multiple de bb
  • bb divise aa
bannière à retenir

À retenir

  • Les diviseurs de 11 sont 1-1 et 11 .
  • 11 et 1-1 sont des diviseurs de n’importe quel entier relatif.
  • 00 est multiple de n’importe quel entier relatif.
  • Les entiers relatifs pairs sont les multiples de 22, c’est-à-dire ceux qui s’écrivent 2k2k avec kZk\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+12k+1 avec kZk\in\mathbb Z .
bannière propriete

Propriété

Transitivité:

Soit aa, bb et cc des entiers relatifs.

Si bb divise aa et si cc divise bb, alors cc divise aa.

bannière demonstration

Démonstration

Comme bb divise aa, il existe un entier kk tel que a=b×ka=b\times k

Comme cc divise bb, il existe un entier kk' tel que b=c×kb=c\times k'

Ainsi,
a=b×k=(c×k)×k=c×(k×k)=c×K\begin{aligned}a&=b\times k\&=(c\times k')\times k\&=c\times (k'\times k)\&=c\times K\end{aligned}
K=kkK=kk' donc cc divise aa.

bannière propriete

Propriété

Combinaisons linéaires entières

Soit aa, bb et cc des entiers relatifs.

Si cc divise aa et bb, alors pour tous les entiers relatifs nn et nn', cc divise n×a+n×bn\times a+n'\times b.

bannière à retenir

À retenir

Autrement dit, si cc divise aa et bb, alors il divise toutes les combinaisons linéaires entières de aa et bb​.

bannière demonstration

Démonstration

Comme cc divise aa et bb, il existe deux entiers kk et kk' tels que a=k×ca=k\times c et b=k×cb=k'\times c.

Alors :

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

K=nk+nkK=nk+n'k'

Ainsi cc divise n×a+n×bn\times a+n'\times b.

Division euclidienne

bannière definition

Définition

Division euclidienne :

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

a=bq+ra=bq+r et 0r<b0\leq r < b

L’entier naturel aa est le dividende et bb est le diviseur.

L’entier naturel qq s’appelle le quotient et rr s’appelle le reste de la division euclidienne de aa par bb.

bannière exemple

Exemple

  • La division euclidienne de 343 par 12 : 343=12×28+7343=12\times 28+7 et 07<120\leq 7 < 12
  • La division euclidienne de 1526 par 11 : 1526=11×138+81526=11\times 138+8 et 08<110\leq 8 < 11
bannière propriete

Propriété

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

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

bannière exemple

Exemple

  • La division euclidienne de 431431 par 17:-17 : 431=17×(25)+6431=-17\times (-25)+6 avec 06<170\leq 6<\big|-17\big|
  • La division euclidienne de 121-121 par 9:-9: 121=9×14+5-121=-9\times 14+5 avec 05<90\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 11 s’il s’agit d’un homme, 22 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.