Bezout et Fibonacci

donnet

Bonjour à tous 
je propose un petit exercice reliant les nombres premiers entre eux et ceux de Fibonacci

Soient Gi et Gi-1 deux nombres premiers entre eux dont les coefficients de Bezout Ki et Ki-1
sont deux nombres successifs de Fibonacci, i étant un élément de N.
Exprimer  Gi en fonction de i.
Indice : utiliser l'algorithme d'Euclide.

gerard0

Bonjour.

Il manque manifestement un élément dans cet énoncé, car i n'y est pas défini.

Cordialement.

donnet

Bonsoir Gérard,

il fait lire en fonction des Ki et non pas des i ;  mille excuses pour la coquille
 Il faut comprendre que i est un indice attaché au nombre G.

Voici quelques indices

 on construit l'algorithme d'EUCLIDE étendu théorique en partant du bas.
Pour ne pas être ambigu ces indices seront mis entre parenthèses.

G(1)=1
G(2)=G(1)*H(1)
G(3)=G(2)*H(2)+G(1)
G(4)=G(3)*H(3)+G(2)
..........

G(i)=G(i-1)*H(i-1)+G(i-2)

La résolution de cet algorithme théorique donnera les expressions des G(i) en fonction des H(i),H(i-1).....
Si K(i) et K(i-1) sont les coefficients de BEZOUT de l'équation
   G(i)*K(i-1)-G(i-1)*K(i)= +/-1
Ils s'exprimeront également en fonction des mêmes H(i),H(i-1).....

C'est un bon exercice de manipulation algébrique
Cette résolution de l'algorithme théorique donne des résultats  surprenants .
il ne faudra pas s'arrêter à la solution triviale où tous les H(i) sont égaux à 1
Les G(i) étant simplement  les nombres de FIBONACCI.

On devra trouver en résultats intermédiaires  K(2)=1   ; K(3)=1  ;  K(4)=2  K(5)=3  etc
Les curieux pourront aller plus loin en faisant varier les valeurs des H(i) et éventuellement partager leurs trouvailles

gerard0

C'est de moins en moins clair !

"Gi et Gi-1 deux nombres premiers entre eux dont les coefficients de Bezout Ki et Ki-1

sont deux nombres successifs de Fibonacci,"
" Il faut comprendre que i est un indice attaché au nombre G."
"G(1)=1
G(2)=G(1)*H(1)"

Finalement, tu nous dis que tu construis une suite de nombres qui ont la particularité que tu disais. Mais ce n'est pas ce que tu expliquais au premier message. Et c'est toujours cryptique, tu ne dis pas qui sont les H(i).

Pourrais-tu arrêter d'écrire pour toi et commencer à penser à communiquer ?
Rédiger de façon compréhensible pour les autres, donner la signification des notations, ...?

Lirone93

dont les coefficients de Bezout 

dont une paire de coeff ...

donnet

bonjour,

      Habituellement l'utilisation de l'algorithme d'EUCLIDE se fait en commençant par diviser le plus grand des deux nombres premiers entre eux
  par le plus petit ici G(i) par G(i-1)
      Chaque ligne  est de la forme G(i)=G(i-1)*H(i-1)+G(i-2) et représente la division euclidienne de G(i) par G(i-1) ,
  les" H(i-1)" en sont les dividendes et les "G(i-2)" en sont les restes qui  deviendront les diviseurs de la division suivante. G(i-1) par G(i-2)
      En général cette ligne reçoit le numéro du nombre qui est divisé ici la ième ligne pour la  division de G(i)

    L'utilisation de l'algorithme d'EUCLIDE  se fait en  "descendant " ainsi à chaque division jusqu'à obtenir la dernière division qui est toujours sans reste et d'une forme similaire  à:
             G(2)=G(1)*H(1) ou G(i) est toujours égal à 1  et H(1) est   le dernier dividende obtenu.  H(1) peut prendre toute valeur inférieure à G(3)
Ensuite on repart en  sens inverse pour trouver les coefficients de BEZOUT de nos deux nombres premiers entre eux
Je suis parti dans mon exposé directement en partant du bas ce qui s'explique a postériori car les deux ligne 1 et 2 sont toujours identiques 
mais peuvent dérouter eux qui utilisent que des nombres entiers .
Mais en dehors de celà  je suppose que la méthode est parfaitement  est parfaitement connue de tous les habitués du forum. 

