NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 05/05/2020

Orientation générale        DicoMot Math          Atlas                   Actualités                       M'écrire

Barre de recherche          DicoCulture              Index alphabétique        Références      Brèves de Maths

      

Partitions

 

Débutants

Addition

Variations sur les carrés

 

Glossaire

Addition

 

 

INDEX

PARTITION

 

Carrés

Chiffres répétés

Repdigits

Produits

66 x 67 …

66 x 99 …

Factorisation

Sommes

Somme double

 

Factorisation – Algorithme

Différences

Propriétés

Écart 1, 2, …

Trouver la dif. des carrés

Table 1 à 100

Repdigits

Table des Repdigits

Curiosités

Tableau synthèse

a² – b² = c² – d²

 

Sommaire de cette page

>>> Approche

>>> Théorème de la factorisation

>>> Une méthode algorithmique de factorisation

 

 

 

 

 

 

FACTORISATION des nombres

différence de deux carrés

Algorithme

 

Une méthode originale proposée par Olivier Mehaye. Il s'agit d'un algorithme de recherche d'un élément commun dans deux suites de nombres.

Son fondement est exposé en Différence des carrés de deux nombres et une approche avec des factorisations particulières est expliquée en Factorisation.

 

 

 

Approche de la factorisation d'un nombre composé

Une approche originale  de factorisation.

 

Le but est de connaitre la factorisation de p = a.b

Exemple avec p = 21 dont on cherche à trouver la factorisation: 3 x 7.

 

Procédé

Former deux suites de nombre en choisissant p et en faisant progresser n.

*      La suite T est égale à p auquel on ajoute le carré de n: T(n) = p + n²

*      La suite T' est égale à 2p auquel on ajoute le carré de m: T'(m) = 2p + n².

 

On repère le cas où T(n) = T'(m).  C'est le cas pour n = 5 et m = 2 avec la même valeur 46.

 

La factorisation est simplement donnée par la somme et la différence entre ces deux nombres.

 

 

Formation des deux suites T et T'

n

0

1

2

3

4

5

0

1

4

9

16

25

T

21

22

25

30

37

46

T'

42

43

46

51

58

67

 

46 = 21 + = 2x21 +

Factorisation

21 = (5 – 2) (5 + 2) = 3 x 7

 

 

Théorème de la factorisation

Cette approche est astucieuse et marche pour presque tous les nombres.

 

Une vérification par tableur semble montrer que l'on trouve toujours une égalité et que:

p = (n – m) (n + m)  = s . e 

 

En fait, chercher l'égalité revient à résoudre cette équation dont la solution s'exprime par le produit d'une somme et d'une  différence des mêmes nombres.

 

 

p + n² = 2p + m²

n² – m² = p

p = (n – m) (n + m)

 

Notez que l'on n'a fait aucune hypothèse sur la nature du nombre p

Le tableau montre les nombres p atteint par cette relation entre m et n. Ils sont pairs comme impairs, mais … on y trouve:

*      tous les impairs et,

*      certains pairs.

Les nombres impairs y sont au moins une fois sur la deuxième diagonale.

Les nombres pairs multiples de 4, sauf 4, y sont tous sur la troisième diagonale. Les autres pairs n'y sont jamais

 

  Suite en Différence des carrés de deux nombres

 

Table de p = (n – m) (n + m)

n

m

1

2

3

4

5

6

7

8

9

1

0

3

8

15

24

35

48

63

80

2

0

5

12

21

32

45

60

77

3

0

7

16

27

40

55

72

4

 

0

9

20

33

48

65

5

 

 

 

0

11

24

39

56

 

Les absents du tableau

Les nombres pairs non multiples de 4

 

Théorèmes

TOUT nombre est égal à une différence de carrés, au moins. SAUF, les nombres en 4k + 2 et les nombres: 1, 2, 4.

 

Conséquence

TOUT nombre impair, comme tout nombre premier (sauf 2), comme tout produit de nombres premiers (sauf avec 2) sont:

*      la différence de deux carrés, et

*      le produit de la somme et de la différence de deux mêmes nombres.

 

 

p = n² – m² = (n – m) (n + m) = s . e

avec n = (s + e) /2 et m = (s – e) /2

 

Exemples

 

 

 

Une méthode algorithmique de factorisation

 

L'idée consiste à balayer deux listes jusqu'à détecter l'égalité entre deux éléments.

Hélas, il n'existe pas de formule analytique directe qui donnerait les valeurs de m et n, pas plus que celles des a et b.

Une méthode algorithmique s'impose. Le temps d'exploration restera néanmoins important pour de grands nombres. D'autres méthodes plus efficaces existent.

 

 

Une implémentation sur tableur est possible, mais on s'intéresse certainement à de grands nombres. La programmation est plus indiquée.

 

Programmation Python

 

 

 

 

But

Étant donné un nombre p, on se propose de trouver sa factorisation en deux facteurs.

Soit, trouver m et n et en déduire s et e:

p (n – m) (n + m) = s . e

 

Commentaires

On donne une valeur à p (volontairement un produit à fin de test). On vérifie tout de suite que le nombre p n'est pas de la forme 4k + 2.

La liste T est ouverte. Elle mémorisera les éléments de la liste qui croit le plus rapidement (n² + 2p).

Boucle (for …) qui calcule tt et t et conserve tt dans la liste T.

Si la nouvelle valeur de t est déjà dans la liste de tt, alors, on a trouvé notre égalité.

Le nombre m est le rang de la valeur commune dans la liste T.

Les nombres cherchés sont n et m puis a et b.

On imprime le résultat des recherches et on stoppe la recherche avec un break.

En bleu le résultat.

 

Programmation Maple

But

Identique

 

Commentaires

Initialisation par restart.

Même commentaires que ci-dessus.

 

Particularités

On demande la factorisation avec ifactor à titre de test.

Ajouter un élément à une liste se fait avec [op(liste), nouvel élément]

L'instruction member vérifie si un élément est dans la liste et en donne le rang en troisième paramètre (ici: m).

 

En bleu ce résultat.

Voir ProgrammationIndex

 

 

 

 

Retour

*    Différence des carrés de deux nombres

Suite

*    Table des différences de carrés de 1 à 100

*    S'y retrouver

Voir

*    AdditionGlossaire

*    Addition des carrés

*    Connaître les carrés des nombres

*    Machine des frères Carisan

*    TABLESIndex

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Addition/P100a500/FactAlgo.htm