Home

MPSI/PCSI

Maths

Algèbre

PGCD et algorithme d’Euclide

Dans cet exercice, nous étudions la suite de Fibonacci. Nous rappelons que la suite de Fibonacci est définie par U0=0, U1=1 et Un+2 = Un+1 + Un. 

La première question consiste à montrer que pour tout n positif, (Un+1 * Un-1 - Un^2) = (-1)^n. Pour cela, nous considérons une suite Vn définie par Vn = (Un+1 * Un-1 - Un^2). Nous souhaitons montrer que Vn est une suite géométrique de raison -1. 

Nous commençons par exprimer Vn+1 en fonction de Vn. En utilisant la relation de récurrence de la suite de Fibonacci, nous obtenons Vn+1 = (Un+2 * Un - Un+1^2). Nous procédons ensuite à un développement et simplifions l'expression pour obtenir Vn+1 = -Vn. Cela prouve que Vn est une suite géométrique de raison -1. 

En calculant V1, nous trouvons que Vn = (-1)^n. Ainsi, nous avons montré que pour tout n positif, (Un+1 * Un-1 - Un^2) = (-1)^n. 

La deuxième partie consiste à montrer que deux termes consécutifs de la suite de Fibonacci sont premiers entre eux. Nous utilisons l'égalité précédente pour cela. Nous remarquons que cette égalité ressemble à une égalité de Bézout. En multipliant les deux côtés de l'égalité par (-1)^n, nous obtenons U(n+1) * U(n-1) - U(n)^2 = 1. En écrivant cette égalité sous la forme U(n-1) * U(n+1) + U(n) * Un = 1, nous avons trouvé les coefficients de Bézout montrant que U(n-1) et U(n+1) sont premiers entre eux. 

Ensuite, nous montrons que pour tout n, U(m+n) = Um * Un+1 + Um-1 * Un. Nous utilisons une double récurrence pour démontrer cette propriété. En vérifiant les deux premiers termes de la récurrence, nous constatons que la propriété est vérifiée. Ensuite, nous supposons que la propriété est vraie pour PM et PM+1, et nous montrons qu'elle est également vraie pour PM+2. Finalement, en utilisant cette propriété, nous montrons que le PGCD de Um et Un est égal à U(PGCD(m,n)).

En conclusion, nous avons étudié la suite de Fibonacci et montré plusieurs propriétés intéressantes, telles que la relation géométrique entre les termes de la suite, la coprimalité des termes consécutifs et la relation entre le PGCD de deux termes et le PGCD de leurs indices.

