Probl`emes de Math´ematiques Sur les traces de Leonardo Pisano ´Enonc´e Sur les traces de Leonardo Pisano On d´efinit la suite de Fibonacci (Fn)n≥0 par : � F0 = 0 F1 = 1 et ∀ n ≥ 0, Fn+2 = Fn+1 + Fn. On a donc F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8, F7 = 13, F8 = 21, etc. On d´efinit ainsi une suite d’entiers naturels, strictement croissante `a partir du rang 2. Leonardo Pisano, dit Fibonacci (1170-1250) : par son oeuvre principale, le « liber abaci », il a introduit et popularis´e la num´erotation positionnelle utilisant les chiffres arabes. Les entiers Fn y apparaissent dans un probl`eme relatif `a la descendance d’un couple de lapins. C’est le math´ematicien fran¸cais Edouard Lucas (1842-1891) qui baptisa cette suite et en d´ecouvrit d’int´eressantes propri´et´es. Premi`ere partie Dans cette partie, on ´etudie quelques propri´et´es de divisibilit´e portant sur les entiers Fn. 1. Pour tout n de N∗, prouver la relation de Cassini : Fn+1Fn−1 − F 2 n = (−1)n. En d´eduire que pour tout n de N∗, les entiers Fn−1 et Fn sont premiers entre eux. Jean-Baptiste Cassini (1625-1712), astronome `a qui on doit la d´ecouverte des satellites de Jupiter. [ S ] 2. Pouvez-vous expliquer le paradoxe suivant, attribu´e `a Lewis Carrol ? On d´ecoupe un carr´e 8×8 comme indiqu´e en deux triangles et deux trap`ezes. On r´earrange les quatre morceaux en un seul rectangle de taille 5 × 13. Avant d´ecoupe, l’aire totale vaut 64. Apr`es r´earrangement elle vaut 65. D’o`u vient le carr´e suppl´ementaire ? G´en´eraliser tr`es soigneusement en utilisant les entiers Fn. Lewis Carrol, 1832-1898, logicien et ´ecrivain britannique. Auteur de « Alice au Pays des Merveilles ». [ S ] 3. Montrer que pour tout (n, m) de N2, on a Fn+m+1 = Fm+1Fn+1 + FmFn. [ S ] 4. En d´eduire que pour tout (q, n) de N2, Fqn est un multiple de Fn. [ S ] 5. On se donne (m, n) dans N2, avec m ≤ n. Soit d un entier naturel. Montrer que si d divise Fn et Fm, alors il divise Fn−m (utiliser les questions 1 et 3.) [ S ] 6. En d´eduire que pour tous entiers m et n on a : Fm ∧ Fn = Fm∧n. Indication : on sera amen´e `a d´emontrer que si p divise Fm et Fn, alors il divise Fm∧n. Pour cela, on raisonnera par r´ecurrence sur la valeur de m + n, et on utilisera la question 5. [ S ] 7. Montrer qu’on peut maintenant compl´eter le r´esultat de la question 4 de la fa¸con suivante : Pour tout entier n ≥ 3, et pour tout entier m, on a l’´equivalence : Fn ;;; Fm ⇔ n ;;; m. [ S ] 8. Dans cette question on va prouver le lemme de Yuri Matijasevitch (1970) : « Pour n ≥ 3 et m ≥ 0 : Fm est divisible par F 2 n si et seulement si m est divisible par nFn » (a) Par r´ecurrence sur k, montrer les congruences � Fkn ≡ kFnF k−1 n+1 (F 2 n) Fkn+1 ≡ F k n+1 (F 2 n) [ S ] (b) Conclure [ S ] Page 1 Jean-Michel Ferrard www.klubprepa.net c⃝EduKlub S.A. Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation individuelle et priv´ee sont interdites.