PGCD (TS spé maths)

[Jota Be]

Bonjour à tous et à toutes,
je bloque sur une question d'un exercice : "on désiqne par p un nombre entier naturel. On considère pour tout entier naturel non nul n le nombre A_n=2^(n) +p. On note d_n le PGCD de A_n et A_n+1.
a) Montrer que d_n divise 2^n"

J'ai commencé par chercher le PGCD de A_n et A_n+1, tout bêtement, et je bloque déjà pour le déterminer, donc je requiers votre aide.
Merci.

[Cryptocatron-11]

Salut ,

donc du coup tu tombes sur quel pgcd ?

le raisonnement est simple : on utilise l'algorithme d'euclide.

normalement à la fin tu trouves ce qui est logique. ensuite c'est là que ça devient interessant. on continues et on trouve que . donc si 2^n/p est un entier alors forcément p est ..... ?

[Jota Be]

Salut Cryptocatron et merci,
Tout d'abord, je t'explique comment j'ai fait : 2^(n+1) +p=1*(2^n +p)+2^n
ensuite, 2^n +p=1*(2^n)+p
Là, on est d'accords.
Ensuite, je fais 2^n=0*p+2^n, ce qui visiblement n'est pas la bonne méthode.
En suivant ta démarche, je pose 2^n=p*((2^n)/p), mais qu'est-ce qui me prouve que (2^n)/p appartient aux rationnels ou aux entiers ? On peut partir de la supposition que (2^n)/p est entier, pour cela p serait alors un diviseur de 2^n de la forme 2^x, xdonc ce quotient est de la forme (2^n)/(2^x)=2^z avec z appartenant à N*, z=n-x.
Mais alors, quid du fait que (2^n)/p puisse être rationnel ?

[Cryptocatron-11]

mais qu'est-ce qui me prouve que (2^n)/p appartient aux rationnels ou aux entiers ? ?

Rien du tout. a vrai dire on le sais pas et on s'en fout de le savoir c'est pas ce qu'on cherche. ce qu'on cherche à savoir c'est pourquoi le pgcd divise 2^n. Donc s'il s'avère que ce soit vrai alors p est le PGCD c'est ce que j'attendais comme réponse. et donc forcement p divise 2^n en entier naturel et doncréciproquement on retombe sur ta truc à montrer.

[Jota Be]

On ne peut pourtant pas dire que p divise 2^n si on écrit 2^n=p*x, x un rationnel.

[Cryptocatron-11]

bah si p est le pgcd qu'est ce que t'en déduis pour 2^n/p ?

[el niala]

je trouve votre raisonnement un peu "tordu" :triste:
pourquoi ne pas faire simple ?



avec et

d'où

or

d'où la réponse

[Cryptocatron-11]

je trouve votre raisonnement un peu "tordu" :triste:
pourquoi ne pas faire simple ?



avec et

d'où

or

d'où la réponse

Pourquoi tordu ? pourtant c'est logique. On suppose que p est le pgcd donc si p est lepgcd alors forcément 2^n/p est un entier et donc p=d_n divise 2^n. c'est simple non ? ça tient en deux lignes en comptant l'algorithme qui en fait qu'une. j'ai privilégié le raisonnement intutif ... après libre de suivre le raisonnementqu'on veut

[Jota Be]

On suppose que p est le pgcd donc si p est lepgcd alors forcément 2^n/p est un entier et donc p=d_n divise 2^n.

Là j'ai compris, mais il m'a fallu un peu détailler : Si on suppose que p est le pgcd, alors p|2^(n+1)+p et p|2^n +p donc p|2^(n+1)-2^n soit p|2^n
Mais on suppose que p=d_n. Comment prouver que p est d_n ? Peut-être que cette question est idiote, mais j'aimerais que tu m'expliques un peu plus.

[Jota Be]

je trouve votre raisonnement un peu "tordu" :triste:
pourquoi ne pas faire simple ?



avec et

d'où

or

d'où la réponse

El Niala, quel est ce signe tout en haut ? Que veut-il dire ? Et puis, je ne saisis pas tout ce raisonnement que j'aimerais vraiment comprendre.

Bien qu'il me semble que l'on arrive à la même finalité.

[el niala]

désolé Cryptocatron mais ça ne tient pas en 2 lignes :triste:

car tu commences par affirmer "On suppose que p est le pgcd" ce qui est à tout le moins hasardeux, car si l'on part d'une hypothèse fausse on est tenu à un raisonnement par l'absurde(*) ; de plus l'énoncé précise que le pgcd c'est d_n, donc dans l'esprit de cet exercice on doit s'en tenir à cette notation, puisqu'on ne demande pas (dans un premier temps) de calculer ce PGCD

(*) je peux commencer une démonstration en "supposant" que 1=0 par exemple, elle n'aura aucune valeur si à l'arrivée je ne conclus pas par "donc 10"

je ne voudrais pas polluer ce fil, alors je réponds aussi à la question de Jota Be:

