NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 24/10/2016

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

Théorie des Nombres

 

Débutants

Général

DIVISIBILITÉ

 

Glossaire

Général

 

 

INDEX

 

Calcul

 

Théorie des nombres

 

PGCD

Algorithme d'Euclide

Premiers entre eux

PPCM

Pgcd / Ppcm / Racine

Sommaire de cette page

>>> Approche

>>> Premiers entre eux

>>> Propriétés – Particulières

>>> Propriétés – Générales

>>> Premiers par paires

>>> Théorème de Cesaro

>>> Propriétés avec somme, différence et produit

>>> Somme et différence: a + b et a – b

>>> Somme et produit: a + b et ab

>>> Avec des carrés

 

 

 

 

NOMBRES PREMIERS ENTRE EUX

ou ÉTRANGERS

 

On connaît les nombres premiers.

 

On peut étendre cette notion à des groupes de nombres.

 

Lorsqu'on cherche à rendre une fraction irréductible, les nombres au numérateur et au dénominateur sont premiers entre eux.

 

30

=

2 x 3 x 5

=

3

3 et 7 sont étrangers

ou premiers entre eux (PEE)

70

2 x 5 x 7

7

 

Deux nombres premiers sont toujours étrangers.

Exemple: 11 et 13

 

Mais, ceci n'est pas nécessaire.

Exemple: 8 et 9 sont étrangers sans être premiers ni l'un ni l'autre.

Deux nombres étrangers n'ont pas de diviseurs communs.
Leur plus grand commun diviseur (PGCD) est 1.

 

Notation abrégée:  (a , b) = 1

 

 Anglais: a and b  are relatively prime or coprimes.

 

 

 

Approche

A, B, C …. sont premiers entre eux s'ils n'ont que 1 comme diviseur commun.

PGCD (A, B, C …) = 1

 

 

 A = 11

= 1 x 11

B = 21

= 1 x 3 x 7

PGCD (A, B)

= 1

 On dit que:

11 et 21 sont premiers entre eux

ou étrangers

 

  

A = 11

= 1 x 11

B = 21

= 1 x 3 x 7

C = 25

= 1 x 5 x 5

PGCD (A, B, C)

= 1

 

 

 

 

Approche illustrée

 

Deux nombres sont premiers entre eux si le segment qui les représente (en rouge) ne passe par aucun point de la grille. Dans le cas contraire (en vert), le premier point d'intersection (vert) représente deux nombres effectivement premiers entre eux.

 

 

 

Table des PGCD & nombres étrangers

 

Établissons la table des PGCD

& Observons

 

*    La symétrie du tableau

Car PGCD (A, B) = PGCD (B, A).

*    Les enfilades de 1 lorsque le nombre est premier jusqu'à rencontrer son multiple.

Voir 7 en particulier.

*    Les cycles sur les lignes n : le motif se répète avec une période égale à n.

En ligne 3, on trouve: 1, 1, 3, 1, 1, 3 ….

*    Mêmes cycles sur les colonnes.
Du fait de la symétrie du tableau.

 

 

PGCD des nombres de 1 à 10

 

 

1

2

3

4

5

6

7

8

9

10

1

1

1

1

1

1

1

1

1

1

1

2

1

2

1

2

1

2

1

2

1

2

3

1

1

3

1

1

3

1

1

3

1

4

1

2

1

4

1

2

1

4

1

2

5

1

1

1

1

5

1

1

1

1

5

6

1

2

3

2

1

6

1

2

3

2

7

1

1

1

1

1

1

7

1

1

1

8

1

2

1

4

1

2

1

8

1

2

9

1

1

3

1

1

3

1

1

9

1

10

1

2

1

2

5

2

1

2

1

10

 

On laisse en blanc les cases

des nombres premiers entre eux.

 

 

Grilles des premiers en eux (PEE en noir)

 

  

Ces grilles sont symétriques par rapport à la diagonale descendante.

 

Zones de carrés blancs: nombres successifs non premiers entre eux

 

Le cercle rouge indique le premier carré 2x2 avec quatre nombres non-PEE. Coordonnées du coin: (14, 20). Illustration ci-dessous.

Le premier carré 3x3 non-PEE est en (104, 6 200):

 

Recherche d'un carré 3x3

Prenons n et m impairs. Alors, les quatre coins seront pairs. Sur la colonne centrale, n est impair, prenons 3 et pour les deux autres facteurs 5 et 7 et voyons. n = 3 x 5 + 7 = 105.

