Inscription / Connexion Nouveau Sujet
Calcul de PGCD
Bonsoir,
Voici l'énoncé de l'exercice
Soit n ∈ N*. Calculons 5^n - 1 et 5^{n+1} - 1.
Pour cela, j'ai utilisé le théorème de Bézout. Soient a et b des entiers relatifs. D'après le théorème de Bézout, il existe deux entiers u et v tels que :
a u + b v = PGCD(a, b)
Ainsi, nous avons :
<=>
Montrons que
Cela peut être montré par récurrence. Pour tout n ∈ N*, montrons que avec k ∈ Z. Faut-il faire une deuxième récurrence pour montrer que
, ou peut-on simplement le déduire à partir de la première récurrence ?
J'aimerais aussi utiliser une autre méthode (qui me semble moins longue) :
Mais je ne sais pas comment montrer que cette somme est égale à 4k.
Merci pour votre aide,
salut
que signifie
Voici l'énoncé de l'exercice
Soit n ∈ N*. Calculons 5^n - 1 et 5^{n+1} - 1.
alors une remarque dans la rédaction :
Montrons que
(*) te permet seulement de conclure que le pgcd divise 4 mais tu n'es pas certain que ce pgcd est 4
il ne faut donc pas dire "montrons" mais "vérifions si " ...
Bonjour,
Je réponds à cette question :
Pour tout n ∈ N*, montrons que
* alors 4 divise 5m-1 pour tout m de *.
Remplacer m par n+1
Par ailleurs le théorème de Bezout n'est pas utile.
En effet, si au + bv = c
et que
d
est le pgcd de
a
et
b
alors da'u + db'v = c
; donc
d
divise
c .
Ça n'utilise que des choses élémentaires sur la divisibilité.
Je propose cette rédaction :
On a
.
Donc le pgcd cherché est un diviseur de 4.
Il reste à démontrer que 4 divise les deux entiers
et
.
Bonjour,
Merci pour vos retours, je prends en compte vos corrections sur ma rédaction
En revanche, si j'utilise le théorème de Bézout, je ne suis pas sûre de comprendre pourquoi il est nécessaire de vérifier que 4 divise les 2 entiers a et b. J'ai fait plusieurs exercices où ce n'était pas le cas
a \;
Donc le pgcd cherché est un diviseur de 4.
Il reste à démontrer que 4 divise les deux entiers
Pour moi, le théorème de Bézout s'écrit avec 1 au second membre.
De plus, on peut avoir au+bv = c sans que c soit le pgcd de a et b.
Dans mon cours, le théorème de Bézout est défini comme suit :
au+bv = PGCD(a, b)
Mais oui, il me semble avoir vu qu'il s'agissait plutôt de l'identité/relation de Bézout et que le théorème de Bézout est plutôt le suivant : Soient a et b deux entiers premiers entre eux, il existe 2 entiers relatifs u et v tels que : au+bv = 1.
Donc pour être tout à fait exacte, je
devrais plutôt parler de la relation de Bézout si je comprends bien ?
Pour l'exercice suivant : Déterminer le pgcd de 9n+4 et 2n-1 (avec n entier naturel), je suis donc censée vérifier que le pgcd obtenu divise 9n+4 et 2n-1 ?
Mais je n'aurais donc pas besoin de faire une vérification si l'énoncé est le suivant : Montrer que 9n+4 et 2n+1 sont premiers entre eux ?
Dans mon cours, le théorème de Bézout est défini comme suit :
au+bv = PGCD(a, b)
Pour répondre à ta dernière question :
Si
On le sait bien avant d'avoir rencontré le théorème de Bézout.
Il suffit d'écrire
Il est écrit :
Théorème de Bézout : Soient a et b deux entiers relatifs tels que a,b différents de 0. Il existe 2 entiers relatifs u et v tels que :
PGCD(a, b) = au + bv (relation de Bézout).
Je vois, merci.
oui ça ne va pas et il faut revenir aux choses de base et dans l'ordre :
1/ si d divise a et b alors d divise toute combinaison linéaire de a et b
2/ si d = pgcd (a, b) alors il existe des entiers u et v tels que au + bv = d
3/ donc s'il existe des entiers p et q tels que m = pa + qb la seule chose que tu sais c'est que tout diviseur commun à a et b divise m
donc que ce n'est pas parce qu'un entier n s'écrit n = ax + by que n est le pgcd de a et b
et comme Sylvieg le dit cela n'est vrai que si n = 1
Oui, je comprends mieux. Merci
1. Cela signifie qu'il existe 2 entiers u et v tels que d|au+bv ?
Donc à partir du moment où le pgcd est différent de 1, il est nécessaire de vérifier que n divise a et b ?
Annuler
connectez vous