L'arithmétique (Travaux Pratiques Encadrés)

« Un nombre n est divisible par un autre nombre m lorsqu'i l est le produit de ce dernier avec un troisième nombre : n =m.p .

Autrement dit, le reste de la division euclidienne de n par m est égal à O.

Exemple : 8 = 4 x 2 + o.

Le nombre m est alors un diviseur den, et n est un multiple de m .

Critères de divisibilité o Un nombre est divisible par 2 s'il se termine par un chiffre pair (0, 2, 4, 6, 8).

o Un nombre est divisible par 3 lorsque la somme de ses chiffres est divisible par 3.

Exemple : 471, la somme de ses chiffres est 4 + 7 + 1 = 12, qui est divisible par 3 .

• Un nombre est divisible par 5 lorsqu 'il se termine par 0 ou 5.

• Un nombre est divisible par 9 lorsque la somme de ses chiffres est divisible par 9.

Exemple : 4 185, la somme de ses chiffres est 4 + 1 + 8 + 5 = 18, qui est divisible par 9.

AlGORITHME D'EUCLIDE ET PGCD À partir de la notion de divisibilité , on introduit naturellement les notions très utiles en théorie des nombres de plus grand diviseur commun (PGCD) et plus petit multiple commun (PPCM) de deux nombres.

Le PGCD de a et de b est le plus grand nombre qui divise à la fois a et b.

Le PPCM de a et de b est le plus petit nombre qui est divisé à la fois par a et par b.

L'algorithme d 'Euclide, basé sur l'utilisation de la division euclidienne permet de déterminer le PGCD de deux nombres a et b.

Soient a= 540 et b = 231.

540 divisé par 231 donne 2, reste 78; 540 = 231 x 2 + 78.

231 divisé par 78 donne 2, reste 75 ; 231 = 78 x 2 + 75 78 divisé par 75 donne 1, reste 3 ; 78 = 75 x 1 + 3 75 divisé par 3 donne 25, reste 0 ; 75 = 3 x 25 +o.

Le dernier reste , 3, est le PGCD de 540 et 231.

On peut alors en déduire le PPCM de 540 et 231.

Il suffit de diviser le produit des deux nombres a et b par le PGCD .

Le PPCM de 540 et 231 est donc 41 580.

Une propriété intéressante du PGCD est l'identité de Bézout : Si d = PGCD ( a , b), il existe deux nombres u et v tels que d = a.u + b.v.

Par exemple, le PGCD de 14 et 10 est 2, donc il existe deux nombres tels que 2 = 14 x u + 10 x v, ce qui n 'est pas évide nt a priori.

Par exemple : u = 2 et V=-3.

Si le PGCD de deux nombres est égal à 1, on dit que ces deux nombres sont premiers entre eux.

Ils n 'ont alors aucun diviseur commun autre que 1 et eux-même.

NOMBRES PARFAITS ET NOMBRES AMIABLES Introduits par Pythagore , les nombre s parfaits et amiables sont parmi les premières notions arithm étiques inventées.

Un nombre est parfait s'il est égal à la somme de ses diviseurs.

Ainsi, 6 est un nombre parfait.

En effet, les diviseurs de 6 sont 1, 2, 3 et 6 = 1 + 2 + 3.

Il n'existe pas de nombre parfait impair inférieur à 10100, mais on ignore s'il en existe ou non au-delà.

Le plus grand nombre parfait connu est 1-------------_, 2756838 ( 275683' -1) et il est pair.

LA NUMÉRATION DANS UNE BASE L'adoption d'une base de numérat ion est un moyen pour n'utiliser qu'un petit nombre de symboles dans la représentation des nombres.

Au lieu de compter uniquement par unités (n = 1 + 1 + 1 + 1.

..

), on compte par «paquets».

On sait que les Babyloniens utilisaient le systè me sexagésimal (base 60), les Grecs se serva ient des lettres de l'alphabet, les Mayas utilisaient un système vicésimal (base 20).

Actuellement la numération décimale (base 10) est la plus largement répandue.

Elle fait intervenir dix symbo les distinct s, ou chiffres, pour représenter des nombres : 0, 1, 2, 3, 4, 5 , 6, 7, 8, 9.

Dans le système décimal, la quantité représentée par n'importe lequel des dix symboles en usage dépend de sa position dans le nombre.

Par exemple, le nombre 123 456 est une notation abrégée pour : 1 x 105 + 2x 10'+ 3 x 10' + 4 x 102 + 5 x 101 + 6 x 10" Pour certains usage s, on utilise toujours d'autres nombre s que 10 comme base car ils possèdent plus de diviseurs.

Par exemple, la base 60 et son sous­ multiple 12 s'avèrent très utile s pour subdiviser le temps .

Par ailleurs, le système binaire (base 2), avec le système de numération de base 16, est utilisé en informatique.

Si la somme des diviseurs d 'un nombre est supérieure à ce nombre , on dit qu'il est abondant.

On sait qu'il existe une infinité de nombres abondants (12, 18, 20 ...

).

