Mathématiques : 2Bac SMA-SMB

Séance 9-1-1 : Arithmétique dans  - Partie 1 (Cours)

 

 

Professeur : Mr CHEDDADI Haitam

 

Sommaire

 

I- P.G.C.D - P.P.M.C

1-1/ Rappels et compléments

1-2/ Calcul pratique du P.G.C.D : algorithme d'euclide

1-3/ Nombres premiers entre eux

1-4/ Théorème de bezout

1-5/ Détermination des coefficients du théorème de bezout

1-6/ Applications du théorème de bezout

1-7/ L'équation diophantienne ax+by=c

1-8/ P.G.C.D et P.P.C.M d’un nombre fini d’entiers relatifs

1-9/ Congruence modulo n (rappels et compléments)

II- Les nombres premiers

2-1/ Rappels et compléments

2-2- Petit théorème de fermat

2-3/ Décomposition en produit de facteurs premiers

2-4/ Applications de la décomposition en produit de facteurs premiers

 


I- P.G.C.D - P.P.M.C

 

1-1/ Rappels et compléments

Définition 1

Soit a et b deux entiers relatifs non nulles.

Le plus grand commun diviseur de a et b, noté ab ou PGCD(a,b), est le plus grand des
diviseurs positifs communs à a et b.

Le plus petit commun multiple de a et b, noté ab ou PPCM(a,b), est le plus petit des multiples strictement positifs communs à a et b.

On convient que : a0=a et a0=0

 

 

Remarques

Soit a et b deux entiers relatifs non nulles. Si d=ab et m=ab alors :

- d1 et d/a et d/b

- m1 et a/m et b/m

- Pour toute c* : c/a et c/bc/d et a/c et b/cm/c

- Pour toute c* : c/a et c/bcd et a/c et b/cmc

- ab=d et a1=1 et aa=a0=a

- ab=m et a1=a et aa=a

 

 

Proposition 1

Soit a, b et c des entiers relatifs non nulles et n un entier naturel. Alors :

1 ab=ba2 ab=ba3 a/bab=aab=b4 abc=abc5 cacb=cab6 c/ac/bacbc=abc 7 abc=abc8 cacb=cab9 c/ac/bacbc=abc10 anbn=abn11 anbn=abn12 ab.ab=ab

 

 

1-2/ Calcul pratique du P.G.C.D : algorithme d'euclide

Proposition 2

Soit a* et b*.

Lorsque b ne divise pas a, le plus grand commun diviseur des entiers a et b est égal au dernier reste non nul obtenu grâce à l'algorithme d'Euclide.

 

 

1-3/ Nombres premiers entre eux

Définition 2

Soit a et b deux entiers relatifs non nulles.

On dit que a et b sont premiers entre eux si le seul diviseur positif commun à a et b est 1, c'est-à-dire si ab=1:

 

Théorème 1

Soit a et b deux entiers relatifs non nulles, et d un entier naturel non nul.

Alors :

d=abα;β2 a=αd et b=βd et αβ=1

 

Théorème 2

Soit a,b*2

On a l’implication :

d=abu;v2 d=au+bv

 

Remarques

Le couple u;v n'est pas unique. Par exemple :

94=1=1×9-2×4 u=1 et v=-294=-43×9+97×4 u=-43 et v=97

La réciproque du théorème 2 est incorrecte, contre-exemple : 3×5+7×-1=8 mais 378.

 

1-4/ Théorème de bezout

Théorème 3

Soit a et b deux entiers relatifs non nulles.

Alors : ab=1u;v2 au+bv=1

 

Applications

En utilisant le théorème de Bezout, montrer que pour tout n :

1 5n+32n+1=12 2n-13-7n=1

 

1-5/ Détermination des coefficients du théorème de bezout

L’inconvénient du théorème du Bezout, sous sa forme théorique, est qu’il ne fournit pas les coefficients u et v intervenant dans la relation au+bv=1.

L’algorithme d’Euclide fournit une réponse pratique à ce problème.

À titre d’exemple, posons : a=155 et b=23.

 

1-6/ Applications du théorème de bezout

Théorème 4

