***************************************************************************************************************************** Algorithme des coefficients de Bezout ****************************** ************************************************************************************************* Auteur : Pedro C. (Drop_f@hotmail.com) - Des captures d'écrans de TI-89 et TI-92 du même exemple sont fournies. - Les fichiers : > le programme : * bezout.92p : programme pour TI-92 / TI-92II / TI-92Plus * bezout.89p : programme pour TI-89 > les captures d'écrans : * 89 - bezout... : captures d'un exemple sur TI-89 * 92 - bezout... : captures du même exemple sur TI-92 > ce fichier que vous être en train de lire ************************************************************************************************* Présentation ============ Ce programme permet de trouver les coefficients de Bezout, ainsi que le PGCD et le PPCM de 2 nombres à l'aide d'un tableau : le jour du bac, il n'y a plus qu'a recopier :o))). Il peut également être utilisé pour faire l'algorithme d'Euclide (division euclidienne) instantanément. Il suffit de réécrire le tableau sous forme linéaire (équations) du type de celle de l'algorithme d'Euclide ; cette manipulation sera décrite en bas de la page. Il utilise un algorithme qui peut être parfois contesté au Bac. C'est pourquoi, si vous l'utilisez au Bac, il est nécessaire de rajouter une phrase qui explique la méthode utilisée. ************************************************************************************************* Fonctionnement et restrictions ============================== Pour lancer le programme, il suffit de taper "bezout()" sur la calculatrice (à condition d'être dans le répertoire où se trouve le programme). On rentre les deux nombres, et on choisit si on veut les étapes (c'est-à-dire avec le tableau, puis les résultats) ou si on ne veut pas les étapes (sans le tabeau, mais avec les résultats). Sur la TI-89, les chiffres du tableau ne peuvent pas dépasser 3 caractères. Par exemple : * 100, -32, 952 etc. marchent * 1000, 6541, -102, etc. ne marchent pas car ils se superposent dans le tableau et peuvent effacer d'autres chiffres. Sur, la TI-92, même restriction mais avec 4 caractères (je pense que 5 caractères marche aussi) Ce programme ne contient aucun bugs en principe, car c'est un "petit" programme. Il y a des problèmes pour les calculatrices qui sont dans une autre langue que l'Anglais. Si votre calculatrice est en français, il éditer le programme en remplaçant : - tous les "off" par "naff" - tous les "on" par "aff" ************************************************************************************************* Méthode ======= Si l'on veut une solution (u et v) possible de l'équation : a.u + b.v = 1 (avec a et b premiers entre eux) Il suffit alors de faire le tableau suivant : | | | | | | | q1 | q2 | q3 | q4 | q... | q final | | | | | | --------------------------------------------------------- | | | | | | | a | b | r1 | r2 | r3 | r... | 1 | 0 <----- reste final | | | | | | | --------------------------------------------------------- | | | | | | | 1 | 0 | u1 | u2 | u3 | u... | u <---------\ | | | | | | | | -------------------------------------------------- |-- solutions de l'équation | | | | | | | | 0 | 1 | v1 | v2 | v3 | v... | V <---------/ | | | | | | | où : * q(n) correspond au quotient de la n-ième division euclidienne de a par b * r(n) _____________ reste ____________________________________________ * u1 = 1 - 0xq1 u2 = 0 - u1xq2 u3 = u1 - u2xq3 ... u(n) = u(n-2) - u(n-1)*q(n) (Attention : u(n) et q(n) sont décalés d'une colonne) * idem que u(n) pour v(n) mais à ligne d'en-dessous (dans le tableau) : v1 = 0 - 1*q1 v2 = 1 - v1*q2 v3 = v1 - v2*q3 ... v(n) = v(n-2) - v(n-1)*q(n) (Attention : v(n) et q(n) sont décalés d'une colonne) Remarque : on voit bien que a et b sont premiers entre eux si, dans le tableau, le dernier reste -------- est nul et si le reste d'avant est 1. Si ce n'est pas le cas, alors la méthode de Bezout ne peut être employée et le tableau est faux. Par contre, le PGCD et le PPCM sont bons. ************************************************************************************************* Division euclidienne : ==================== Pour l'algirithme d'Euclide, il suffit d'écrire : a = b*q1 - r1 b = r1*q2 - r2 r1 = r2*q3 - r3 ... r(n) = r(n+1)*r(n+2) - r(n+2) ************************************************************************************************* CE LOGICIEL EST DISTRIBUE TEL QUEL, ET L'AUTEUR DECLINE TOUTE RESPONSABILITE POUR CE QUI EST DES DOMMAGES (MATERIELS, LOGICIELS ET ECONOMIQUES) QUI PEUVENT DECOULER DE SON UTILISATION. VOUS N'AVEZ PAS LE DROIT DE DISTRIBUER DES VERSIONS MODIFIEES DU CODE SOURCE OU DE CE FICHIER TEXTE SANS LA PERMISSION DE L'AUTEUR. VOUS N'AVEZ PAS LE DROIT DE CREER DES VERSIONS MODIFIEES DE CE LOGICIEL QUI POURRAIENT CREER DES DOMMAGES. L'AUTEUR DECLINE TOUTE RESPONSABILITE SI UNE LE PROGRAMME DE BEZOUT CREER DES DOMMAGES : VOUS UTILISEZ CE PROGRAMME SOUS VOTRE PROPRE RESPONSABILITE. *************************************************************************************************