Annuler
connectez vous
arithmétique en post-bac
- Arithmétique dans Z - supérieur
- Exercice : le petit théorème de Fermat
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Un best-of d'exos de probabilités (après le bac)
- Espaces vectoriels et Applications linéaires - supérieur
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Maths sup ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau Maths sup
Algorithme d'Euclide
Posté par 
Ramanujan
RamanujanBonsoir,
def pgcd(a,b) :
while b!=0
(a,b) =(b,a%b)
return aJe ne comprends pas pourquoi si le PGCD est le dernier reste non nul, on affiche à la fin a
On devrait afficher a%b non ?
et
On a
ici
Donc le PGCD vaut 5. Ok merci je vois.
J'aimerais démontrer dans le cadre général que le dernier reste non nul est le PGCD.
D'après le cours
Et
Par exemple, si est le dernier reste non nul. Comment montrer que
?
On sait que
Mais après je bloque.
Je suis d'accord mais je ne vois pas en quoi ça m'aide à résoudre mon problème.
Comment montrer que le PGCD est le dernier reste non nul ?
salut
pgcd(a,b)=pgcd(b,r1)=pgcd(r1,r2)=pgcd(r2,r3)
dans l'exemple donné
a = b.q1 + r1 --> 35=25.1+10
b=r1.q2 +r2 --> 25=10.2+5
r1=r2.q2+r3 --> 10=5.2+0
soit
pgcd(35,25)=pgcd(25,10)=pgcd(10,5)=pgcd(5,0)=5 c'est donc bien le dernier reste non
nul