Divisibilité dans Z, congruence et récurrence.

[invitebf69b977]

Bonjour à tous, j'ai besoin que vos lumières éclaire ma lanterne.
En l'occurence, mon professeur de mathématiques nous a donné un DM en spécialité à rendre pour jeudi.
J'ai cherché durant toutes les vacances à résoudre cet exercice, néanmoins, je n'y arrive pas.
J'ai donc besoin de vous, pour un exercice type BAC selon mon bouquin.

1/Démontrez par récurrence que, pour tout entier naturel n, 2^(3n+1)-1 est divisible par 7.

2/Déduisez en que 2^(3n+1)-2 est un multiple de 7 et que 2^(3n+2)-4 est un multiple de 7.

3/Déterminez les restes de la division par 7 des puissances de 2.

J'ai donc tenté de faire une récurrence, l'initialison pour n=0 passe tranquillement, je bloque à l'hérédité.
Merci d'avance pour vos conseils, si vous pouviez me guider un peu, histoire que je sache quoi faire dans cet exercice.
-----

[invitebf69b977]

J'ai oublié de mettre ce que j'ai tenté.

Je passe le blabla de l'hérédité:
P(n)=(2^(3n)-1)/7=0

J'ai essayé deux choses:

1) P(n+1)=(2^(3(n+1))-1)7
=(2^(3n+3)-1)/7
Et là je bloque.

