Médaille
N°1 pour apprendre & réviser du collège au lycée.
Algorithme d’Euclide : rechercher le PGCD de deux entiers naturels a et b - Casio
Découvrez, sur SchoolMouv, des milliers de contenus pédagogiques, du CP à la Terminale, rédigés par des enseignants de l’Éducation nationale.
Les élèves de troisième, de première ou de terminale bénéficient, en plus, de contenus spécifiques pour réviser efficacement leur brevet des collèges, leur bac de français ou leur baccalauréat édition 2023.
Algorithme

Type de calculatrice

Casio

Prérequis

L’algorithme d’Euclide repose sur le principe de la division euclidienne : soient deux entiers a>ba>b, et rr le reste de la division euclidienne de aa par bb, alors le PGCD de aa et bb est le même que le PGCD de bb et rr. Ainsi, par divisions euclidiennes successives on arrive à déterminer le PGCD de deux entiers.

Description

Programme

Le programme prend deux entiers a>ba>b et effectue la division de aa par bb, de reste rr, ensuite aa prend la valeur de bb, et bb prend la valeur de rr, la boucle est répétée tant que r0r\not=0. Alors la valeur de bb est le PGCD recherché.

Variables

aa et bb deux entiers entrés par l’utilisateur tels que a>ba>b
rr un entier calculé par le programme

Algorithme

|demander aa et bb
|r=r= le reste de la division euclidienne de aa par bb
|tant que r0r\not=0
|aa prend la valeur de bb
|bb prend la valeur de rr
|r=r= le reste de la division euclidienne de aa par bb
|afficher bb

Programme Casio

?A:?B\mathsf{?} \rightarrow \mathsf{A}:\mathsf{?} \rightarrow \mathsf{B}

AInt (A÷B)×BR\mathsf{A}- \mathsf{Int}\ (\mathsf{A}\div \mathsf{B}) \times \mathsf{B} \rightarrow \mathsf{R}

While R0\mathsf{While}\ \mathsf{R}\not= 0

BA:RB\mathsf{B}\rightarrow \mathsf{A} : \mathsf{R}\rightarrow \mathsf{B}

AInt (A÷B)×BR\mathsf{A}- \mathsf{Int}\ (\mathsf{A}\div \mathsf{B}) \times \mathsf{B} \rightarrow \mathsf{R}

WhileEnd\mathsf{WhileEnd}

B\mathsf{B}\blacktriangleleft

  • SHIFTVARSF4 « ? » AlphaX,θ,TX,\theta,T « A »
    SHIFTVARSF6 « ▷ » F5 « : »
    SHIFTVARSF4 « ? » Alphalog « B » EXE « ↵ »
  • AlphaX,θ,TX,\theta,T « A »  - 
    OPTNF6 « ▷ » F4 « NUM » F2 « Int »
    ( AlphaX,θ,TX,\theta,T « A » ÷ Alphalog « B » )
     ×  Alphalog « B » Alpha6 « R » EXE « ↵ »
  • SHIFTVARSF1 « COM » F6 « ▷ » F6 « ▷ » F1 « While » Alpha6 « R » SHIFTVARSF6 « ▷ » F3 « REL » F2 «  » 0 EXE « ↵ »
  • Alphalog « B » AlphaX,θ,TX,\theta,T « A »
    SHIFTVARSF6 « ▷ » F5 « : »
    Alpha6 « R » Alphalog « B » EXE « ↵ »
  • AlphaX,θ,TX,\theta,T « A »  - 
    OPTNF6 « ▷ » F4 « NUM » F2 « Int »
    ( AlphaX,θ,TX,\theta,T « A » ÷ Alphalog « B » )
     ×  Alphalog « B » Alpha6 « R » EXE « ↵ »
  • SHIFTVARSF1 « COM » F6 « ▷ » F6 « ▷ » F2 « WhileEnd »
    EXE « ↵ »
  • Alphalog « B » SHIFTVARSF5 « ◄ »

Remarque
Décortiquons l’instruction AInt (A÷B)×BR\mathsf{A}- \mathsf{Int}\ (\mathsf{A}\div \mathsf{B}) \times \mathsf{B} \rightarrow \mathsf{R} sur un exemple.
Prenons A=14\mathsf{A}=14 et B=5\mathsf{B}=5 alors :

  • A÷B=2,8\mathsf{A}\div \mathsf{B}=2,8
  • donc Int (A÷B)=2\mathsf{Int}\ (\mathsf{A}\div \mathsf{B})=2
  • donc Int (A÷B)×B=10\mathsf{Int}\ (\mathsf{A}\div \mathsf{B}) \times \mathsf{B}=10
  • ainsi AInt (A÷B)×B=1410=4\mathsf{A}- \mathsf{Int}\ (\mathsf{A}\div \mathsf{B}) \times \mathsf{B}=14-10=4, c’est le reste (R\mathsf{R}) de la division euclidienne de 1414 par 55.

Cours associés

Arithmétique et problèmes de codage