Alors n -1 = 104 = 23 x 13 et 106 = 2 x 53. Ce qui induit que m = k x 3 x 13 x 53 = 2 067. Un essai montre que k = 1 ou 2 ne conviennent pas et que k = 3 donne une solution.

On imagine que cet exemple est le plus petit. Une exploration par programme le confirme.

 

 

 

Table des nombres premiers entre eux jusqu'à 50

Lecture: n = 10; il y a quatre premiers avec 10; ce sont: 1, 3, 7, 9 dont 3 et 7 sont premiers (rouge)

 

Voir Tables

 

Une liste très militée

Nombres dont tous les premiers avec eux sont également premiers

(ligne jaune avec tous les nombres en rouge):

2, 3, 8, 12, 18, 24, 30.

Et c'est tout!

 

 

 

Propriétés particulières

 

Propriété

n et

n + 1

2n + 1

k.n + 1

Sont

premiers

entre eux.

 

 

 

Exemple

n

m = k.n + 1

PGCD (n, m)

7

8

1

15

1

22

1

29

1

36

1

43

1

50

1

57

1

64

1

71

1

 

 Fibonacci

 

Fn et Fn+1 sont premiers entre eux.

 

Deux termes voisins de la suite de Fibonacci  sont premiers entre eux.

 

Exemple

1

1

2

3

5

8

13

21

34

55

 

 

P

 

 

 

 

 

 

 

 

 

 

P

P

 

 

 

 

 

 

 

 

 

 

P

P

 

 

 

 

 

 

 

 

 

 

P

23

 

 

 

 

 

 

 

 

 

 

23

P

 

 

 

 

 

 

 

 

 

 

P

3.7

 

 

 

 

 

 

 

 

 

 

3.7

2.17

 

 

 

 

 

 

 

 

 

 

2.17

5.11

 

 

 

 

Propriétés générales

Théorème de caractérisation

des nombres premiers entre eux

 

S'il existe deux nombres x et y

tels que ax + by = 1

alors a et b sont premiers entre eux 

a et b > 0.

 

 

 

Démonstration

Directe

 

Si a et b premiers entre eux

PGCD = 1

Théorème de Bachet - Bézout

Il existe x et y tels que

 

ax + by = 1

Inverse

 

S'il existe x et y tels que

ax + by = 1

Si d divise a et b , il divise aussi

ax et by

Donc d divise

ax + by

Or

ax + by = 1

Si d divise l'unité,

 il ne peut être que

1

Et

a et b sont premiers entre eux

 

Puissances

 

Voir Autres propriétés

 

 

 

 

Premiers par pairesNombres a1 , a2 , … , an

Général

Par paires

 

*    Nombres premiers entre eux.

*    Nombres étrangers.

*    Relatively prime.

*    Ils sont tous premiers entre eux.

 

Anglais: Coprime

 

( a1 , a2 , … , an ) = 1

 

 

*    Nombres premiers entre eux par paires.

*    Nombres étrangers par pairs.

*    Relatively prime in pairs.

*    Ils sont premiers entre eux deux par deux.

 

Pairwise coprimes

 

( ai , aj ) = 1

pour tous

 

 

 

Théorème de Cesaro

0,607927102 …

 

*      Probabilité que deux nombres n'aient aucun diviseur commun. Cad: Probabilité que deux nombres pris au hasard soient premiers entre eux.

*      Probabilité qu'un nombre ne soit pas divisible par un carré.

*      Densité asymptotique des nombres sans carré.

 

Théorème de Cesàrio (1859-1906), démontré en 1881).

 

Pour tout n, la probabilité Pn que deux nombres entiers choisis au hasard et inférieurs à n soient premiers entre eux est exprimée par la limite suivante:

 

Le calcul de zêta (2) = pi/6, dit problème de Bâle, est dû à Euler en 1735.

 

 

 

 

Résumé des propriétés

 

(voir ci-dessous)

que si a et b sont

de parité opposée

(voir ci-dessous)

 

 

Exemples de calculs  (PEE = premiers entre eux)

 

 

Si a et b sont PEE, alors a et b sont PEE avec la somme d'une part et avec la différence d'autre part.

 

 

 

 

On sait que a et b sont PEE:: a ne divise pas b et b ne divise pas a.

 

Avec a + b,

*       a divise le premier terme mais pas le second;

*       b divise le second pas le premier.

*       a + b est premier avec a et avec b.

Même chose avec a – b

 

Démonstration alternative

 Relation de Bézout: au + bv = 1

au + bv + av – av = 1

au – av + av + bv = 1

a(u – v) + (a + b)v = 1

aU + (a + b)V = 1

