Diviseurs et factorisationDiviseurs et factorisation

Multiples et DiviseursMultiples et Diviseurs

Soit Soit aa un nombre non nul, chaque nombre un nombre non nul, chaque nombre divisible par divisible par aa est un est un multiple multiple dede a a; chaque ; chaque nombre qui divise nombre qui divise aa est un est un diviseur diviseur dede a a. . Autrement dit, Autrement dit, b b est un diviseur de est un diviseur de aa si, dans la si, dans la division de division de aa par par bb, le reste est nul. , le reste est nul.

Si a et b sont deux entiers naturels, b n'étant Si a et b sont deux entiers naturels, b n'étant pas nul, on dit que pas nul, on dit que bb divise divise a a ou que ou que bb est un est un diviseur de diviseur de aa ou que ou que aa est un multiple de est un multiple de bb s'il s'il existe un entier existe un entier qq tel que tel que a = bqa = bq..

Les multiples d’un nombre se déterminent en multipliant Les multiples d’un nombre se déterminent en multipliant le nombre de départ par chaque terme de la succession le nombre de départ par chaque terme de la succession des nombres naturels, sauf le zéro, ou en ajoutant ce des nombres naturels, sauf le zéro, ou en ajoutant ce nombre à la somme précédente pour former une série. nombre à la somme précédente pour former une série. M(4) = {4xM(4) = {4x11; 4x; 4x22; 4x; 4x33; 4x; 4x44; ...; 4x; ...; 4xnn} } M(4) = {4; 8; 12; 16; ...} M(4) = {4; 8; 12; 16; ...}

Les multiples d’un nombre sont donc infinis.Les multiples d’un nombre sont donc infinis.M(n)≥M(n)≥nn#M(n)=∞ (où #M(n) cardinalité des multiples de #M(n)=∞ (où #M(n) cardinalité des multiples de nn))

Les diviseurs d’un nombre coïncident avec ses Les diviseurs d’un nombre coïncident avec ses sous-multiples. sous-multiples. D(24) = {1;2;3;4;5;8;12;24}D(24) = {1;2;3;4;5;8;12;24}

Il est évident que les diviseurs d’un nombre sont Il est évident que les diviseurs d’un nombre sont finis et ils sont compris entre 1 et le nombre de finis et ils sont compris entre 1 et le nombre de départ. départ.

Un nombre quelconque admet comme diviseur Un nombre quelconque admet comme diviseur le nombre 1 et soi-même. le nombre 1 et soi-même.

Nombres premiers et composésNombres premiers et composés

Un nombre premier est un entier naturel qui admet Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs exactement deux diviseurs distincts entiers et positifs (qui sont 1 et lui-même). Cette définition exclut 1, qui n'a (qui sont 1 et lui-même). Cette définition exclut 1, qui n'a qu'un seul diviseur entier positif. Par opposition, un qu'un seul diviseur entier positif. Par opposition, un nombre non nul produit de deux nombres entiers nombre non nul produit de deux nombres entiers différents de 1 est dit composé. Par exemple 12 = 2 × 6 différents de 1 est dit composé. Par exemple 12 = 2 × 6 est composé, tout comme 21 = 3 × 7 ou 7 × 3, mais 11 est composé, tout comme 21 = 3 × 7 ou 7 × 3, mais 11 est premier car 1 et 11 sont les seuls diviseurs de 11. est premier car 1 et 11 sont les seuls diviseurs de 11. Les nombres 0 et 1 ne sont ni premiers ni composés. Les nombres 0 et 1 ne sont ni premiers ni composés. Les nombres premiers inférieurs à 100 sont :Les nombres premiers inférieurs à 100 sont :

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 9761, 67, 71, 73, 79, 83, 89, 97

