Répondre à la discussion
Affichage des résultats 1 à 17 sur 17

Divisibilité dans Z, congruence et récurrence.



  1. #1
    Tonio59225

    Divisibilité dans Z, congruence et récurrence.


    ------

    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.

    -----

  2. Publicité
  3. #2
    Tonio59225

    Re : Divisibilité dans Z, congruence et récurrence.

    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.

  4. #3
    Flyingsquirrel

    Re : Divisibilité dans Z, congruence et récurrence.

    Salut,
    Citation Envoyé par Tonio59225 Voir le message
    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.

  5. #4
    skavonette

    Re : Divisibilité dans Z, congruence et récurrence.

    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?

  6. #5
    Tonio59225

    Re : Divisibilité dans Z, congruence et récurrence.

    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?

  7. A voir en vidéo sur Futura
  8. #6
    skavonette

    Re : Divisibilité dans Z, congruence et récurrence.

    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 ?

  9. Publicité
  10. #7
    Tonio59225

    Re : Divisibilité dans Z, congruence et récurrence.

    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.

  11. #8
    skavonette

    Re : Divisibilité dans Z, congruence et récurrence.

    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

  12. #9
    Tonio59225

    Re : Divisibilité dans Z, congruence et récurrence.

    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?

  13. #10
    skavonette

    Re : Divisibilité dans Z, congruence et récurrence.

    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é

  14. #11
    Tonio59225

    Re : Divisibilité dans Z, congruence et récurrence.

    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é?

  15. #12
    Flyingsquirrel

    Re : Divisibilité dans Z, congruence et récurrence.

    Citation Envoyé par Tonio59225 Voir le message
    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.

    Citation Envoyé par Tonio59225 Voir le message
    P(n+1)=2^(3n+1)-1
    Non. Au rang il faut montrer que est divisible par 7, tu as oublié les parenthèses.

  16. Publicité
  17. #13
    Tonio59225

    Re : Divisibilité dans Z, congruence et récurrence.

    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.

  18. #14
    Flyingsquirrel

    Re : Divisibilité dans Z, congruence et récurrence.

    Citation Envoyé par Tonio59225 Voir le message
    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 no2 : pour utiliser l'hypothèse de récurrence tu peux exprimer en fonction de ...

  19. #15
    Tonio59225

    Re : Divisibilité dans Z, congruence et récurrence.

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

  20. #16
    Flyingsquirrel

    Re : Divisibilité dans Z, congruence et récurrence.

    Citation Envoyé par Tonio59225 Voir le message
    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 :

  21. #17
    Tonio59225

    Re : Divisibilité dans Z, congruence et récurrence.

    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.

Sur le même thème :

Discussions similaires

  1. spé maths TS congruence et divisibilité
    Par Sacreebetuz dans le forum Mathématiques du collège et du lycée
    Réponses: 7
    Dernier message: 17/10/2009, 20h56
  2. Congruence et divisibilité
    Par Daisy3 dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 21/08/2009, 20h29
  3. Spé Maths : divisibilité et congruence
    Par Edwik dans le forum Mathématiques du collège et du lycée
    Réponses: 8
    Dernier message: 14/10/2008, 23h10
  4. spé maths TS : divisibilité et congruence
    Par x-lue-x dans le forum Mathématiques du collège et du lycée
    Réponses: 8
    Dernier message: 30/09/2008, 20h59
  5. problème spé maths, divisibilité, congruence
    Par zorglube dans le forum Mathématiques du collège et du lycée
    Réponses: 0
    Dernier message: 01/11/2006, 09h32