Les nombre a et a + b sont PEE.

 

 

 

Si a et b sont PEE et de parité opposée, alors leur somme et différence sont PEE.

 

 

 

Exemples

a et b étant PPE

 

Lorsque la parité est opposée, la somme et la différence sont PPE.

 

Examinons la parité

*       Si a et b sont pairs, somme et différence sont paires et ne sont donc pas PEE (Voir le rappel en pied de chapitre).

*       Si a et b sont impairs, somme et différence sont paires et ne sont donc pas PEE.

*       Pour que somme et différence soient PEE, il est nécessaire que a et b soient de parité opposée.

*       Mais ce n'est pas suffisant comme le montre cet exemple: 6 + 3 = 9 et 6 – 3 = 3. On constate que dans ce cas les nombres a = 6 et b = 3 sont bien de parité opposée, mais (a et b) comme (a+b et a–b) ne sont pas PEE.

 

Nécessité d'être premiers entre eux

Donc a et b doivent être de parité opposée; mais, que faut-il en plus?

Prenons le cas où a et b partagent un facteur commun g.

a = ga' et b = gb'

Alors:

a + b = g (a' + b')

a – b = g (a' – b')

Somme et produit partagent aussi ce même facteur commun, et ils ne sont donc pas PEE. Pour être PEE, il faut que g = 1. Ce qui veut dire que les nombres a et b doivent être aussi PEE.

 

Rappel

Supposons a et b de même parité.

Si pairs (P):

a + b  P + P  P

a – b  P – P  P

Si impairs (I):

a + b  I + I  P

a – b  I – I  P

Si a et b sont de même parité alors a + b comme a – b sont divisibles par 2.

 

 

Somme et produit

 

Théorème

 

Si a et b sont PEE,

alors a.b et a+b sont PEE.

 

Rappel du lemme d'Euclide

Si p, un nombre premier divise a.b, deux nombres entiers relatifs, alors p divise a ou b.

 

 

 

 

Démonstration 1

Supposons que p, un nombre premier, divise a.b et a + b

Si p divise a.b, il divise a ou b; disons a (sinon, on inverse).

Or p divise (a + b), il divise déjà a, il doit aussi diviser b. On peut le monter en faisant p diviser la somme algébrique: (a+b) – a = b.

Divisant à la fois a et b, p serait un facteur commun. Ce qui contraire à notre hypothèse.

Alors p = 1 et a.b est a + b sont PEE.

 

Rappel sur la relation de Bézout

Les nombres a et b sont PEE, si et seulement s'il existe deux nombres entiers relatifs (u et v) tels que:

au + bv = 1

 

 

Démonstration 2

au + bv = 1

(au + bv = 1

(au)² + 2aubv + (bv = 1

Suite

(au)² + 2aubv + (bv + abu² – abu² + abv² - abv²   = 1

a²u² + abv² + abu² + b²v² – abu² + 2abuv – abv² = 1

(a + b) (au² + bv²) – ab (u – v)² = 1

(a + b) U + ab V = 1

Bézout => a + b et a.b sont PEE

 

 

Avec des carrés

 

Théorème

 

Si a et b sont PEE,

alors a+b et a² – ab + b² sont PEE

ou divisible par 3

 

 

Soit d un diviseur commun à a + b et a² – ab + b², alors:

d | a + b  et d | a² – ab + b²

d | (a + b et d | a² – ab + b²
d | (a + b)²
(a² – ab + b²)
d | 3ab

Nous avons vu que si a et b sont PEE, alors a + b et ab son PEE: la somme et le produit n'ont aucun facteur en commun.

Or d divise la somme, il ne divise pas le produit

(a + b, ab) = 1

d | a + b  => d ab

Avec le lemme d'Euclide:

d | 3 => d = 1 ou 3

Deux exemples

1 + 5 = 6, 1² – 5 + 25 = 21 et (6, 21) = 3

1 + 6 = 7, 1² – 6 + 36 = 31 et (7, 31) = 1

 

 

 

 

 

Suite

*    Propriétés des nombres premiers entre eux

Voir

*    Diviseurs: calculs et facteurs premiers

*    Divisibilité dans une suite de nombres

*    Quantité de nombres premiers avec n

*    Totient d'Euler

*    Théorie des nombres Index

*    Diviseurs: nombres parfaits

*    Nombres Premiers

*    Pseudo Premiers

*    Pseudo Premiers Absolus

*    Fraction continue

DicoNombre

*    Nombre 0,607 …

Cette page

http://villemin.gerard.free.fr/ThNbDemo/PremEEux.htm