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 !

Rappels sur la récurrence

Définitions : les ensembles de nombres

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

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

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

Z\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)P(n) est vraie pour tout entier naturel nn supérieur ou égal à un entier naturel n0n_0 fixé, on procède en trois étapes :

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

Attention : cette étape est à faire pour un entier nn 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>n0)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 xx, il existe un unique entier relatif nn tel que xx soit compris entre nn inclus et n+1n+1 exclu : nx<n+1n ≤ x < n+1

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

Représentation graphique de la fonction partie entière maths terminale Représentation graphique de la fonction partie entière

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

Divisibilité dans Z\mathbb Z

Définitions : diviseurs et multiples

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
  • Conséquences de cette définition :
  • 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 22, c’est-à-dire ceux qui s’écrivent 2k+12k+1 avec kZk\in\mathbb Z.

Propriété : la transitivité

Soit a,ba,b et cc des entiers relatifs. Si bb divise aa et si cc divise bb, alors cc divise aa.

Démontration :

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.

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.

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

K=nk+kK=nk+'k'

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

Division euclidienne

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

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|

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