Il existe, en outre, des nombres premiers en quantité Il existe, en outre, des nombres premiers en quantité infinie (Euclide a formulé la première démonstration infinie (Euclide a formulé la première démonstration “pour absurde”). Selon le théorème de l’infinité des “pour absurde”). Selon le théorème de l’infinité des nombres premiers, quoiqu’on choisisse un nombre nombres premiers, quoiqu’on choisisse un nombre naturel naturel nn énorme, il existera toujours un nombre premier énorme, il existera toujours un nombre premier plus grand que plus grand que nn. .

Leur importance en mathématiques est démesurée et Leur importance en mathématiques est démesurée et dérive du théorème fondamental de l'arithmétique, qui dérive du théorème fondamental de l'arithmétique, qui affirme que tout nombre naturel affirme que tout nombre naturel n n non nul (plus grand non nul (plus grand que 1) est un nombre premier ou il peut s'écrire de que 1) est un nombre premier ou il peut s'écrire de manière unique comme le produit fini de nombres manière unique comme le produit fini de nombres premiers à une puissance adéquate.premiers à une puissance adéquate.

Crible d’ÉratosthèneCrible d’Ératosthène Ératosthène était un astronome, géographe, philosophe Ératosthène était un astronome, géographe, philosophe

et mathématicien grec du IIIe siècle av. J.-C. (275-195 et mathématicien grec du IIIe siècle av. J.-C. (275-195 a.C.). Directeur de la bibliothèque d’Alessandria, il a.C.). Directeur de la bibliothèque d’Alessandria, il élabora une procédure de recherche des nombres élabora une procédure de recherche des nombres premiers. Le crible d'Ératosthène est un procédé qui premiers. Le crible d'Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N.L'algorithme procède un certain entier naturel donné N.L'algorithme procède par élimination : il s'agit de supprimer d'une table tous par élimination : il s'agit de supprimer d'une table tous les multiples des entiers de 2 à N.les multiples des entiers de 2 à N.

On commence par les multiples de 2, puis à chaque fois on raye les On commence par les multiples de 2, puis à chaque fois on raye les multiples du plus petit entier restant jusqu'à ce que le carré de celui-ci multiples du plus petit entier restant jusqu'à ce que le carré de celui-ci soit supérieur au plus grand entier de la liste.soit supérieur au plus grand entier de la liste.

On peut s'arrêter lorsque le carré du plus petit entier est inférieur au On peut s'arrêter lorsque le carré du plus petit entier est inférieur au plus grand entier, car dans ce cas, s'il existait des non-premiers, ils plus grand entier, car dans ce cas, s'il existait des non-premiers, ils auraient déjà été rayés précédemment.auraient déjà été rayés précédemment.

À la fin du processus, tous les entiers qui n'ont pas été rayés sont les À la fin du processus, tous les entiers qui n'ont pas été rayés sont les nombres premiers inférieurs à N.nombres premiers inférieurs à N.

Critères de divisibilitéCritères de divisibilité *par 2*par 2

Un entier est divisible par 2 si son dernier chiffre décimal est pair, Un entier est divisible par 2 si son dernier chiffre décimal est pair, c’est-à-dire s'il se termine par 0, 2, 4, 6 ou 8. Cette condition est c’est-à-dire s'il se termine par 0, 2, 4, 6 ou 8. Cette condition est nécessaire et suffisante.nécessaire et suffisante.

*par 3*par 3Un entier est divisible par 3 si la somme de ses chiffres est elle-même Un entier est divisible par 3 si la somme de ses chiffres est elle-même divisible par 3 ou par un de ses multiples. Cette condition est divisible par 3 ou par un de ses multiples. Cette condition est nécessaire et suffisante.nécessaire et suffisante.Exemples: Exemples:

132 est divisible par 3 parce que 1+2+3=6, qui est divisible par 3, par conséquent 132 est divisible par 3 parce que 1+2+3=6, qui est divisible par 3, par conséquent aussi 132aussi 132

12 est divisible par 3 parce que 1+ 2= 3, qui est divisible par 3, par conséquent 12 est divisible par 3 parce que 1+ 2= 3, qui est divisible par 3, par conséquent aussi12aussi12

24 est divisible par 3 parce que 2+ 4= 6, qui est divisible par 3, par conséquent 24 est divisible par 3 parce que 2+ 4= 6, qui est divisible par 3, par conséquent aussi 24aussi 24

16 n’est pas divisible par 3 parce que 1+6= 7, qui n’est pas multiple de 316 n’est pas divisible par 3 parce que 1+6= 7, qui n’est pas multiple de 3

*par 4*par 4Un entier est divisible par 4 si ses deux derniers chiffres sont 00 ou Un entier est divisible par 4 si ses deux derniers chiffres sont 00 ou si le nombre formé par ses 2 derniers chiffres est divisible par 4, ou si le nombre formé par ses 2 derniers chiffres est divisible par 4, ou si son avant-dernier chiffre est impair et le dernier est 2 ou 6, ou si si son avant-dernier chiffre est impair et le dernier est 2 ou 6, ou si son avant-dernier chiffre est pair et le dernier est 0, 4, 8.son avant-dernier chiffre est pair et le dernier est 0, 4, 8.Exemples: Exemples: 144 se termine avec les chiffres 44 par conséquent il est divisible par 4 144 se termine avec les chiffres 44 par conséquent il est divisible par 4 500 est divisible par 4500 est divisible par 4

*par 5*par 5Un entier est divisible par 5 s'il se termine par 0 ou 5 Un entier est divisible par 5 s'il se termine par 0 ou 5 Exemples: Exemples: 55 est divisible par 5 parce qu'il se termine par 555 est divisible par 5 parce qu'il se termine par 5 60 est divisible par 5 parce qu'il se termine par 060 est divisible par 5 parce qu'il se termine par 0 37 n’est pas divisible par 5, parce qu'il ne se termine ni par 5 ni par 037 n’est pas divisible par 5, parce qu'il ne se termine ni par 5 ni par 0

*par 9*par 9Un entier est divisible par 9 si la somme de ses chiffres est divisible par 9.Un entier est divisible par 9 si la somme de ses chiffres est divisible par 9.Exemples: Exemples:

18 est divisible par 9 parce que 1+ 8= 9, qui est divisible par 9, par conséquent 18 est divisible par 9 parce que 1+ 8= 9, qui est divisible par 9, par conséquent aussi 18aussi 18

369 est divisible par 9 parce que 3+ 6+ 9= 18, qui est divisible par 9, par 369 est divisible par 9 parce que 3+ 6+ 9= 18, qui est divisible par 9, par conséquent aussi 369conséquent aussi 369

457 n’est pas divisible par 9 parce que 4+5+7= 16, qui n’est pas multiple de 9457 n’est pas divisible par 9 parce que 4+5+7= 16, qui n’est pas multiple de 9 16 n’est pas divisible par 9 parce que 1+6= 7, qui n’est pas multiple de 916 n’est pas divisible par 9 parce que 1+6= 7, qui n’est pas multiple de 9

*par 11*par 11Un entier est divisible par 11 si la somme alternée de ses chiffres à partir Un entier est divisible par 11 si la somme alternée de ses chiffres à partir de la droite est divisible par 11 (par alternée, on entend ajouter/soustraire de la droite est divisible par 11 (par alternée, on entend ajouter/soustraire successivement) ou elle est nulle.successivement) ou elle est nulle.Exemples: Exemples:

4257; la différence entre la somme des chiffres de rang pair (2 et 7) et la somme 4257; la différence entre la somme des chiffres de rang pair (2 et 7) et la somme des chiffres de rang impair (4 et 5) doit être un multiple de 11 ou être nulle: des chiffres de rang impair (4 et 5) doit être un multiple de 11 ou être nulle: 9-9=0. 9-9=0.

919 380 (9+9+8 = 26; 1+3+0 = 4; 26 - 4 = 22 = 2x11)919 380 (9+9+8 = 26; 1+3+0 = 4; 26 - 4 = 22 = 2x11)

Décomposition en facteurs Décomposition en facteurs premiers ou factorisationpremiers ou factorisation

Le procédé qui permet de rechercher les nombres premiers diviseur Le procédé qui permet de rechercher les nombres premiers diviseur d’un nombre donné est appelé décomposition en facteurs premiers d’un nombre donné est appelé décomposition en facteurs premiers ou factorisation. Ce procédé est valide pour les nombres composés ou factorisation. Ce procédé est valide pour les nombres composés et non pas pour les nombres premiers. En accord avec le théorème et non pas pour les nombres premiers. En accord avec le théorème fondamental de l'arithmétique tout nombre naturel n non nul (plus fondamental de l'arithmétique tout nombre naturel n non nul (plus grand que 1) est un nombre premier ou il peut s'écrire de manière grand que 1) est un nombre premier ou il peut s'écrire de manière unique (si on ne considère pas l’ordre des facteurs) comme le unique (si on ne considère pas l’ordre des facteurs) comme le produit fini de nombres premiers à une puissance adéquate. En produit fini de nombres premiers à une puissance adéquate. En d’autres mots : chaque entier strictement positif peut être écrit d’autres mots : chaque entier strictement positif peut être écrit comme un produit de nombres premiers d'une unique façon, à comme un produit de nombres premiers d'une unique façon, à l'ordre près des facteurs.l'ordre près des facteurs.

(où p1, p2,…, pm sont les nombres premiers ordonnés de façon à (où p1, p2,…, pm sont les nombres premiers ordonnés de façon à ce que p1 < p2 < p3 <…< pm et où a1, a2, a3,…, am sont les ce que p1 < p2 < p3 <…< pm et où a1, a2, a3,…, am sont les exposants entiers positifs). exposants entiers positifs).

Règle pratiqueRègle pratique : on utilise les critères de divisibilité et à : on utilise les critères de divisibilité et à travers une série de divisions, en partant des nombres travers une série de divisions, en partant des nombres premiers les plus petits (2;3;5; ..), on établit les facteurs premiers les plus petits (2;3;5; ..), on établit les facteurs qui multipliés entre eux donnent le nombre de départ. qui multipliés entre eux donnent le nombre de départ. La décomposition d'un nombre non premier en facteurs La décomposition d'un nombre non premier en facteurs premiers s'effectue comme suit :premiers s'effectue comme suit :

1) on établit si le nombre est divisible par 2 et en cas affirmatif, 1) on établit si le nombre est divisible par 2 et en cas affirmatif, on calcule le quotienton calcule le quotient

