PGCD - term S spé maths

[Anonyme]

Bonsoir à tout le monde,

J'ai un problème dans un exercice à une sous-question.
J'ai la réponse mais je ne la comprends pas donc s'il y a d'autres façons d'arriver à trouver la même, chose, je souhaiterai bien qu'on m'explique.

7°)
a-démontrer que pour tout entier naturel n, 2xn-yn=5. (fait)
b-exprimer yn en fonction de n. (fait)
c-en utilisant les congruences modulo 5, éudier suivant les valeurs de l'entier narturel p le reste de la division euclidienne de 2^p par 5. (fait)
d-on note dn le pgcd de xn et yn pour tout entier naturel n.
Démontrer que l'on a dn=1 ou dn=5; en déduire l'ensemble des entiers naturels n tels que xn et yn soient premiers entre eux.

Réponse de la d- :

xn et yn sont premiers entre eux si et seulement si n+1 n'est pas divisible par 4.

Comment arrive-t-on à cette réponse ?
Je sais que le PGCD de xn et yn est dn donc dn divise 2xn - yn = 5.
5 est un nombre premier donc on déduit que dn = 1 ou dn = 5.

Et après ?

Merci d'avance !

[Nightmare]

Salut,

quelles sont les définitions de xn et yn?

[Anonyme]

Les suites d'entiers naturels (xn) et (yn) sont définies sur N par :
x0 = 3 et xn+1 = 2xn - 1
yo = 1 et yn+1 = 2yn + 3

- J'ai démontré par récurrence que pour tout n appartenant à N, xn = 2^(n+1) + 1.
- J'ai prouvé que xn et xn+1 sont premiers entre eux pour tout entier naturel n.

[Anonyme]

Petit Up du sujet ;)

[Nightmare]

Ok,

tu as montré précédemment que le PGCD de xn et yn est soit 1, soit 5. Pour qu'ils soient premiers entre eux, il faut donc pouvoir éliminer le cas où ce PGCD peut être égal à 5.

Or, dire que ce PGCD vaut 5 revient à dire que xn et yn sont tous les deux divisibles par 5.

En prenant la contrapposée de cette affirmation, on en déduit que le PGCD ne vaut pas 5 (donc vaut 1) quand l'un des deux parmi xn et yn n'est pas divisible par 5.

On connait les expressions de xn et yn, on devrait pouvoir déterminer sous quelle(s) condition(s) ils ne sont pas divisibles par 5.

Je te laisse y réfléchir.

[Anonyme]

On sait que 2xn-yn = 5 donc yn = 2xn - 5

dn = PGCD(xn;yn) = PGCD(xn;2xn-5)= PGCD(xn;xn-5) = PGCD(xn;5)
5 est un nombre premier. Si 5 divise xn, alors dn = 5 sinon dn = 1.

xn et yn sont premiers entre eux ssi dn = 1 ssi 5 ne divise pas xn.

Supposons que dn = 5 alors yn est divisible par 5.
Donc yn congru 0 [5]
Donc 2^n+2 - 3 congru 0 [5]
Donc 2^n+2 congru 3 [5]
Donc n+2 = 4k+3 avec k appartient à N.
On en déduit que : n = 4k + 1 avec k appartient à N.

Réciproquement, si n = 4k + 1 avec k appartient à N.
Alors yn congru 2^n+2 - 3 congru 3 - 3 congru 0 [5]
Donc yn est divisible par 5.
Et xn congru 2^n+1 + 1 congru 2^]4k+2 congru 4+1 congru 0 [5]
Donc xn est divisible par 5.

On en déduit que dn = 5.

dn = 5 si et seulement si n = 4k+1 avec k appartient à N.
dn = 1 si et seulement si n différent de 4k+1 avec k appartient à N.

Donc xn et yn sont premiers entre eux si et seulement si n - 1 n'est pas divisible par 4.


Correction ?

[Nightmare]

C'est niquel.

[Anonyme]

Merci ;)
Bonne semaine !