J'ai d'abord écrit un algorithme d'EUCLIDE théorique qui est universel et applicable quelque soient les deux nombres premiers entre eux.
 Ceci est représenté par la suite de divisions de mon post initial.je n'ai pas été assez clair comme l'a fait remarquer Gérard sur ce que représentaient 
 mes notations et leurs indices . J'espère que je suis un peu plus compréhensible.
Pour les courageux qui vont s'attaquer à ce problème 
Il pourront démontrer en cours de route que les  G(i) et G(i-1) de chaque division successive sont premiers entre eux, en donner une expression qui  
ne dépendra que des H(i),H(i-1).....et exprimer de la même manière leur coefficients de BEZOUT respectifs.
Et en donnant des valeurs particulières aux H(i) ils obtiendront des propriétés bien particulières dont l'une fait justement l'objet de cet exercice 
que je pense original.

PS si quelqu'un a déjà cela rencontré une résolution de l'algorithme d'EUCLIDE théorique , je le remercie de me donner des infos. 
 

lourrran

Si on a 4 nombres de Fibonacci successifs $A, B, C, D$ ,  $A \times \D - B \times C$ vaut alternativement $1$ ou $-1$ ; je suppose que c'est le résultat attendu.

gerard0

Bon, finalement, tu dis que tu fais la remontée d'un algorithme d'Euclide "à priori", en utilisant des diviseurs H(i)  (i est le numéro de l'étape). Donc tout dépend du choix de la suite $(H(i))_i$. Et bien évidemment les coefficients de Bézout. Donc finalement, tu enfonces une porte ouverte. L'exercice n'était difficile que parce que incompréhensible.

Sinon, l'algorithme d'Euclide est connu depuis très longtemps, et très utilisé en maths discrètes (les maths à la base des algorithmes du calcul formel). Tu devrais trouver dans les ouvrages de cette discipline de nombreux résultats, et bien entendu, les coefficients de Bézout en fonction du calcul du pgcd, très utilisés. Y compris dans d'autres arithmétiques que celle des entiers, celle des polynômes, par exemple.

Cordialement.

donnet

bonsoir Lourrran merci de t'intéresser positivement à mon petit exercice.  
  pour les premiers termes 
 G(2) =H(1)                                                                             ;   K(2) =  1
 G(3) =1+(H(1)*H(2)                                                               ;   K(3) =   H(2)
 G(4) =(1+H(1)*H(2))*H(3)+H(1)                                             ;  K(4) =   1+H(2)*H(3)
 G(5)  =[ (1+H(1)*H(2))*H(3)+H(1) ]*H(4)+1+(H(1)*H(2)        ;  K(5)  = (1+H(2)*H(3))*H(4)+H(2)
les formules deviennent rapidement imposantes mais simple à prévoir à l'aide des divisions euclidiennes correspondantes 

Pour les coefficients de BEZOUT on vérifie pour tout i 
                 K(i)=K(i-1)*H(i-1)+K(i-2)  similaire avec la formule des G(i) la différence étant G(1)=1 et G(2)=H(1) alors que K(2)=1 et K(3)=H(2) 

Les identités du même nom 
                 G(2i+1)*K(2i )-G(2i )*K(2i+1)=1 
                 G(2i )*K(2i-1 )-G(2i-1 )*K(2i )=-1
cela permet de prévoir le signe de l'identité ( démonstration  par récurrence)

cas particulier Tous les H(i) sont égaux à une seule valeur H
                 Les G(i) sont les termes d'une suite récurrente d'ordre 2  G(i)=H*G(i-1)+G(i-2)    et K(i)=G(i-1)
                 Et Si H=1
                                  Les G(i) sont les nombres de FIBONACCI  

en ce qui concerne l'exercice il ne reste plus qu'à trouver la bonne combinaison de H(i) c'est assez facile en regardant comment évoluent Les G et K

Je referme ici la porte ouverte que j'ai enfoncée comme cela est dit si charitablement  

donnet

Bonjour 
pour clore ce post 
la solution au problème proposé est H(1), route les autres valeurs des H(i)=1.
On obtient avec les résultats de l'algorithme d'Euclide "théorique"
 G(i)=F(i-2)+F'(I-1)*H(1) et le coefficient de Bézout K(i)=F(I-1Les F(i) étant les nombres de Fibonacci (F(1)=1 F(2)=1, F(3)=2 etc.
On peut également considérer tous les H(i)=1 sauf H(2) sauf les H(2) qui prennent une valeur quelconque.
On peut également obtenir les G(i) termes d'une suite des nombres de Lucas avec H(1)=3 tous les autres égaux à 1.
[Tu peux modifier toi-même tes messages. Clique sur la roue dentée en haut à droite de ton message. AD]