2) on continue en divisant par deux jusqu'à ce que l'on trouve un 2) on continue en divisant par deux jusqu'à ce que l'on trouve un quotient qui n'est plus divisible par deuxquotient qui n'est plus divisible par deux

3) si le premier nombre ou le dernier quotient n'est pas divisible 3) si le premier nombre ou le dernier quotient n'est pas divisible par deux, on continue de la même façon avec les nombres par deux, on continue de la même façon avec les nombres premiers suivants (3, 5, 7...) jusqu'à ce que l'on obtienne un premiers suivants (3, 5, 7...) jusqu'à ce que l'on obtienne un quotient qui est un nombre premierquotient qui est un nombre premier

La méthode de La méthode de décomposition en facteurs décomposition en facteurs premiers est évidente dans premiers est évidente dans les exemples suivantsles exemples suivants

RemarqueRemarque : si, lors de la : si, lors de la recherche d'un diviseur recherche d'un diviseur possible pour le nombre x possible pour le nombre x on dépasse la valeur on dépasse la valeur √x√x+1 +1 c'est que x est un nombre c'est que x est un nombre premier...premier...

1

2|13

2|91

2|182

2|364

2|728

728 = 2 x 2 x 2 x 7 x 13728 = 2 x 2 x 2 x 7 x 13

= 23 x 13= 23 x 13