L'homme ne montre son véritable visage qu'une fois qu'il a ôté sa culotte. (Sade)
Un exercice original sur le pgcd
dans Arithmétique
Bonjour,
Soient $d, p$ deux entiers naturels.
Quels sont les deux plus petits nombres ayant $p$ comme PGCD et pour lesquels le calcul du PGCD exige $d$ divisions ?
A+
Soient $d, p$ deux entiers naturels.
Quels sont les deux plus petits nombres ayant $p$ comme PGCD et pour lesquels le calcul du PGCD exige $d$ divisions ?
A+
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
« le calcul du PGCD exige d divisions »
Il faut préciser cela. Est-ce « le calcul par la méthode d’Euclide des divisions successives » ?
Même si ça semble une évidence...
Je réponds mais c'est hors sujet à mon avis. C'est juste histoire de participer.
Je prends une suite d'entiers $q_1, \cdots, q_d$, supérieurs ou égaux à $1$, sauf le dernier pour lequel je suppose que $q_d \ge 2$ (car le dernier quotient dans l'algorithme d'Euclide n'est jamais égal à 1, sauf cas très très particuliers).
Par exemple, avec $d = 7$ :
Je fais alors un petit truc secret qui à partir des $q_i$ détermine deux entiers $a, b$ Et là, je déroule la suite des divisions euclidiennes en partant de $(a, b)$. Et on retrouve exactement la suite des quotients.
Tu vas me dire qu'en fait, en planquette, je suis parti de $a,b$ et j'ai déterminé les quotients. Non, non, je t'assure. Tu n'as qu'à me donner une suite de quotients, tu verras.
Oui, oui, je sais, ce n'est pas ta question. Mais j'ai quand même parlé de divisions euclidiennes.
Sinon, tes nombres a et b se trouvent facilement.
Tu as l'oeil. En ce qui concerne les 1, je suppose que tu veux dire sauf le dernier (au lieu de sauf le premier). Les histoires de réduites, continuants, polynômes d'Euler (je crois qu'ils s'appellent ainsi), cela m'a toujours fasciné. Les étudiant(e)s, enfin certains, aimaient bien jouer avec ces objets. Moi aussi, la preuve.
Je remets un peu de contexte : les $d=7$ quotients. Puis je considère les $d$ matrices $2 \times 2$ que tu vois. Pour éviter de saturer la machine, je montre seulement les 3 premières matrices, les autres sont du même acabit. Ici dans ces matrices, $q_i$ est une indéterminée. Je vais faire le produit $M$ dans cet ordre de ces $d=7$ matrices. Et voici les coefficients $M_{11}$ (polynôme d'Euler de $q_1, q_2, \cdots, q_d$), et $M_{21}$ (polynôme d'Euler de $q_2, q_2, \cdots, q_d$), Je vais évaluer ces deux polynômes $M_{11}$ et $M_{21}$ en les 7 quotients donnés au début pour retrouver $a,b$. Un truc amusant, je trouve c'est l'aspect renversant du polynôme d'Euler : le polynôme d'Euler de $(q_1, q_2, \cdots, q_d)$ c'est aussi celui de $(q_d, \cdots, q_2, q_1)$. En algorithmique, cela permet le calcul de la réduite ``à la volée'' comme on dit : dans l'ordre des quotients et pas dans l'ordre inverse. Et je termine en allant un peu vers toi. Je considère la suite (je t'emprunte ton nom) de longueur $d$ constituée de $d-1$ 1 puis un 2 (le dernier quotient n'est jamais égal à un). Puis j'évalue les 4 coefficients-polynômes $M_{i,j}$ de la matrice en la suite Qnodgim et je laisse tout ce beau monde dans une matrice $2 \times 2$.
Les nombres de Fibonacci sont là.
Je l'avais posé en Math-Sup en 1991-92, dans une feuille d'exercices que je vous joins, tapée avec ce bon vieux ChiWriter.
Je l'avais trouvé dans des traités anciens, qui dataient d'une époque où la suite de Fibonacci était appelée « série de Lamé » : il faudra que je retrouve une source.
Bonne journée.
Fr. Ch.