Soit a, b et c des entiers relatifs non nuls.

On a l’implication : a/bc et ab=1a/c

Ce résultat est connu sous le nom de « Théorème de Gauss ».

Remarque

Dans le théorème de Gauss, la condition ab=1 est nécessaire.

Par exemple : 12/9×8 mais 12 ne divise ni le nombre 9 ni le nombre 8.

 

Théorème 5

Soit a, b et c des entiers relatifs non nuls.

On a l’implication : a/c et b/c et ab=1ab/c

Remarque

Dans le théorème 5, la condition ab=1 est nécessaire.

Par exemple : 8/48 et 12/48 mais 12×8 ne divise pas 48.

 

Proposition 3

Soit a, b et c des entiers relatifs non nuls.

Alors :

1- ab=1 et ac=1abc=1

2- Pour tout m,n*2 : ab=1abn=1 et ab=1ambn=1

 

1-7/ L'équation diophantienne ax+by=c

Théorème 6

Soit a, b et c des entiers relatifs tels que ab0

L’équation d’inconnue ax+by=c a des solutions si, et seulement si, ab divise c.

 

Théorème 7

Si le couple (x0;y0) est une solution de l’équation E : ax+by=c, alors l’ensemble solution de l’équation E s’écrit sous la forme :

S=x0+bkab;y0-akab/k

 

1-8/ P.G.C.D et P.P.C.M d’un nombre fini d’entiers relatifs

Définition 3

Soit n un entier naturel, n2, et des entiers relatifs non nuls a1,a2,...an

Le plus grand commun diviseur des entiers a1,a2,...an, noté a1a2...an, est le plus grand des diviseurs positifs communs à a1,a2,...an.

Le plus petit commun multiple des entiers a1,a2,...an, noté a1a2...an ou PPCMa1,a2,...an, est le plus petit des multiples positifs communs a1,a2,...an.

 

Théorème 8

Soit n un entier naturel, n2, et des entiers relatifs non nuls a1,a2,...an.

I1 existe des entiers relatifs u1,u2,...un tels que : i=1nai.ui=δ, où δ désigne le plus grand commun diviseur de a1,a2,...an.

 

Définition 4

Soit n un entier naturel, n2, et des entiers relatifs non nuls a1,a2,...an.

On dit que les entiers a1,a2,...an sont premiers entre eux si 1 est le seul diviseur positif commun à tous ces entiers, c'est-à-dire : a1a2...an=1

 

Remarques

Attention, dire que des entiers sont premiers entre eux ne signifie pas qu’ils sont entre eux deux à deux. Par exemple, les trois entiers a=8b=7 et c=12 sont premiers entre eux. Pourtant, les entiers a et c ont 4 pour grand diviseur commun : ac=4>1

La relation ab.ab=ab n’est pas valable pour plus de deux entiers relatifs.

Contre-exemple : 61015=30 et 61015=1

donc : 61015.61015=306×10×15

c'est-à-dire qu’on a en général : abc.abcabc

Le résultat du théorème 8 reste aussi valable pour plus de deux entiers. Plus précisément : n2 δ=a1a2...an signifie qu’il existe a'1,a'2,...a'nn tel que pour tout i1;2;...;n : ai=δa'i et a'1a'2...a'n=1.

 

Théorème 9

Soit n un entier naturel, n2, et des entiers relatifs non nuls a1,a2,...an.

Les entiers a1,a2,...an sont premiers entre eux si, et seulement si :

u1;u2;...unn ; i=1nai.ui=1

Autrement dit :

a1a2...an=1u1;u2;...unn ; i=1nai.ui=1

 

1-9/ Congruence modulo n (rappels et compléments)

Définition 5

Soit n un entier naturel non nul.

On dit que deux entiers relatifs a et b sont congrus modulo n si n divise b-a, c'est-à-dire s'il existe un entier k tel que b=a+kn.

On écrit : ab n

 

Proposition 4

Soit n un entier naturel non nul.

La relation « de congruence» est une relation d'équivalence sur , c'est-à-dire :

1) Elle est réflexive : a aa n

2) Elle est symétrique : a;b2 ab nba n

