Nombres premiers entre eux

Définition : nombres premiers entre eux

Deux entiers sont premiers entre eux (ou étrangers) si leur PGCD (ou plus grand commun diviseur) est égal à 1.
Une définition équivalente : 2 nombres sont premiers entre eux s'ils n'ont aucun facteur (diviseur) premier commun.

Exemple : 15 et 63 sont premiers entre eux car,

15 = 3 x 5, les facteurs premiers de 15 sont 3 et 5
63 = 7 x 9, les facteurs premiers de 63 sont 7 et 9

Pour factoriser un nombre, on peut utiliser ce calculateur Factoriser un nombre.

Ces 2 entiers n'ont pas de facteur commun donc ils sont premiers entre eux.
A contrario, 15 et 50 ne sont pas premiers entre eux car ils ont un facteur commun qui est 5 !

Généralisation à une liste de plusieurs entiers

La définition ci-dessus, valable pour 2 entiers, peut être généralisée à 3, 4, 5... N entiers. Ainsi, des nombres entiers sont dits premiers entre eux si leurs PGCD est égal 1. De manière équivalente, ils sont pemiers entre eux s'ils n'ont pas de facteurs (diviseur) premier commun.

Exemple : 6, 35 et 20 sont premiers entre eux car,

6 = 3 x 2, les facteurs sont 2 et 3
35 = 5 x 7, les facteurs 5 et 7
20 = 5 x 2 x 2, les facteurs sont 2 et 5

Ces 3 entiers n'ont pas de facteur commun donc ils sont premiers entre eux.
On remarquera que 2 est un facteur commun entre 6 et 20 mais il n'est pas un facteur de 35. Donc, 2 n'est pas un facteur commun aux 3 entiers !
A contrario, 6, 20 et 100 ne sont pas premiers entre eux car ils ont un facteur commun qui est 2 !

Comment savoir si 2 nombres sont premiers entre eux ?

Il existe plusieurs méthodes pour savoir si deux ou plusieurs entiers sont premiers entre eux.

Méthode utilisant le PGCD
On calcule le PGCD des entiers en question. S'il est égal à 1 alors les nombres sont premiers entre eux.

Exemple 1
PGCD(16,56,85) = 1, donc les entiers 16, 56 et 85 sont premiers entre eux.

Exemple 2
PGCD(22,143,55) = 8, donc les entiers 22, 143 et 55 ne sont pas premiers entre eux.

Méthode par décomposition en facteurs premiers
On décompose ces entiers en facteurs premiers (factorisation), les nombres sont premiers entre eux s'ils n'ont pas de facteur premier commun.
On reprend les mêmes exemples que ci-dessus.

Exemple 1
16 = 2 x 2 x 2 x 2
56 = 2 x 2 x 2 x 2 x 7
85 = 5 x 17

On remarque qu'il n'y a pas de facteur commun entre les 3 nombres, donc 16, 56 et 85 sont premiers entre eux.

Exemple 2
22 = 11 x 2
143 = 11 x 13
55 = 11 x 5

On remarque que 11 est un facteur commun entre les 3 nombres, donc 22, 143 et 55 ne sont pas premiers entre eux.

Euclide étendu ou théorème de Bezout

En utilisant, le théorème de Bezout (ou Euclide étendu), on peut déduire une autre définition de 2 nombres premiers entre eux.
2 nombres a et b sont premiers entre eux si et seulement s'il existe 2 entiers relatifs u et v tels que,

`a*u + b*v = 1`

Cette propriété est importante car très utilisée dans la théorie des nombres.

Programmation

Python

Ce programme en python teste si deux nombres entiers a et b sont premiers entre eux. La fonction "premiers_entre_eux" retourne une variable de type booléen : True (si a et b sont premiers entre eux) ou False dans le cas contraire.

- On utilise la fonction pgcd en python et on utilise la défnition : deux nombres sont premiers entre eux si et seulement si leur PGCD (Plus Grand Commun Diviseur) est égal à 1.

- L'opérateur % désigne le reste de la division euclidienne.

def premiers_entre_eux(a,b):
    if( pgcd(a,b) == 1 ):
	    return True
    return False

def pgcd(a,b):
	while b:
		a, b = b, a%b
	return a

Voir aussi

Factoriser un nombre
PGCD
Trouver les diviseurs d'un nombre
Théorème de Bezout (ou Euclide étendu)