Dm math spé : division euclidienne


  • X

    J'ai des difficultés pour mon dm que voici :

    Enoncé

    **1.**Soit n un entier naturel.
    Démontrer que le reste de la division euclidienne de
    2^n + 2^(n-1) +.....+ 2 + 1
    par 2^n
    est 2^(n-1) +.....+ 2 + 1.

    Réponses
    J'utilise la formule a=bq+r avec :
    a = 2^n + 2^(n-1) +.....+ 2 + 1
    b = 2^n
    r = 2^(n-1) +.....+ 2 + 1

    On m'a dit de faire la relation avec une suite géometrique mais je ne vois pas comment faire du tout.😕

    Alors si vous avez une idée. Merci d'avance.


  • M

    Bonjour,
    Tu sais calculer la somme : 1 + a + a² +...+ an−1a^{n-1}an1
    Qu'est-ce que cela donne pour a = 2 ?
    Il te restera alors à vérifier que r < b


  • X

    Merci .Si je comprends bien, on fait la somme des 1er termes d'une suite géometrique.
    S=1*(1-q^(n+1))/(1-q)
    je suppose que q=2
    S=(1-2^(n-1+1))/(1-2)
    S=(1-2^n)/-1
    S=-1+2^n
    Si je n'est pas fait de faute, je vois pas comment je dois conclure et comment on prouve que c'est une suite géometrique ?
    r<b donc 2^(n-1) +.....+ 2 + 1 < 2^n ............. ?


  • M

    Sn−1S_{n-1}Sn1 = 1 +2 +2² + ... + 2n−12^{n-1}2n1 = 2n2^n2n - 1
    et SnS_nSn = 1 + 2 + 2² +...+ 2n2^n2n son t des suites géométriques : rien à prouver : il suffit d'observer.
    Ensuite : Sn−1S_{n-1}Sn1 = 2n2^n2n - 1 , donc Sn−1S_{n-1}Sn1 < 2n2^n2n , donc en revenant à tes notations : r < b
    Pour l'égalité de la division euclidienne , reste à voir quel est le quotient .


  • X

    a=bq+r
    -1+2^(n+1)=2^n*q-1+2^n
    donc q=(-1+2^(n+1)+1-2^n)/2^n
    q=(2^(n+1)-2^n)/2^n
    q=1
    es ce bon ?


  • M

    Oui mais c'est trop compliqué :
    a = 2n2^n2n + (2n−1(2^{n-1}(2n1 + ...+ 1)
    a = 1<em>2n1<em>2^n1<em>2n + r
    a = 1b + r
    Sans oublier ce qui est fondamental : r < b


  • X

    soit N un entier naturel strictement positif. demontrer que N peut s'ecrire de facon unique comme une somme de puissance de 2.
    je vous montre le debut de mon raisonnement en cascade:
    N est soit pair soit impaire -si N est pair:N/2=q -si N est impair:N/2=q avec un reste de r=1
    donc N=2q ou N=2q+1
    ensuite, q est soit pair soit impair -si q est pair:q/2=q1 -si q est impair:q/2=q1 avec un reste r=1
    Donc q=2q1 ou q=2q+1
    D'ou N=2^2q1 ou N=2^2q1+2 ou N=2^2q1+1 ou N=2^2q1+2+1

    On a donc N>q>q1>q2…..

    et je continu ainsi de suite,( j ai aussi fait avec q2 mais ca continu comme ca a commencé, a par qu au lieu d avoir 4 solution j en ai 8), comme ca ,ca peut durer tres longtemps, donc voila, si les quelques personnes qui ont compris ce que j ai ecrit pouvais me dire comment terminer mon raisonnemnet ou comment faire cela plus rapidemant ce serait cool


  • M

    C'est vrai seulement à partir de N = 1
    Sauf si l'on fait la remarque suivante :
    une somme de puissance de 2 est une écriture de la forme
    aaa_n2n2^n2n + ... + aaa_1212^121 + aaa_0202^020 , où les aia_iai valent 0 ou 1 .
    Il s'agit en fait de l'écriture du nombre en base 2.
    Il est facile de démontrer le résultat par récurrence sur N : il faut poser correctement l'hypothèse de récurrence.


  • X

    D'abord, je voulez vous remercier de votre aide précieuse .
    Mais Désolé je ne comprend pas vraiment 😕


  • M

    Par exemple, pour N = 3 : 3 = 1<em>211<em>2^11<em>21 + 1</em>201</em>2^01</em>20
    Pour n = 4 : 4 = 2² = 12² + 0</em>210</em>2^10</em>21 + 0∗200*2^0020

    H.R : supposons la propriété vraie pour tous les entiers inférieurs à N
    ta division euclidienne par 2 donne N = 2*q+ r , avec r = 0 ou 1.
    Et HR est vraie pour q car q < N comme tu l'avais remarqué.
    Donc q = 2p2^p2p + aaa_{p-1}2p−12^{p-1}2p1 + ... + aaa_0202^020
    Il n'y a plus qu'à remplacer dans l'expression de N


  • X

    Encore une fois merci beaucoup


  • M

    De rien
    A+


  • X

    Reboujour, j'ai encore un problème.Pour la question 1, on doit trouver le reste. Donc je fait les deux suites géomtriques mais normalement il faudrait trouver la valeur de q dans "a=bq+r" avant de faire :
    −1+2-1+21+2^{n+1}=2n=2^n=2n-q+r
    −1+2-1+21+2^{n+1}−2n-2^n2n=r
    −1+2n-1+2^n1+2n
    et là on prouve vraiment que r = −1+2n-1+2^n1+2n mais avant il faut trouver q Comment fait-on ?


  • M

    On te demande uniquement le reste.
    Mais on avait déjà trouvé le quotient :
    Citation
    a=bq+r
    -1+2^(n+1)=2^n*q-1+2^n
    donc q=(-1+2^(n+1)+1-2^n)/2^n
    q=(2^(n+1)-2^n)/2^n
    q=1
    es ce bon ?

    Citation
    Oui mais c'est trop compliqué :
    a = 2n + (2n-1 + ...+ 1)
    a = 12n + r
    a = 1
    b + r
    Sans oublier ce qui est fondamental : r < b


  • X

    Oui mais on se sert déja du reste alos qu'on ne le pas encore trouvé. NON ?


  • M

    Non : relis
    l'ensembledu raisonnement.
    Je dois maintenant me déconnecter.
    A+


Se connecter pour répondre