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... Licence Maths 1e ann ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau Licence Maths 1e ann
Ex PGCD
Posté par wai
Bonjour,
j'ai l'exercice de PGCD , aide moi svp
on a :
x>y>=0;
fonction PGCD(x, y entier)
{
if y=0 then return x ;
else return PGCD(y, x mod y);
}
Question:
Soit n(x,y) le nombre divisions ("mod")effectuees par l'algorithme
Montrer que n(x,y) = 0 si y =0
= 1+n(y, x mod y) sinon
Montrer par récurrence que pour x>y>=0 , si n(x,y)=k alors x> F(k+2) (ou F(k+2) est le k+2 éme terme de la suite de Fibonacci
F(n): =0 si n=0
=1 si n=1
=F(n-1)+ F(n-2) si n>=2
et F(n) = 1\sqrt5 *(phi^n - phi'^n).
merci d'avance
c'est un algorithme recursif
a chaque passage qd y est different de 0 on fait une division euclidienne
(d'où le +1 ds le nombre de division)
premiere division de x par y
x=yq+r
et on rappelle la fonction pgcd(y,r)
si r est different de 0 on fait une division euclidienne
(d'où le +1 ds le nombre de division)
de y par r
y=rq+r2
et on rappelle la fonction pgcd(r,r2)
et ainsi de suite
je comprend bien que c'est algorithme
mais ici , je sais pas comment montrer si n(x,y)=k alors x >= F(k+2)