le signe est le symbole du PGCD (en arithmétique, car en algèbre c'est celui du produit vectoriel)
heureusement que l'on revient au même, mais la démarche me semble plus simple et plus dans l'esprit de l'exercice

[Jota Be]

désolé Cryptocatron mais ça ne tient pas en 2 lignes :triste:

car tu commences par affirmer "On suppose que p est le pgcd" ce qui est à tout le moins hasardeux, car si l'on part d'un hypothèse fausse on est tenu à un raisonnement par l'absurde(*) ; de plus l'énoncé précise que le pgcd c'est d_n, donc dans l'esprit de cet exercice on doit s'en tenir à cette notation, puisqu'on ne demande pas (dans un premier temps) de calculer ce PGCD

(*) je peux commencer une démonstration en "supposant" que 1=0 par exemple, elle n'aura aucune valeur si à l'arrivée je ne conclus pas par "donc 10"

je ne voudrais pas polluer ce fil, alors je réponds aussi à l'autre question :

le signe est le symbole du PGCD (en arithmétique, car en algèbre c'est celui du produit vectoriel)
heureusement que l'on revient au même, mais la démarche me semble plus simple et plus dans l'esprit de l'exercice

Tu ne pollues pas du tout le fil. Je trouve que ta participation est claire et tout le monde sait que la confrontation d'idées n'est que bénéfique (pour l'un, pour l'autre, pour les deux). Les remarques, si elles existent, sont constructives, et me permettent de voir quel est le bon cheminement.
J'ai parfaitement compris ta méthode qui de plus répond à la question (il ne fallait pas calculer d_n, et ça je l'avais pas compris !).
Ceci dit, Cryptocatron m'a aussi beaucoup aidé et je vous suis très reconnaissant.
Si j'ai d'autres questions, je continuerai sur ce topic.
A bientôt (d'autres remarques sont les bienvenues).

[Cryptocatron-11]

désolé Cryptocatron mais ça ne tient pas en 2 lignes :triste:

car tu commences par affirmer "On suppose que p est le pgcd" ce qui est à tout le moins hasardeux, car si l'on part d'une hypothèse fausse on est tenu à un raisonnement par l'absurde(*) ; de plus l'énoncé précise que le pgcd c'est d_n, donc dans l'esprit de cet exercice on doit s'en tenir à cette notation, puisqu'on ne demande pas (dans un premier temps) de calculer ce PGCD

Je suppose p=d_n je vois vraiment pas ou c'est faux. c'est comme dans démonstration je suppose x>1 c'est pas toujours vrai pourtant on le suppose bien non pour démontrer des trucs?
et ensuite j'ai le droite de poser




enfin bref je suis pas là pour avoir raison mais je vois pas pourquoi je peux pas supposer ça

[el niala]

Je suppose p=d_n je vois vraiment pas ou c'est faux. c'est comme je suppose x>1 c'est pas toujours vrai pourtant on le uppose bien non ?

la différence est fondamentale :

p est unique
d_n est unique

alors que x ne l'est pas

[Cryptocatron-11]

OK je ne le savais pas que l'unicité changeais quelque chose merci pour la remarque

[Skullkid]

Salut, l'idée c'est que l'objet p est déjà défini par l'énoncé : c'est un entier naturel quelconque fixé. Tu ne peux pas lui ajouter d'autres propriétés.

Si on te donne un réel x quelconque, tu violes la généralité de l'énoncé en supposant x > 1. Tu peux restaurer cette généralité en traitant a posteriori le cas x <= 1 (puisqu'un réel quelconque est forcément soit strictement supérieur à 1, soit inférieur ou égal à 1), mais tant que ce n'est pas fait, le problème n'est que partiellement résolu. Ici, ta démo ne marche que si p est effectivement le pgcd. Mais tu n'as pas prouvé que c'était le cas, tu as prouvé que si c'était le cas, alors [...].

Le pgcd de 2^1 + 3 et de 2^(1+1) + 3 n'est pas égal à 3, en revanche il divise bien 2^1.

[Cryptocatron-11]

OK merci pour vos corrections

[Jota Be]

J'ai à nouveau besoin d'une piste de réflexion.
Un peu plus loin, on me demande de déterminer la parité de A_n en fonction de celle de p. Je l'ai fait.
Ensuite, je rencontre une question où on me demande de déterminer la parité de d_n en fonction de celle de p. Alors là, gros blanc. Je suis en train d'y réfléchir. Si vous avez des indices, n'hésitez pas.

[Jota Be]

En partant du fait que 2^n +p=d_n*k et que 2^n=d_n*q, j'écris :
p=k*d_n-q*d_n=(k-q)d_n
Mais je doute que cela soit la bonne voie.

[el niala]

En partant du fait que 2^n +p=d_n*k et que 2^n=d_n*q

effectivement ça n'apporte pas grand chose

je suppose que tu as trouvé A_n de la parité de p

pour la suite, dans les exercices, les questions ne sont pas posées au hasard, tu ne vois pas le rapport entre la parité de d_n et le résultat précédent (d_n divise 2^n) ?