2) (2^(3n)-1)/7+2^(n+1)
=(2^(3n)-1)/7+(7(2^(n+1))/7
=((2^(3n)-1)(7(2^n+1))/7
Là je bloque encore.

[Flyingsquirrel]

Salut,

J'ai donc tenté de faire une récurrence, l'initialison pour n=0 passe tranquillement, je bloque à l'hérédité.

Pour prouver l'hérédité tu peux commencer par exprimer en fonction de qui, par hypothèse, est divisible par 7.

[inviteac5028a9]

bonjour,
Pour ma part je te propose comme hypothèse de dire
et de démontrer que pour n+1 p(n+1)=7k'
Tu vois ce que je veux dire?

[A voir en vidéo sur Futura]

[invitebf69b977]

Désolé Skavonette, je ne vois pas trop ce que tu veux dire.
Ensuite, j'ai fais une erreur dans l'énoncé, rattrapable selon ce que tu m'a dis Flyingsquirrel, dans la question 1, ce n'est pas 2^(3n+1)-1 mais 2^(3n)-1.
Je peux donc exprimer 2^(3n+1)-1 en fonction de 2^(3n)-1 qui par hypothèse est divisible par 7 non?

Si oui, je l'ai fais d'avance:
P(n+1)=2^(3n+1)-1

Mais que faire une fois arrivée là, si j'ai le bon résultat?

[inviteac5028a9]

ce que je te propose est le raisonnement suivant :
hypothèse de récurrence : admettons que est divisible par 7
donc on peut l'écrire sous forme où k est un coefficient entier naturel.

pour l'hérédité il te suffit de démontrer que pour n+1, est toujours égal à .
Donc si pour n+1 le nombre s'écrit qu'on a appelé ici Alors il reste toujours divisible par 7 quelquesoit n.

tu me suis maintenant ?

[invitebf69b977]

Effectivement, je te suis et je comprends ton raisonnement.
Peut-on y arriver par congruence?
2^(3n)=2^(3)n
2^((3)n)-1 congrues à -1 modulo 7.

[inviteac5028a9]

oui on peut y arriver par les congruences :
comme hypothèse tu prends, prenons est divisible par 7 alors on peut dire que

il te suffit te prouver dans l'hérédité que

[invitebf69b977]

2^(3n)-1 congrue 0 modulo 7
=2^(3n) congrue 1 modulo 7

Or 2^3 congrue 8 modulo 7, congrue à 1 modulo 7.
D'où 2^3n = (2^3)^n
2^3n congrue 1^n modulo 7, congrue à 1 modulo 7.
2^(3n)-1 congrue à 0 modulo 7.

Donc 2^(3n+1)-1 = ((2^3)^n+1)-1
D'où 2^(3n+1) congrue à 1^(n+1) modulo 7.
2^(3n+1) congrue à 1 modulo 7.
2^(3n+1)-1 congrue à 0 modulo 7.

Est-ce bon?

[inviteac5028a9]

ce que tu dis est juste mais ce n'est pas un raisonnement par récurrence là or ton énoncé dis qu'il faut le démontrer par récurrence!

Sert toi de ce que tu as écrit et met le sous la forme d'un raisonnement par récurrence et le tour est joué

[invitebf69b977]

P(n)= 2^(3n)-1

Initialisation:
P(1)= 2^(3*1)-1=2^(3)-1=8-1=7
7 Est divisible par 7 alors P(1) vraie.

Hérédité:
Je suppose qu'il existe une valeur n tel que P(n) vraie, montrons qu'alors P(n+1) vraie.
P(n+1)=2^(3n+1)-1= ((2^3)^n+1)-1
D'où 2^(3n+1) congrue à 1^(n+1) modulo 7.
2^(3n+1) congrue à 1 modulo 7.
2^(3n+1)-1 congrue à 0 modulo 7.
Donc 2^(3n+1)-1 est divisible par 7.
Alors P(n) vraie => P(n+1) vraie.

Conclusion:
P(1) vraie
P(n) vraie=> P(n+1) vraie
Donc P(n) vraie pour tout n appartenant à N.

Je pense m'en être tiré?

[Flyingsquirrel]

P(n)= 2^(3n)-1

Initialisation:
P(1)= 2^(3*1)-1=2^(3)-1=8-1=7
7 Est divisible par 7 alors P(1) vraie.

Hérédité:
Je suppose qu'il existe une valeur n tel que P(n) vraie, montrons
qu'alors P(n+1) vraie.

Ça n'a pas tellement de sens de dire que — qui est un nombre — est vrai. Par contre si l'on appelle l'affirmation « est divisible par 7 » alors on a le droit de dire que est vraie ou fausse.

P(n+1)=2^(3n+1)-1

Non. Au rang il faut montrer que est divisible par 7, tu as oublié les parenthèses.

[invitebf69b977]

Merci Flyingsquirrel:
Je me suis corrigé, néanmoins le fait que j'ai oublié une parenthèse ne change rien au résultat si je ne me trompe pas?

P(n) = l'affirmation "2^(3n)-1 est divisible par 7"

Initialisation:
P(1)= 2^(3*1)-1=2^(3)-1=8-1=7
7 Est divisible par 7 alors P(1) vraie.

Hérédité:
Je suppose qu'il existe une valeur n tel que P(n) vraie, montrons qu'alors P(n+1) vraie.
P(n+1)=2^(3(n+1))-1= ((2^3)^(n+1)-1
D'où 2^(3(n+1)) congrue à 1^(n+1) modulo 7.
2^(3(n+1)) congrue à 1 modulo 7.
2^(3(n+1))-1 congrue à 0 modulo 7.
Donc 2^(3(n+1))-1 est divisible par 7.
Alors P(n) vraie => P(n+1) vraie.

Conclusion:
P(1) vraie
P(n) vraie=> P(n+1) vraie
Donc P(n) vraie pour tout n appartenant à N.

[Flyingsquirrel]

Hérédité:
Je suppose qu'il existe une valeur n tel que P(n) vraie, montrons qu'alors P(n+1) vraie.
P(n+1)=2^(3(n+1))-1= ((2^3)^(n+1)-1
D'où 2^(3(n+1)) congrue à 1^(n+1) modulo 7.
2^(3(n+1)) congrue à 1 modulo 7.
2^(3(n+1))-1 congrue à 0 modulo 7.
Donc 2^(3(n+1))-1 est divisible par 7.
Alors P(n) vraie => P(n+1) vraie.

C'est correct mais tu ne te sers pas de l'hypothèse de récurrence pour prouver que la propriété est héréditaire donc tu ne fais pas un raisonnement par récurrence comme on te le demande. On en revient à la suggestion faite au message n^o2 : pour utiliser l'hypothèse de récurrence tu peux exprimer en fonction de ...

[invitebf69b977]

Je ne vois pas comment exprimer ceci, j'en ai discuté avec un camarade il sais pas non plus l'exprimer.
Je m'excuse.

[Flyingsquirrel]

Je ne vois pas comment exprimer ceci, j'en ai discuté avec un camarade il sais pas non plus l'exprimer.
Je m'excuse.

Ce n'est pas la peine de t'excuser, tu as le droit de ne pas trouver.

Il faut jouer avec l'écriture du nombre pour faire apparaître ce qui nous intéresse :

[invitebf69b977]

Ah oui, elles sont biens ces astuces là pour arriver au résultat intéressant.
Merci beaucoup Flyingsquirrel, j'essaierais de m'en rappeller pour de futurs exercices de ces façons de faire apparaître les choses.