Salut, bienvenue dans cet exercice où l'on va étudier la suite de Fibonacci. Alors, la suite de Fibonacci, on la rappelle, u0 c'est 0, u1 c'est 1, et ensuite un plus 2 c'est un plus 1 plus un. Donc en gros, on prend deux termes de la suite, on les additionne, et ça nous donne le terme d'encore après. Donc, première question, on nous dit montrer que pour toute n positive, on a un plus 1 fois un moins 1 moins un au carré est égal à moins 1 puissance n. Et ensuite en déduire que deux termes consécutifs de la suite sont premiers entre eux. Donc pour faire ça, ce qu'on va voir, c'est que cette partie-là, la partie de gauche de l'égalité, on va considérer que c'est une suite. D'accord ? Parce que bon, c'est que des termes avec du n, on va créer une nouvelle suite qui va être comme ça. Et le but, ça va être de montrer que c'est une suite géométrique, c'est de là que la puissance va venir, c'est de montrer que c'est une suite géométrique de raison moins 1. Donc c'est parti. Donc on pose Vn qui vaut cette égalité, cette expression, pardon, un plus 1 fois un moins 1 moins un au carré. Le but, comme je disais, c'est de montrer que c'est une suite géométrique de raison moins 1. Donc c'est parti. Vn plus 1, c'est un plus 2 fois un moins un plus 1 au carré. Le but, là, c'est de faire apparaître Vn. On aimerait bien dire que Vn plus 1, c'est moins Vn. Donc le but étant de faire apparaître Vn. Pour faire apparaître Vn, il faut qu'on ait Un moins 1 qui apparaisse. Et il faut qu'on fasse disparaître le Un plus 2 dans cette écriture-là. Donc le Un plus 2, on utilise la relation de Fibonacci. Donc Un plus 2, on remplace par Un plus 1 plus Un. Et pour faire apparaître Un moins 1, on fait pareil avec un des Un plus 1 qui est ici. Vu qu'il est au carré, c'est Un plus 1 fois Un plus 1. Il y en a un qu'on va remplacer par Un plus Un moins 1. Comme ça, on a fait apparaître le Un moins 1. Donc on développe, on voit ce qui se simplifie. Donc on développe, et il y a ces deux-là qui vont se simplifier. Et il va rester Un carré moins Un plus 1 fois Un moins 1. Et là, ça, c'est exactement moins Vn. Donc ça nous dit que Vn est une suite géométrique de raison moins 1. Vn, le premier terme, c'est V1. Donc l'écriture de Vn, ça va être V1 fois moins 1 puissance N moins 1. On calcule V1. C'est U2 fois U0 moins U1 au carré. Et ça, ça nous fait exactement moins 1. Et donc, on a bien que pour toute N strictement positive, Vn est égal à moins 1 puissance N. Donc on a l'égalité recherchée. De Un plus 1 fois Un moins 1 moins Un au carré est égal à moins 1 puissance N. Deuxième partie, c'est là où il faut en déduire que pour toute N strictement positive, deux termes consécutifs de la suite sont premiers entre eux. Alors là, ce qu'on va faire, on va utiliser l'égalité qu'on a ici. De toute façon, quand on a en déduire, généralement, c'est qu'il faut utiliser ce qui précède. Et on remarque que ça ressemble un tout petit peu, pas exactement, mais ça ressemble un peu à une égalité de Bézout. Avec Un plus 1, il est là. Un, il est là. C'est pas 1, mais presque. Donc on va essayer de faire en sorte que ça marche bien. Où est-ce que j'en étais ? On réécrit cette égalité. Là, on va multiplier par moins 1 puissance N de chaque côté. Ce qui fait que le moins 1 puissance N ici va se transformer en 1. Et il y a un moins 1 puissance N qui va apparaître ici et là. Un moins 1 puissance N plus 1 parce qu'il y a un moins. Le but, c'est d'avoir Un plus 1 et Un premiers entre eux. On aimerait bien trouver des coefficients de Bézout pour avoir U fois Un plus 1 plus V fois Un est égal à 1. En fait, c'est ce qu'on a. En faisant ça, pour Un plus 1, le U sera moins 1 puissance N fois U indice N moins 1. Et pour Un, le V, le coefficient, ce sera moins 1 puissance N plus 1 fois Un. En faisant ça, on a réussi à écrire Un plus 1 et Un comme U fois Un plus 1 plus V fois Un est égal à 1. Et donc, le théorème de Bézout nous dit que ça veut exactement dire que Un et Un plus 1 sont premiers entre eux. Question d'après. Montrer que pour toute N, U indice M plus N est égal à Um fois Un plus 1 plus Um moins 1 fois Un. Et en déduire que le PGCD de Um et Un est égal à U indice PGCD de M et N. Vu comme ça, on a l'impression que ça sort de nulle part. On va voir comment faire. On va faire une récurrence double sur la propriété qu'on nous demande de démontrer. Une récurrence double, c'est parce que vu qu'on utilise des relations de récurrence d'ordre 2, on fait une récurrence double, ça veut dire qu'on fait sur deux termes en même temps. Enfin, deux termes consécutifs en même temps. Donc, pour les deux premiers, ça marche bien. Pour M égal 1, M égal 2. Donc là, on remplace U1, U0, U2, U1 par leurs valeurs. Et on trouve qu'on a bien les résultats qui correspondent. Maintenant, le passage de M à N plus 1. Donc, on suppose que PM et PM plus 1 sont vrais pour un certain M. Je rappelle ce que ça veut dire. Ça, c'est pour PM plus 1, ça, c'est pour PM. Il faut montrer que pour PM plus 2, c'est aussi vrai. Donc, ce qu'on veut montrer, c'est que U indice M, N plus 2, c'est égal à U indice M plus 2 fois U indice N plus 1, plus U indice M plus 1 fois UN. Donc, on va se lancer dans les calculs. U indice N plus M plus 2, on utilise la relation de récurrence de la suite de Fibonacci, parce qu'on parle toujours de la suite de Fibonacci. Du coup, c'est la somme des deux termes de la suite précédent. Là, on utilise l'hypothèse de récurrence avec justement ces deux termes précédents. On remplace celui-ci par... C'est lequel ? Avec le M plus 1, c'est celui-ci. Et celui-ci par cette égalité-là. Ça, c'est l'hypothèse de récurrence qui nous dit qu'on peut faire ça. Et une fois qu'on fait ça, on factorise. Par U1, ça nous fait UM plus 1, plus UM. Facteur de U indice N plus 1. Et pareil pour UN. Et ce qu'on observe, on utilise encore la propriété de la suite de Fibonacci pour dire que ça, c'est U indice M plus 2. Et ça, c'est U indice M plus 1. On remplace et on trouve bien l'égalité qu'on souhaitait. Donc, rapide conclusion, c'est une récurrence, tout marche bien. Donc, PM est vrai. Ensuite, ce qu'on va faire... Là, on va parler de PGCD, etc. Souvent, on fait des algorithmes de Clyde. Pour ça, il faut commencer par faire des divisions euclidiennes. Là, on suppose que N est plus petit que M. Auquel cas, on inverse juste le rôle de M et N dans le raisonnement qu'on va faire. Enfin, si ce n'est pas le cas. On effectue la division euclidienne de N par M. Et on a que N, c'est MQ plus R. Avec, bien sûr, R qui est entre 0 et M moins 1. Donc, on réécrit l'égalité. Donc, ça fait U indice M plus R. On utilise ce qu'on vient de montrer. C'est U indice M fois U indice R plus 1. Plus U indice M moins 1 fois U indice R. Ensuite, CD, c'est un diviseur commun à UM et UR. UM, ici, et UR. Alors, il divise UM plus R et UM. Là, ce qu'on essaie de faire, c'est une sorte d'algorithme d'euclide. On veut trouver le PGCD. On refait un peu le principe de l'algorithme d'euclide. Si un nombre divise à la fois lui et lui, étant donné qu'on a deux entiers et une somme, il va diviser aussi lui. Il va diviser lui et lui. Parce que D de base divise lui. Si on fait ça, c'est pour toujours les garder deux par deux. Pour pouvoir enchaîner les divisions euclidiennes. Réciproquement, si on a un diviseur qui divise lui et lui, donc UM plus R et UM, en passant ça de l'autre côté, il va diviser UM moins 1 et UR. Parce que si on passe ça de l'autre côté, s'il y en a un diviseur de lui, un diviseur de lui, la soustraction sera égale à UM moins 1 fois UR. Donc D divisera le produit des deux. Mais, étant donné que UM et UM moins 1 sont premiers entre eux, D est un diviseur de UM, il ne peut pas diviser UM moins 1, sauf s'il vaut 1. D'après le théorème de Gauss, D divise un produit, on sait que ce n'est pas un diviseur de UM moins 1, parce que c'est un diviseur de UM qui sont premiers entre eux. Donc naturellement, D divise UR. Si c'est 1, ça divise aussi UR. Il n'y a pas de souci. Du coup, on vient de montrer une des propriétés de l'algorithme d'euclide qu'on utilise pour la recherche de PGCD, qu'on ne rappelle même plus maintenant. On a montré que les diviseurs communs de UM plus R et UM, ne sont pas les mêmes diviseurs que ceux de UM et UR. Là, ce qu'on a fait, c'est le même raisonnement que l'algorithme d'euclide pour les principes de PGCD, mais on a dû le refaire, parce qu'on ne fait pas la division euclidienne. On n'est pas en train de faire la division euclidienne de UM plus R par UM, avec celui-là qui est le reste, etc. Ce n'est pas ce qu'on est en train de faire. On est juste en train d'écrire l'égalité, et de proche en proche, d'écrire d'autres égalités. On sait que cette égalité nous donne que les diviseurs communs de lui et lui, sont les mêmes diviseurs communs que UM et UR. On va pouvoir raisonner de proche en proche. Finalement, le PGCD de UM plus R et UM, c'est le PGCD de UM et de UR. S'ils ont les mêmes diviseurs communs, le plus grand diviseur commun sera le même dans les deux cas. Du coup, comme je disais, en raisonnant de proche en proche, en itérant ce procédé, le PGCD de UM et de UR, c'est le PGCD de UM et de UN. Parce que là, ce qu'on fait, c'est que le PGCD de UM, UR, c'est le PGCD de UM, UM plus R. On rajoute M ici. Ensuite, c'est le PGCD de U, indice de M plus R, jusqu'à QM plus R. QM plus R, c'est exactement N. On a montré que le PGCD de UM, UR, c'est le PGCD de UM, UN. Parce que c'est ça qui nous intéressait. Si on veut remonter un peu dans la question, on voulait avoir des infos sur le PGCD de UM et de UN. C'est ça qu'on voulait. En fait, comme je disais, on a la relation qui nous dit que celui-là est égal à celui-là. Donc finalement, si on applique en parallèle l'algorithme d'Euclide à la fois à UM, UN d'une part et à M et N d'autre part, on a bien l'égalité recherchée que le PGCD de UM et UN, c'est égal à U indice le PGCD de M et de N. Et voilà ce qui conclut cet exercice.

PGCD Fibonacci

RELATED

Recommended videos

algorithme d’Euclide

Equations de Bezou