{"id":1326,"date":"2017-04-15T15:49:02","date_gmt":"2017-04-15T13:49:02","guid":{"rendered":"http:\/\/www2.mathnique.com\/site\/?page_id=1326"},"modified":"2017-04-15T16:04:01","modified_gmt":"2017-04-15T14:04:01","slug":"algorithmes-gcd","status":"publish","type":"page","link":"https:\/\/www.mathnique.com\/site\/algorithmes-gcd\/","title":{"rendered":"Algorithmes Pgcd"},"content":{"rendered":"

Algorithme 1 : L'Algorithme d'EUCLIDE<\/b>\u00a0<\/span><\/p>\n

$a$ et $b$ \u00e9tant des entiers naturels non nuls.
\nOn sait qu'il existe des entiers naturels $q$ et $r$ tels que $a = b q + r$ o\u00f9 $0 \\leq r < b$
\n<\/b>L'on a ainsi effectu\u00e9 la division euclidienne de $a$ par $b$.
\n<\/b>$q$ s'appelle le quotient de la division euclidienne.<\/b>\u00a0Dans le tableur Excel, $q$ s'obtient par $ent(a,b)$ $<\/b>r$ s'appelle le reste de la division euclidienne.\u00a0Dans le tableur Excel, $r$ s'obtient par $mod(a,b)$<\/b><\/p>\n

Le PGCD de deux nombres est le dernier reste non nul de la succession de divisions que l'on effectue dans l'algorithme d'Euclide.\u00a0<\/b><\/p>\n

\u00a0 <\/b>Voici une feuille de calcul Excel r\u00e9alisant cet algorithme :<\/b><\/p>\n

\"\"
\nVoici les formules utilis\u00e9es dans cette feuille :<\/b><\/p>\n

\"\"<\/p>\n

Algorithme 2 : L'algorithme de la diff\u00e9rence<\/b>\u00a0<\/span><\/p>\n

Il est bas\u00e9 sur la propri\u00e9t\u00e9 suivante :<\/b><\/p>\n

Soient $a$ et $b$ des entiers naturels non nuls avec $a > b$. Alors le PGCD de $a$ et de $b$ est \u00e9gal au PGCD de $b$ et de $a - b$<\/b><\/p>\n\n\n\n\n\n\n\n\n\n\n
\n

d = pgcd(810 ; 450)<\/p>\n<\/td>\n

\n

810 - 450 = 360<\/p>\n<\/td>\n<\/tr>\n

\n

d = pgcd(450 ; 360)<\/p>\n<\/td>\n

\n

450 - 360 = 90<\/p>\n<\/td>\n<\/tr>\n

\n

d = pgcd(360 ; 90 )<\/p>\n<\/td>\n

\n

360 - 90 = 270<\/p>\n<\/td>\n<\/tr>\n

\n

d = pgcd(90 ; 270) = pgcd(270 ; 90)<\/p>\n<\/td>\n

\n

270 - 90 = 180<\/p>\n<\/td>\n<\/tr>\n

\n

d = pgcd(90 ; 180) = pgcd(180 ; 90)<\/p>\n<\/td>\n

\n

180 - 90 = 90<\/p>\n<\/td>\n<\/tr>\n

\n

d = pgcd(90 ; 90)<\/p>\n<\/td>\n

\n

90 - 90 = 0<\/p>\n<\/td>\n<\/tr>\n

\n

le pgcd est donc 90<\/b><\/p>\n<\/td>\n

<\/td>\n<\/tr>\n
<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

La feuille de calcul suivante utilise cet algorithme :<\/b><\/p>\n

\"\"<\/p>\n

Voici les formules utilis\u00e9es dans cette feuille :<\/b><\/p>\n

\"\"<\/p>\n

On peut am\u00e9liorer cette feuille en remarquant que d\u00e8s que b est \u00e9gal \u00e0 1 alors le pgcd est a<\/b>
\nAuteur : Christian CYRILLE Groupe IREM Kabrit Bwa<\/span><\/em><\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"

Algorithme 1 : L'Algorithme d'EUCLIDE\u00a0 $a$ et $b$ \u00e9tant des entiers naturels non nuls. On sait qu'il existe des entiers naturels $q$ et $r$ tels que $a = b q + r$ o\u00f9 $0 \\leq r < b$ L'on a ainsi effectu\u00e9 la division euclidienne de $a$ par $b$. $q$ s'appelle le quotient de la … Continuer la lecture de « Algorithmes Pgcd »<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"class_list":["post-1326","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages\/1326","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/comments?post=1326"}],"version-history":[{"count":5,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages\/1326\/revisions"}],"predecessor-version":[{"id":1335,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages\/1326\/revisions\/1335"}],"wp:attachment":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/media?parent=1326"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}