Il rassemble les connaissances nécessaires et indispensable à tout élève débutant en arithmétique.
Notations
Liens utiles :
Notations
IN = {0,1,2,3,...} l'ensemble des entiers naturels,
IN∗ l'ensemble des entiers naturels non nuls ;
Z = {...,−3,−2,−1,0,1,2,3,...} l'ensemble des entiers relatifs ;
Q l'ensemble des nombres rationnels,
c'est-à-dire qui peuvent s'écrire sous la forme:
a/b avec a ∈ Z et b ∈ IN∗
c'est-à-dire qui peuvent s'écrire sous la forme:
a/b avec a ∈ Z et b ∈ IN∗
IR l'ensemble des nombres réels.
Q∗ désigne l'ensemble des rationnels non nuls,
Q∗+ l'ensemble des rationnels strictement positifs
Q∗− l'ensemble des rationnels strictement négatifs.
Q∗+ l'ensemble des rationnels strictement positifs
Q∗− l'ensemble des rationnels strictement négatifs.
On introduit de même les notations Z−, Z∗, R∗, R∗+, R∗-.
Si a et b sont deux nombres, alors ab désigne le produit a×b.
Dans ce document, nous utiliserons fréquemment le principe de récurrence suivant:
Soit P(n) une propriété d'un entier n. On suppose que:
(i) (initialisation) P(0) est vraie
(ii) (hérédité) pour tout entier naturel n,
si P(n) est vraie alors P(n + 1) est vraie.
Alors P(n) est vraie pour tout n.
Vocabulaire :
lorsque l'on essaye de démontrer l'implication P(n) ⇒ P(n + 1),
la propriété P(n) que l'on suppose vraie s'appelle l'hypothèse de récurrence.
Une variante de ce principe est la récurrence forte :
supposons que:
(i) (initialisation) P(0) est vraie
(ii) (hérédité) pour tout entier naturel n,
si P(k) est vraie pour tout k ⩽ n alors P(n + 1) est vraie.
Alors P(n) est vraie pour tout n.
Exercice:
Montrer que pour tout n∊IN* on a 2n ≥ n.
Solution:
Soit n∊IN* On pose P(n) : 2n ≥ n.
Montrons que P(n) est vraie par récurrence
(i) le premier élément de IN* est 1
pour n=1 ona 21=1≥0 donc P(1) est vraie.
(ii) on suppose que P(n) est vraie ie 2n ≥ n
Montrons que P(n + 1): 2n+1 ≥ n+1 est vraie
On a:
d'après l'hypothèse de récurrence:
2n ≥ n
➝ 2x2n ≥ 2n
➝2n+1 ≥ 2n
Or on a: n∊IN*
➝n≥1
➝ 2n≥n+1
➝2n+1 ≥ n+1
d’ou P(n+1): 2n+1 ≥ n+1 est vraie.
Alors P(n):2n ≥ n est vraie pour tout n∊IN*.
2- Divisibilité
Définition:
Soient a, b deux entiers relatifs.
On dit que a divise b
(ou que b est divisible par a, ou que b est un multiple de a)
s'il existe un entier c tel que b = ac. On note a | b.
Par exemple:
2|6, 1|n, n|n, n|0 pour tout entier n.
Proposition:
Soient a, b, b , c, λ des entiers.
(i) (Transitivité) Si a | b et b | c alors a | c.
(ii) Si a | b alors a | bc.
(iii) Si a | b et a | b alors a | b + b .
(iv) Si a | b et a | b alors a | b + λb .
(v) Si λ = 0 alors a | b si et seulement si λa | λb.
(vi) Si a | b et b ≠ 0 alors |a| ⩽ |b|.
(vii) Si a | b et b | a alors b = a ou b = −a.
Démonstration
(i) Par définition:
il existe u et v tels que b = au et c = bv.
On a alors c = (au)v = a(uv)
donc a | c.
(ii) Il est clair que b | bc. D'après (i), on en déduit que a | bc.
(iii) Il existe u et v tels que b = au et b = av.
On a alors b + b = au + av = a(u + v) donc a | b + b .
(iv) D'après (ii), on a a | λb , et d'après (iii)
on en déduit que a | b + (λb ).
(v) Si a | b, alors il existe u tel que b = au.
Ceci entraîne λb = (λa)u
donc λa | λb.
Réciproquement, si λa | λb, alors il existe v tel que λb = λau. Comme λ = 0, on peut diviser par λ, ce qui donne b = au, autrement dit a | b.
(vi) Soit u tel que b = au. Comme b ≠ 0, on a u ≠ 0, donc 1 ⩽ |u|.
En multipliant membre à membre par |a|, on obtient |a| ⩽ |au| = |b|.
(vii) On suppose que a | b et b | a.
Si a = 0, alors le fait que a | b entraîne b = 0
donc on a bien b = a ou b =-a.
De même, si b = 0 alors b = a ou b = -a.
Si a ≠ 0 et b ≠ 0,
alors d'après (vi) on a |a| ⩽ |b| et |b| ⩽ |a|,
donc |a| = |b|, ce qui donne bien b = a ou b = −a.
Exercice 1.
Montrer que si a | b et c | d alors ac | bd.
Solution:
Il existe u et v tels que b = au et d = cv donc bd = (ac)(uv)
donc ac | bd.
Exercice 2.
Quels sont les entiers n ∈ N tels que n | n + 7 ?
Solution:
On a:
n | n+7& n | n
alors n | (n+ 7)−n = 7
donc n vaut 1 ou 7.
Dans ces deux cas, on voit que n divise bien n + 7.
Exercice 3.
Quels sont les entiers n ∈ N tels que n2 + 1 | n?
Solution:
si n≠0
On a n²+1 | n et n≠0
alors n²+1 ≤ n
d’autre part n>0
ie: n²+1 > n² ≥ n
ce qui est absurde, donc seul n = 0 est solution.
Exercice 4.
Montrer que pour tout entier n, l'entier n(n + 1) est pair.
Solution:
Si n est pair, alors 2 | n et n | n (n + 1) donc n(n + 1) est pair.
Si n est impair, alors 2 |n + 1 et n+1| n(n + 1) donc n(n + 1) est pair.
Exercice 5.
Montrer que pour tout entier n,
l'entier n(n + 1)(n + 2) est divisible par 6.
Solution:
n, n + 1 et n + 2 sont trois entiers consécutifs donc un des trois est divisible par 3
donc 2 | n(n + 1)(n + 2) est divisible par 3.
on peut écrire n(n + 1)(n +2)=3u.
De plus, n(n + 1) est pair
par l'exercice précédent donc n(n + 1)(n + 2) aussi.
donc 3u est pair.
Or, le produit de deux nombres impairs est impairs
donc u doit être pair,
donc 6=3 × 2 | 3u, d'où le résultat.
Exercice 6.
Soient a, b, c des entiers.
Montrer que si n est un entier vérifiant an²+ bn + c = 0 alors n | c.
Solution:
On a
an² + bn + c = 0
➝ c =an²-bn.
Or, n | -an² et n | -bn donc n | c.
Exercice 7.
Déterminer les entiers n tels que n5-2n4-7n2 -7n +3=0.
Solution:
On a:
n5-2n4-7n2 -7n +3=0.
➝ n5-2n4-7n2 -7n=3
et on a:
n | n5-2n4-7n2 -7n
➝ n|3
donc n∈ {-3,-1, 1,3}.
En testant ces quatre valeurs, on trouve que les seules solutions sont −1 et 3.
Exercice 8.
Soient a ⩾ 1 et n des entiers tels que a | n+2 et a | n²+n + 5.
Montrer que a = 1 ou a = 7.
Solution:
On a:
a | n + 2 & a | n
a | n(n + 2) = n² +2n
et puis que: a | n²+n + 5
donc a | n²+n+5-(n²+ 2n)=-n+5.
On en déduit que a | (n +2)+(-n +5)=7
Donc a = 1 ou a = 7 (car a ⩾ 1 ).
3- Division Euclidienne
La division Euclidienne permet de tester si un entier est divisible par un autre.
Théorème:
Soient a et b deux entiers tels que b ⩾ 1.
Alors il existe un et un seul couple (q,r) d'entiers tel que
• a = bq + r;
• 0 ⩽ r ⩽ b − 1.
Exemple :
pour a = 25 et b = 7, le quotient est 3 et le reste est 4.
25=7x3+4
pour a = -17 et b =-5, le quotient est 4 et le reste est 2.
-17=-5x4+2
Proposition
Soient a, b, d, q, r des entiers.
On suppose que a = bq + r.
Alors d divise a et b si et seulement si d divise b et r.
Démonstration.
Si d divise a et b alors d divise a − bq
donc d divise b et r.
De même, si d divise b et r alors d divise bq + r = a.
4- L'algorithme d'Euclide
Soient maintenant a > b > 0.
L'algorithme d'Euclide consiste à effectuer des divisions Euclidiennes successives :
on pose a0= a et a1 = b.
puis pour tout k > 0
on effectue la division Euclidienne de ak par ak+1 et on appelle ak+2 le reste.
a0 = a1q1 + a2
a1 = a2q2 + a3
a2 = a3q3 + a4
· · ·
an-2 = an-1 qn-1 + an
an = an qn + an+1
jusqu'à tomber sur un reste nul an+1 = 0.
Le processus s'arrête bien car les restes sont de plus en plus petits :
a1 > a2 > a3 > · · ·
On note n l'indice tel que an est le dernier reste non nul.
5- PGCD (plus grand commun diviseur)
Exemple
Calculons le PGCD de 183 et 117 par ce procédé.
Exercice 9.
Définition
Soient a et b deux entiers.
Un entier d ⩾ 0 est appelé PGCD
(plus grand commun diviseur) de a et b.
s'il vérifie la propriété suivante :
pour tout d’ entier, d’ divise a et b si et seulement si d’ divise d.
(Par exemple, pour a = 15 et b = 21,
l'entier d = 3 est le PGCD de a et b.
En effet, les diviseurs positifs communs de 15 et 21 sont 1 et 3, et un entier naturel divise 3 si et seulement s'il est égal à 1 ou à 3.)
Théorème
Si a et b sont non nuls, alors dans l'algorithme d'Euclide,
an est le PGCD de a et b.
Si b = 0 alors a est le PGCD de a et b.
Démonstration. Premier cas : a et b sont non nuls. D'après la proposition précédente,
on a:
d’| a et d’ | b
⇐⇒ d’ | d’ et d’ | a1
⇐⇒ d’ | a1 et d’ | a2
· · ·
⇐⇒ d’ | an et d’ | an+1
⇐⇒ d’ | an
(cette dernière équivalence découle du fait que an+1 = 0 et que d’ | 0 est vrai pour tout d’ ).
Deuxième cas : b = 0. Alors d’ | a et d’ | b si et seulement si d’ | a, donc a est le PGCD
Exemple
Calculons le PGCD de 183 et 117 par ce procédé.
183 = 117 × 1 + 66
117 = 66 × 1 + 51
66 = 51 × 1 + 15
51 = 15 × 3 + 6
15 = 6 × 2 + 3
6 = 3 × 2 + 0
0 fin de l'algorithme d'Euclide
Le dernier reste non nul est 3=an.
Le dernier reste non nul est 3=an.
donc le PGCD de 183 et 117 est égal à 3.
Exercice 9.
Vérifier par l'algorithme d'Euclide que le PGCD de 364 et de 154 est égal à 14.
364 = 154 × 2 + 56
154 = 56 × 2 + 42
56 = 42 × 1 + 14
42 = 14 × 3 + 0
PGCD (364,154)=14.
Exercice 10.
a=10100 et b=10121 + 10813 + 10
a et b Combien ont-ils de diviseurs communs ?
Pour tout entier d,
d divise a et b si et seulement si d divise leur PGCD.
On calcule donc ce PGCD avec l'algorithme d'Euclide :
10121 + 10813 + 10 = 10100 × (1021 + 10713 ) + 10
10100 = 10 × 1099+ 0
PGCD(a,b)= 10
donc les diviseurs communs sont les diviseurs de 10,
soit −10, −5, −2, −1, 1, 2, 5 et 10.
Il y en a 8.
Généralement:
On peut généraliser la notion de PGCD à plusieurs entiers.
On a par exemple PGCD(a, b, c) = PGCD(PGCD(a, b),c) = PGCD(a,PGCD(b, c)).
En effet,
(d | a et d | b) et d | c
⇐⇒ d | PGCD(a, b) et d | c
⇐⇒ d | PGCD(PGCD(a, b),c)
et de même d | a et (d | b et d | c)
⇐⇒ d | PGCD(a,PGCD(b, c)).
On définit également le PGCD de deux (ou plusieurs) entiers relatifs par PGCD(a, b) = PGCD(|a|,|b|).
Proposition
Si a = bq + r alors PGCD(a, b) = PGCD(b, r).
Démonstration:
Évident d'après (4- Division Euclidienne: Proposition)
Exercice 11
Déterminer le PGCD de b=1000000000 et a=1000000005.
Solution:
On a
a=109+5=bx1+5
D'après la proposition précédente pour q = 1 et r = 5
on a :
PGCD(a,b) = PGCD(b,r) = PGCD(109,5)=5.
car 5 | 109.
6- Nombre premier
donc p est premier.
L'une des notions les plus importantes en arithmétique est celle de nombre premier
Définition
Un entier p est dit premier
si p ⩾ 2 et si les seuls diviseurs positifs de p sont 1 et p.
La liste des nombres premiers commence par
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47.
A noter que 1 n'est pas premier.
Exercice 12.
131 est-il premier ? 221 est-il premier ?
Remarque
Si p est premier, alors pour tous entiers naturels a et b,
l'égalité p = ab entraîne (a = 1 et b = p) ou (a = p et b = 1).
Démonstration:
p = ab entraîne que a est un diviseur de p, donc a = 1 ou a = p.
Si a = 1 alors p = ab = 1 × b = b.
si a = p alors p = pb donc b = 1.
Proposition
Soit n ⩾ 2 un entier.
Le plus petit diviseur ⩾ 2 de n est un nombre premier.
Exemple : pour n = 75, les diviseurs ⩾ 2 de n sont 3,5,15,25,75.
Le plus petit de ces nombres est égal à 3, qui est bien premier.
Démonstration:
Notons p le plus petit entier tel que
(i) p | n.
(ii) p ⩾ 2.
Notons que p est bien défini puisqu'il existe des entiers
(par exemple n) vérifiant les deux conditions (i) et (ii).
Soit d est un diviseur ⩾ 2 de p.
Comme d | p et p | n, on a d | n.
De plus, p étant le plus petit diviseur ⩾ 2 de n,
on a p ⩽ d.
Or, d ⩽ p
puisque d divise p.
donc d = p.
Ceci prouve que l'unique diviseur ⩾ 2 de p est p lui-même, donc p est premier.
* Concepts de Base
Liens utiles :
L’Olympiade Internationale de Mathématiques (OIM)
Olympiade de Maths, c'est une gymnastique de l'esprit, Ce qu'il faut c'est 4 math .net et beaucoup de pratiques.
4 math .net Le première clé pour être bon en maths.
4 math .net Le première clé pour être bon en maths.
0 Commentaires