Par exemple , les diviseur s de 12 sont 1, 2, 3, 4, 6 et 12 < 1 + 2 + 3 + 4 + 6 = 16.

Dans le même esprit , deux nombres sont amiables si la somme des diviseurs de l'un est égale à l'autre .

Les grecs ne connaissaient que les deux plus petits nombres amiab les : 220 et 284.

Les diviseurs de 220 sont 1 , 2, 4, 5, 10, 11, 20, 22, 44, 55, 110, dont la somme est 284.

Quant aux diviseurs de 284, qui sont 1, 2, 4, 71 et 142, leur somme n'est autre que 220.

LES NOMBRES PREMIERS Les nombre s premiers sont les nombres les plus importants en arithmétique.

Un nombre est premier lorsqu'il n 'est pas le produit de deux nombres plus petits, c'est-à-dire que ses seuls diviseurs sont 1 et lui-même .

THÉORÈME FONDAMENTAL DE L'ARITHMÉTIQUE Depuis Euclide , on sait que tous les nombres peuvent être décomposés en un produit fini de nombres premier s.

Ainsi, sin désigne un nombre entier quelconque et « 2, 3, 5, 1 ..

.

» la suite des nombr es premiers , alors il existe des exposants (nombres entie rs) i, j, k, 1.

..

tels quen =p,'p,i.

..

= 2 '3 '5'71 ••• Par exemple , 540 = 22335', tous les exposants des autres nombres premiers étant nuls (un nombre élevé à la puissance 0 donne 1).

Chaque exposant désigne donc le nombre de fois que le facteur premier correspondan t apparaît dans la décomposition.

Ce théorème montre que les nombres premiers sont comme les briques élémentaires des autres nombres .

On sait qu'il existe une infinité de nombres premiers mais leur apparition dans la suite des nombres entiers semble aléatoire.

en outre , il n 'existe aucune méthode pour en construi re, bien que de nombreux mathématiciens s'y soient essayés.

NOMBRES DE FERMAT Par exemple, Pierre de Fermat , en décrivant les nombres de Fermat qui sont de la forme F , = 22 " + 1, croyait avoir une formule donnant les nombres premiers.

Mais si F0 = 3, F1 = 5 , F2 = 17, F 3 = 257 et F 4 = 65 537 sont premiers , F 5 ne l'est pas, ainsi que de nombreux autres.

Il a fallu deux ans de calculs pour montrer que F u n'est pas premier.

Ces nombre s ont également d'autres applications, en particulier dans la construction des polygones réguliers.

NOMBRES DE MERSENNE Mersenne (1588-1648) a également décrit les nombre s de Mer senne de la forme M = 2 '- 1, dont il croyait qu'ils étaient premier s si p l'était, ce qui est faux .

Par contre, si M est un nombre premier , alors p l'est également , mais la réciproque est fausse : par exemp le, si p = 11, alors M = 2 047 = 23 x 89.

Néanmoins , les nombres premiers de Mersenne présentent certaines propriétés remarquables .

Une propriété énonce que si M est un nombre premier de Mersenne , alors le nombre M(M + 1)/ 2 est un nombre dit «parfait », c'est-à-dire égal à la somme de ses diviseurs propres .

Les nombres de Mersenne ont aussi permis de construire de nombreux grands nombres premier s.

Le plus grand nombre premier connu à ce jour est un nombre de Mersenne (2" "'"' -1 ), il possède 7 235 733 chiffres et a été découvert le 28 mai 2004 par le GIMPS (Great Internet Prime Search) grâce au calcul partagé sur Internet.

«THÉORÈME DE RARÉFACTION DES NOMBRES PREMIERS» M ême si la distribution des nombre s premiers parmi les nombres entiers naturels semble aléatoire , les nombres premiers obéissent pourtant à des lois très précises .

Ainsi, le théorème de raréfaction des nombres premiers affirme que pour un entier n donné , la quantité de nombres premiers inférieurs à n est à peu près n/log(n) .

Conjecturé par Gauss et Legendre , ce théorème fut démontré indépendamment la même année par Hadamard et de La Vallée-Poussin en 1896 .

INDICATEUR D'EULER Pour un entier n, l'indicateur d'Euler (n) est la quantité de nombres premiers avec n , inférieurs à n .

Il est égal à : (n)=n(l -1/p 1)(1-1/p 2) .•• (1 -1/p,) où n = p1' p,i.

..

est la décomposition de n en fadeurs premiers .

Par exemple, pour n = 10 : 10= 2 x 5 ;p , = 2 etp 2 = s (n) = 10(1 -1/ 2)( 1 -1/5) = 4.

Cette fonction possède de nombreuses propriétés intéressantes , et son étude a donné lieu à de nombreux résultats.

Il existe également encore des questions ouvertes liées à q,, comme par exemple la conjecture de Carmichaël qui affirme que. »