Identité de Brahmgupta et factorisation

Lestics · September 2020

Bonjour
Je me permet d’ouvrir ce thread car je n’arrive pas à retrouver ma bêtise sur le net et ça me frustre beaucoup car tout ce que j’ai fait c’est multiplier 3 et 7 à partir de cette identité.

For example, let's consider the integers 1, 2, 3, and 4:
(1² + 2²)(3² + 4²) = (1*3 + 2*4)² + (1*4 - 2*3)² = 11² + 2² = 125
(1² + 2²)(3² + 4²) = (1*3 - 2*4)² + (1*4 + 2*3)² = 5² + 10² = 125
https://brilliant.org/wiki/diophantus-identity/

Du coup c’est tout pareil à deux trois nuances près:
3 = 2² - 1²
7 = 4² - 3²
(2² - 1²)(4² - 3²) = (2*4 + 1*3)² - (2*3 + 1*4)² = (8 + 3)² - (6 + 4)² = 11² - 10² = 1*21
(2² - 1²)(4² - 3²) = (2*4 - 1*3)² - (2*3 - 1*4)² = (8 - 3)² - (6 - 4) ² = 5² - 2² = 3*7

Et j’aimerais bien savoir en plus sur cette histoire. J’aimerais bien savoir ce que des vrais mathématiciens proposent comme méthode de factorisation à partir de cette variante. Parce que retrouver 11² - 10² c’est un jeu d’enfant, il suffit de diviser par 2 et d’ajouter 0,5 de côté et d’enlever 0,5 de l’autre et partant de là le but du jeu c’est de retrouver les deux deux paires de paires donc une approche naïve consiste à faire la liste de tous les possibles.
11+0, 10+1, 9+2, 8+3, 7+4, 6+5
10+0, 9+1, 8+2, 7+3, 6+4, 5+5
Puis à transformer les “+” en “*” ce qui nous donne:
0, 10, 18, 24, 28, 30
0, 9, 16, 21, 24, 25
Et comme on retrouve le 24 dans les séries on sait que la paire de paires qu’on recherche correspond à (8+3) et (6+4) donc on transforme le “+” en “-” et ça permet de retomber sur le 5 et le 2 qui permettent de construire le 3*7. Ceci dit j’imagine qu’il doit y avoir des méthodes un peu plus élégante pour exploiter cette affaire mais faute de savoir quoi taper dans Google pour retrouver ma bêtise je patauge un peu. Du coup je me demandais si vous auriez une idée de ce que je dois entrer dans Google pour retrouver ma bêtise et en savoir plus.

En vous remerciant d’avoir pris la peine de lire puis en espérant que même si ça doit être plus que basique pour vous tous vu le niveau du forum l’un de vous aura quand même cinq minutes à perdre avec moi.
Merci !

bisam · September 2020

Naïvement, je dirais que ton "algorithme" de factorisation n'a pas beaucoup d'intérêt car, même si les idées qu'il présente sont simples, le nombre de calculs à effectuer est du même ordre de grandeur que $N$ le nombre à factoriser.

Par exemple, pour factoriser $N$, il faut d'abord déterminer la liste des couples $(\frac{N-1}{2}-k,k)$ et $(\frac{N+1}{2}-k,k)$ pour $k$ variant de $1$ à $\frac{N-1}{2}$, puis déterminer s'il existe une valeur commune entre les deux listes des produits correspondants, donc calculer les $N$ produits correspondants et les comparer.
Comme les deux listes sont classées, il est facile de les fusionner en $O(N)$ pour effectuer cette comparaison.

Si on a trouvé une valeur commune, on obtient une factorisation.
Cependant, le nombre d'opérations effectuées est du même ordre de grandeur que la division naïve pas tous les nombres plus petits que $N$.... donc ce n'est pas intéressant.

Lestics · September 2020

J’aimerais bien savoir ce que des vrais mathématiciens proposent comme méthode de factorisation à partir de cette variante. a écrit:

Ceci dit j’imagine qu’il doit y avoir des méthodes un peu plus élégante pour exploiter cette affaire mais faute de savoir quoi taper dans Google pour retrouver ma bêtise je patauge un peu. a écrit:

C'est ça la question, pas de savoir si ma version naive est efficace.

Fin de partie · September 2020

Lestics a écrit:

J’aimerais bien savoir ce que des vrais mathématiciens proposent comme méthode de factorisation à partir de cette variante.

Ils ne proposent rien parce qu'ils ont dans leur musette des méthodes beaucoup plus efficaces. B-)-

PS:
Par ailleurs,
$a^2-b^2=(a+b)(a-b)$

PS2:
Il me semble qu'il y a une méthode de factorisation qui exploite l'identité ci-dessus.
En effet, si $N$ est un entier impair, sauf erreur, on peut toujours l'écrire comme une différence de carrés.

Lestics · September 2020

L'intuition est la suivante. Tout entier naturel impair N se décompose en la différence de deux carrés : N = a2 – b2. Algébriquement, cette différence se factorise en (a + b)(a – b) et, si ni a + b ni a – b n'est égal à 1, alors ce sont des facteurs non triviaux de N. a écrit:

https://fr.wikipedia.org/wiki/Méthode_de_factorisation_de_Fermat#:~:text=En arithmétique modulaire, la méthode,premiers d'un entier naturel.

Et bon même si on a des méthodes beaucoup plus efficaces que celle de Fermat la méthode de Fermat est référencée donc je ne vois pas pourquoi celle que je présente ne serait pas référencée quelque part. Quelque chose d'aussi simple a forcément été déjà relevé par quelqu'un.

Fin de partie · September 2020

Lestics:

L'identité de Brahmagupta
$(ac+nbd)^2-n(ad+bc)^2=(a^2-nb^2)(c^2-nd^2)$

Je l'ai mise dans le "sens" dans lequel tu veux l'utiliser.

Tu as un nombre $N$ et tu veux pouvoir trouver $a,b,c,n$ des entiers tels que $N=(ac+nbd)^2-n(ad+bc)^2$

Par exemple, si tu fixes la valeur $n=1$ cette identité ne sert à rien car on a $u^2-v^2=(u+v)(u-v)$
Et si $N$ est impair on peut toujours trouver $a,b$ entiers tels que $N=u^2-v^2$.

Si $n=-1$ puisqu'on ne peut pas écrire tous les entiers $N$ comme somme de deux carrés on ne peut pas toujours écrire $N$ sous la forme de la somme de deux carrés et donc on ne va pouvoir toujours trouver $a,b,c,d$

Déjà savoir quelle valeur de $n$ on va utiliser ce n'est pas si simple à déterminer me semble-t-il.

PS:
Pourquoi se limiter à ce type d'identité?

Si un polynôme $P$ à plusieurs variables $x_1,x_2,...,x_n$ à coefficients entiers est le produit de deux polynômes à plusieurs variables à coefficients entiers et si on peut trouver des valeurs $x_1,x_2,....,x_n$ entiers telles que $N=P(x_1,x_2,..x_n)$ on tient une factorisation de $N$ (qui peut être $1\times N$)
Le problème est, comment choisir le polynôme $P$?

Identité de Brahmgupta et factorisation

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 29