3) Elle est transitive : a;b;c3 ab n et bc nac n

 

Proposition 5

Soit n un entier naturel non nul et a;b;c;d4. Alors :

1) ab n(Les restes respectifs des divisions euclidiennes de a et b par n sont égaux)

2) Si ab n et cd n, alors : a+cb+d n et acbd n.

3) Si ab n et k, alors : kakb n

4) Si ab n et p, alors : apbp n

 

Théorème 10

Soit a, b et c des entiers relatifs non nulles et n*.

Si d=cn alors :

acbc nab nd

 

Proposition 6

Soit a, b et c des entiers relatifs non nuls et n;p*2 tels que cn=1

Alors :

1 acbc nab n2 ab np/nab p3 acbc pp premierp ne divise pas cab p

 

II- Les nombres premiers

 

2-1/ Rappels et compléments

Définition 6

Un entier relatif p est dit premier lorsqu’il admet exactement quatre diviseurs.

Remarques

Si p est un entier premier dans , alors -p est premier dans . C’est pourquoi dans cette section, nous nous limitons à l'ensemble des entiers naturels.

L’ensemble des nombres premiers (positifs) est noté .

Un entier n2 non premier est dit composé.

 

Théorème 11

Soit n un entier composé supérieur ou égal à 2. Alors :

1) Le plus petit diviseur positif de n différent de 1 est un nombre premier.

2) n est un produit de nombres premiers. En particulier, n possède au moins un diviseur premier.

3) n possède un facteur premier p tel que p2n.

 

Théorème 12

L'ensemble  des nombres premiers positifs est infini.

 

 

Théorème 13

1) Si p et q sont deux nombres premiers positifs distincts, alors ils sont premiers entre eux.

En d’autres termes : p et q et pqpq=1

2) Si p, alors p est premier avec tous les entiers qu'il ne divise pas.

En d'autres termes : a p p ne divise pas apa=1

 

Proposition 7

Soit a,b2 et p un nombre premier. Alors :

p/abp/a ou p/b

 

Corollaire

Soit a1,a2,...an des entiers relatifs et p un nombre premier. Alors :

p/a1.a2....ani1;2;...;n p/ai

Soit a et p un nombre premier. Alors :

n* p/anp/a

Soit p1,p2,...,pn et p des nombres premiers. Alors :

p/p1.p2....pni1;2;...;n p=pi

 

 

2-2- Petit théorème de fermat

Théorème 14

1) Si p est un nombre premier positif, alors il divise ap-a, pour tout a.

Autrement dit : a apa p

2) Si p est un nombre premier positif, alors pour tout a : pa=1ap-11 p

 

 

Remarques

La réciproque du petit théorème de Fermat n'est pas vraie. Autrement dit, si ap-11 p, alors l’entier p n'est pas nécessairement premier. A titre d’exemple, le nombre p=341=31×11 n’est pas premier, or, il divise 2341-2 car :

2341-2=22340-1=221034-1=2210-1k=033210k=2×3×341×k=033210k

Le petit théorème de Fermat permet de calculer le reste de n'importe quel entier assez grand modulo un nombre premier positif p.

 

 

2-3/ Décomposition en produit de facteurs premiers

Théorème 15

Tout élément de *-1;-1 admet une décomposition en produit de nombres premiers, unique à
l’ordre près des facteurs.

Autrement dit, si n*-1;-1, il existe N*, ε1;-1, des nombres premiers deux à deux distincts p1,p2,...pN, et des entiers α1,α2,...αN tels que : n=ε.p1α1.p2α2...pNαN

Ce théorème est connu sous le nom « Théorème fondamental de l'arithmétique ».

 

 

2-4/ Applications de la décomposition en produit de facteurs premiers

Théorème 16

Soit n*-1;-1 et sa décomposition n=ε.p1α1.p2α2...pNαN en produit de facteurs premiers.

Les diviseurs de n sont les entiers relatifs : d=ε'.p1γ1.p2γ2...pNγN avec k1;2;...;N 0γkαk et ε'1;-1

Le nombre de diviseurs positifs de n est : 1+α11+α2...1+αn