Nombres premiers

Définition:
On appelle nombre premier tout nombre distinct de 1 qui n'est divisible que par 1 et lui-même.

(Rappel: on entend par "divisible" que la division euclidienne tombe juste)

Exemples: 2 n'est divisible que par 1 et 2 ; 2 est un nombre premier.

3 n'est divisible que par 1 et 3 ; 3 est un nombre premier.

4 est divisible par 1, 2 et 4 ; 4 n'est pas un nombre premier.

5 n'est divisible que par 1 et 5 ; 5 est un nombre premier.

6 est divisible par 1, 2, 3 et 6 ; 6 n'est pas un nombre premier.

Une méthode fort ancienne de détermination systématique des nombres premiers est:

Le Crible d'Eratosthène.

Il est, par ailleurs, assez aisé de démontrer que le nombre de nombres premiers est infini (si vous en souhaitez une démonstration, cliquez ici), mais il demeure assez fastidieux de déterminer un par un les nombres premiers en les passant au crible .

Pour décomposer des nombres en facteurs premiers,
voici un petit programme écrit en javascript:

Définition:
On dit que deux nombres sont premiers entre eux lorsque leur seul diviseur commun est 1.

Exemples: Les diviseurs de 10 sont 1, 2, 5 et 10.

Les diviseurs de 63 sont 1, 3, 7, 9, 21 et 63.
1 est le seul diviseur commun à 10 et à 63.
10 et 63 sont donc premiers entre eux.
Attention: Ni 10, ni 63 ne sont pour autant des nombres premiers.

Les diviseurs de 42 sont 1, 2, 3, 6, 7, 14, 21 et 42.
Les diviseurs de 66 sont 1, 2, 3, 6, 11, 22, 33 et 66.
1, 2, 3 et 6 sont des diviseurs communs à 42 et à 66.
Le plus grand d'entre eux, 6, est appelé PGCD (Plus Grand Diviseur Commun) des nombres 42 et 66.

Pour décomposer déterminer le PGCD de deux nombres par l'Algorithme d'Euclide,
voici un petit programme écrit en javascript:

Exemples:	2 n'est divisible que par 1 et 2	;	2 est un nombre premier.
	3 n'est divisible que par 1 et 3	;	3 est un nombre premier.
	4 est divisible par 1, 2 et 4	;	4 n'est pas un nombre premier.
	5 n'est divisible que par 1 et 5	;	5 est un nombre premier.
	6 est divisible par 1, 2, 3 et 6	;	6 n'est pas un nombre premier.

Exemples:		Les diviseurs de 10 sont 1, 2, 5 et 10.
		Les diviseurs de 63 sont 1, 3, 7, 9, 21 et 63. 1 est le seul diviseur commun à 10 et à 63. 10 et 63 sont donc premiers entre eux. Attention: Ni 10, ni 63 ne sont pour autant des nombres premiers.

		Les diviseurs de 42 sont 1, 2, 3, 6, 7, 14, 21 et 42. Les diviseurs de 66 sont 1, 2, 3, 6, 11, 22, 33 et 66. 1, 2, 3 et 6 sont des diviseurs communs à 42 et à 66. Le plus grand d'entre eux, 6, est appelé PGCD (Plus Grand Diviseur Commun) des nombres 42 et 66.