How to prove a simple equation?












1












$begingroup$


I have reason(empirical calculations) to think the following statement is true:



For any $k in mathbb{N}$, there exist $s in mathbb{N}$ such that the expression



$$9*s+3+2^{k}$$



is a power of $2$.



To me it seems like a silly statement, but I don't know how I would go about proving it. Any ideas, or references?



THank you.










share|cite|improve this question









$endgroup$

















    1












    $begingroup$


    I have reason(empirical calculations) to think the following statement is true:



    For any $k in mathbb{N}$, there exist $s in mathbb{N}$ such that the expression



    $$9*s+3+2^{k}$$



    is a power of $2$.



    To me it seems like a silly statement, but I don't know how I would go about proving it. Any ideas, or references?



    THank you.










    share|cite|improve this question









    $endgroup$















      1












      1








      1





      $begingroup$


      I have reason(empirical calculations) to think the following statement is true:



      For any $k in mathbb{N}$, there exist $s in mathbb{N}$ such that the expression



      $$9*s+3+2^{k}$$



      is a power of $2$.



      To me it seems like a silly statement, but I don't know how I would go about proving it. Any ideas, or references?



      THank you.










      share|cite|improve this question









      $endgroup$




      I have reason(empirical calculations) to think the following statement is true:



      For any $k in mathbb{N}$, there exist $s in mathbb{N}$ such that the expression



      $$9*s+3+2^{k}$$



      is a power of $2$.



      To me it seems like a silly statement, but I don't know how I would go about proving it. Any ideas, or references?



      THank you.







      number-theory discrete-mathematics recreational-mathematics






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked 1 hour ago









      ReverseFlowReverseFlow

      604513




      604513






















          5 Answers
          5






          active

          oldest

          votes


















          2












          $begingroup$

          The statement that $9s + 3 + 2^k$ is a power of $2$ for some $sinBbb{N}$ is equivalent to saying $2^k + 3 equiv 2^n pmod 9$ for some $ngt k$. Since the values of $2^kbmod 9$ are the periodic sequence $1,2,4,8,7,5,1,2,4,8,7,5,ldots$ consisting of all values which are not multiples of $3$, this is true.



          For example, take $k = 5$. Then $2^k + 3 = 35 equiv 8 pmod 9$ and the next power of $2$ which is congruent to $8$ is $2^9 = 512$. So in this case $s = (512 - 35)/9 = 53$.






          share|cite|improve this answer









          $endgroup$





















            1












            $begingroup$

            $9cdot s+3+2^k=2^{j+k} Rightarrow 2^k(2^j-1)-3 equiv 0 mod 9 Rightarrow 2^k(2^j-1) equiv 3 mod 9$



            $2^k mod 9$ cycles through $2,4,8,7,5,1,$ etc. so $2^j-1 mod 9$ cycles through $1,3,7,6,4,0$ etc.



            For any residue of $2^k$ it is possible to find a residue of $2^j-1$ such that their product equals $3 mod 9$, viz: $2cdot 6; 4cdot 3; 8cdot 6; 7cdot 3; 5cdot 6; 1cdot 3$



            So your observation is true.



            NB As I typed this, I see that Fred H has given a similar answer.






            share|cite|improve this answer









            $endgroup$





















              1












              $begingroup$

              Euler's Theorem tells us $2^6 equiv 1 pmod 9$ and direct calculation shows so



              $2^{6k + i; i=0...5}equiv 1,2,4,8,7,5 pmod 9$.



              So $2^m - 2^k equiv 3 pmod 9$ if



              $kequiv 0 pmod 6;2^kequiv 1pmod 9$ and $mequiv 2pmod 6; 2^mequiv 4pmod 9$.



              $kequiv 1 pmod 6;2^kequiv 2pmod 9$ and $mequiv 5pmod 6; 2^mequiv 5pmod 9$.



              $kequiv 2 pmod 6;2^kequiv 4pmod 9$ and $mequiv 4pmod 6; 2^mequiv 7pmod 9$.



              $kequiv 3 pmod 6;2^kequiv 8pmod 9$ and $mequiv 1pmod 6; 2^mequiv 2pmod 9$ (So $2^m - 2^k equiv 2-8equiv -6equiv 3 pmod 9$).



              $kequiv 4 pmod 6;2^kequiv 7pmod 9$ and $mequiv 0pmod 6; 2^mequiv 1pmod 9$.



              $kequiv 5 pmod 6;2^kequiv 5pmod 9$ and $mequiv 3pmod 6; 2^mequiv 9pmod 9$.



              So for any $k$ there will exist infinitely many $m > k$ (Actually we don't need $m > k$ as $s$ may be negative but... nice answers are nicer) so that $2^m - 2^k equiv 3 pmod 9$.



              So that means for any $k$ there will exist $s$ and $m$ (actually infinitely many $s$ and $m$) so that



              $2^m - 2^k = 9s + 3$ or



              $9s+3 + 2^k$ a power of $2$.



              (I take a dog for a walk and three people post a similar to identical answer. sigh. Anyway hopefully this answer may (or may not) provide a possible fresh take... There's always more than one way to do or explain things.)






              share|cite|improve this answer











              $endgroup$





















                0












                $begingroup$

                If $9s+3 = 3cdot 2^k$,
                this will work.



                Then
                $3s+1 = 2^k$,
                so $3|2^k-1$.



                This works for even $k$.



                More generally,
                it works if
                $9s+3 = (2^m-1)2^k$
                for some $m$.



                To get rid of the 3
                requires $m$ even,
                so write this as
                $9s+3
                = (4^m-1)2^k
                = 3sum_{j=0}^{m-1}4^j2^k
                $

                or
                $3s+1
                = 2^ksum_{j=0}^{m-1}4^j
                $
                .



                Mod 3,
                we want
                $1
                =2^ksum_{j=0}^{m-1}4^j
                =2^km
                $

                so if
                $2^km = 1 bmod 3$
                we are done,
                and this can always be done.






                share|cite|improve this answer









                $endgroup$





















                  0












                  $begingroup$

                  Suppose $k in mathbb{N} = mathbb{Z}_{>0}$ is given.



                  Set begin{align*}
                  s &= 2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) text{, and} \
                  n &= (-1)^{k+1} + k + 3 text{.}
                  end{align*}



                  Then $s$ and $n$ are positive integers and
                  $$ 9s + 3 + 2^k = 2^n text{.} $$



                  This looks like a job for induction, but we can show it directly.



                  The expression for $n$ is a sum of integers, so $n$ is an integer, and the value of the expression lies in $[k+3-1, k+3+1]$. Since $k > 0$, this entire interval contains only positive numbers, so $n$ is a positive integer.



                  For $s$, note that $(-2)^{k+1} - 1 cong 1^{k+1} - 1 cong 1 - 1 cong 0 pmod{3}$, so the division by $3$ yields an integer. We wish to ensure $s > 0$, so begin{align*}
                  2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) overset{?}{>} 0 \
                  2^k + frac{1}{3} left( (-1)^{k+1}2^{k+1} - 1 right) overset{?}{>} 0 \
                  1 + frac{1}{3} left( (-1)^{k+1}2^{1} - 2^{-k} right) overset{?}{>} 0
                  end{align*}

                  If $k$ is even, begin{align*}
                  1 + frac{1}{3} left( -2 - 2^{-k} right) overset{?}{>} 0 text{,}
                  end{align*}

                  $-2 -2^{-k} in (-3,-2)$, so $1 + frac{1}{3} left( -2 - 2^{-k} right) in (0,1/3)$, all elements of which are positive, so $s$ is positive when $k$ is even. If $k$ is odd, begin{align*}
                  1 + frac{1}{3} left( 2 - 2^{-k} right) overset{?}{>} 0 text{,}
                  end{align*}

                  $2 - 2^{-k} in (1,2)$, so $1 + frac{1}{3} left( 2 - 2^{-k} right) in (4/3, 5/3)$, all elements of which are positive, so $s$ is an integer when $k$ is odd. Therefore, $s$ is positive when $k$ is odd. Therefore, $s$ is always a positive integer.



                  Plugging in the above expressions into the given equation, we have
                  $$ 9 left( 2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) right) + 3 + 2^k = 2^{(-1)^{k+1} + k + 3} text{.} $$
                  After a little manipulation, this is
                  $$ 2^{(-1)^{k+1} + k + 2} = 5 cdot 2^k - 3(-2)^k text{.} tag{1} $$



                  First suppose $k$ is even, so $k = 2m$. Substituting this into (1) and simplifying a little, we have
                  $$ 2^{-1 + 2m + 2} = 2 cdot 2^{2m} text{,} $$
                  a tautology.



                  Then suppose $k$ is odd, so $k = 2m+1$. Sustituting this into (1) and simplifying a little, we have
                  $$ 2^{2m + 4} = 8 cdot 2^{2m+1} text{,} $$
                  a tautology.



                  Therefore, the given $s$ and $n$ are positive integers which satisfy the given equation.



                  Aside: The above choices for $s$ and $n$ do not exhaust the solution set. For instance $(k,s,n) = (2, 131,176,846,746,379,033,713, 70)$ is another solution. (This is implicit in the other answers that use the fact that the powers of $2$ are cyclic modulo $9$.)






                  share|cite|improve this answer









                  $endgroup$














                    Your Answer





                    StackExchange.ifUsing("editor", function () {
                    return StackExchange.using("mathjaxEditing", function () {
                    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
                    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
                    });
                    });
                    }, "mathjax-editing");

                    StackExchange.ready(function() {
                    var channelOptions = {
                    tags: "".split(" "),
                    id: "69"
                    };
                    initTagRenderer("".split(" "), "".split(" "), channelOptions);

                    StackExchange.using("externalEditor", function() {
                    // Have to fire editor after snippets, if snippets enabled
                    if (StackExchange.settings.snippets.snippetsEnabled) {
                    StackExchange.using("snippets", function() {
                    createEditor();
                    });
                    }
                    else {
                    createEditor();
                    }
                    });

                    function createEditor() {
                    StackExchange.prepareEditor({
                    heartbeatType: 'answer',
                    autoActivateHeartbeat: false,
                    convertImagesToLinks: true,
                    noModals: true,
                    showLowRepImageUploadWarning: true,
                    reputationToPostImages: 10,
                    bindNavPrevention: true,
                    postfix: "",
                    imageUploader: {
                    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
                    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
                    allowUrls: true
                    },
                    noCode: true, onDemand: true,
                    discardSelector: ".discard-answer"
                    ,immediatelyShowMarkdownHelp:true
                    });


                    }
                    });














                    draft saved

                    draft discarded


















                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3168962%2fhow-to-prove-a-simple-equation%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown

























                    5 Answers
                    5






                    active

                    oldest

                    votes








                    5 Answers
                    5






                    active

                    oldest

                    votes









                    active

                    oldest

                    votes






                    active

                    oldest

                    votes









                    2












                    $begingroup$

                    The statement that $9s + 3 + 2^k$ is a power of $2$ for some $sinBbb{N}$ is equivalent to saying $2^k + 3 equiv 2^n pmod 9$ for some $ngt k$. Since the values of $2^kbmod 9$ are the periodic sequence $1,2,4,8,7,5,1,2,4,8,7,5,ldots$ consisting of all values which are not multiples of $3$, this is true.



                    For example, take $k = 5$. Then $2^k + 3 = 35 equiv 8 pmod 9$ and the next power of $2$ which is congruent to $8$ is $2^9 = 512$. So in this case $s = (512 - 35)/9 = 53$.






                    share|cite|improve this answer









                    $endgroup$


















                      2












                      $begingroup$

                      The statement that $9s + 3 + 2^k$ is a power of $2$ for some $sinBbb{N}$ is equivalent to saying $2^k + 3 equiv 2^n pmod 9$ for some $ngt k$. Since the values of $2^kbmod 9$ are the periodic sequence $1,2,4,8,7,5,1,2,4,8,7,5,ldots$ consisting of all values which are not multiples of $3$, this is true.



                      For example, take $k = 5$. Then $2^k + 3 = 35 equiv 8 pmod 9$ and the next power of $2$ which is congruent to $8$ is $2^9 = 512$. So in this case $s = (512 - 35)/9 = 53$.






                      share|cite|improve this answer









                      $endgroup$
















                        2












                        2








                        2





                        $begingroup$

                        The statement that $9s + 3 + 2^k$ is a power of $2$ for some $sinBbb{N}$ is equivalent to saying $2^k + 3 equiv 2^n pmod 9$ for some $ngt k$. Since the values of $2^kbmod 9$ are the periodic sequence $1,2,4,8,7,5,1,2,4,8,7,5,ldots$ consisting of all values which are not multiples of $3$, this is true.



                        For example, take $k = 5$. Then $2^k + 3 = 35 equiv 8 pmod 9$ and the next power of $2$ which is congruent to $8$ is $2^9 = 512$. So in this case $s = (512 - 35)/9 = 53$.






                        share|cite|improve this answer









                        $endgroup$



                        The statement that $9s + 3 + 2^k$ is a power of $2$ for some $sinBbb{N}$ is equivalent to saying $2^k + 3 equiv 2^n pmod 9$ for some $ngt k$. Since the values of $2^kbmod 9$ are the periodic sequence $1,2,4,8,7,5,1,2,4,8,7,5,ldots$ consisting of all values which are not multiples of $3$, this is true.



                        For example, take $k = 5$. Then $2^k + 3 = 35 equiv 8 pmod 9$ and the next power of $2$ which is congruent to $8$ is $2^9 = 512$. So in this case $s = (512 - 35)/9 = 53$.







                        share|cite|improve this answer












                        share|cite|improve this answer



                        share|cite|improve this answer










                        answered 1 hour ago









                        FredHFredH

                        3,2951022




                        3,2951022























                            1












                            $begingroup$

                            $9cdot s+3+2^k=2^{j+k} Rightarrow 2^k(2^j-1)-3 equiv 0 mod 9 Rightarrow 2^k(2^j-1) equiv 3 mod 9$



                            $2^k mod 9$ cycles through $2,4,8,7,5,1,$ etc. so $2^j-1 mod 9$ cycles through $1,3,7,6,4,0$ etc.



                            For any residue of $2^k$ it is possible to find a residue of $2^j-1$ such that their product equals $3 mod 9$, viz: $2cdot 6; 4cdot 3; 8cdot 6; 7cdot 3; 5cdot 6; 1cdot 3$



                            So your observation is true.



                            NB As I typed this, I see that Fred H has given a similar answer.






                            share|cite|improve this answer









                            $endgroup$


















                              1












                              $begingroup$

                              $9cdot s+3+2^k=2^{j+k} Rightarrow 2^k(2^j-1)-3 equiv 0 mod 9 Rightarrow 2^k(2^j-1) equiv 3 mod 9$



                              $2^k mod 9$ cycles through $2,4,8,7,5,1,$ etc. so $2^j-1 mod 9$ cycles through $1,3,7,6,4,0$ etc.



                              For any residue of $2^k$ it is possible to find a residue of $2^j-1$ such that their product equals $3 mod 9$, viz: $2cdot 6; 4cdot 3; 8cdot 6; 7cdot 3; 5cdot 6; 1cdot 3$



                              So your observation is true.



                              NB As I typed this, I see that Fred H has given a similar answer.






                              share|cite|improve this answer









                              $endgroup$
















                                1












                                1








                                1





                                $begingroup$

                                $9cdot s+3+2^k=2^{j+k} Rightarrow 2^k(2^j-1)-3 equiv 0 mod 9 Rightarrow 2^k(2^j-1) equiv 3 mod 9$



                                $2^k mod 9$ cycles through $2,4,8,7,5,1,$ etc. so $2^j-1 mod 9$ cycles through $1,3,7,6,4,0$ etc.



                                For any residue of $2^k$ it is possible to find a residue of $2^j-1$ such that their product equals $3 mod 9$, viz: $2cdot 6; 4cdot 3; 8cdot 6; 7cdot 3; 5cdot 6; 1cdot 3$



                                So your observation is true.



                                NB As I typed this, I see that Fred H has given a similar answer.






                                share|cite|improve this answer









                                $endgroup$



                                $9cdot s+3+2^k=2^{j+k} Rightarrow 2^k(2^j-1)-3 equiv 0 mod 9 Rightarrow 2^k(2^j-1) equiv 3 mod 9$



                                $2^k mod 9$ cycles through $2,4,8,7,5,1,$ etc. so $2^j-1 mod 9$ cycles through $1,3,7,6,4,0$ etc.



                                For any residue of $2^k$ it is possible to find a residue of $2^j-1$ such that their product equals $3 mod 9$, viz: $2cdot 6; 4cdot 3; 8cdot 6; 7cdot 3; 5cdot 6; 1cdot 3$



                                So your observation is true.



                                NB As I typed this, I see that Fred H has given a similar answer.







                                share|cite|improve this answer












                                share|cite|improve this answer



                                share|cite|improve this answer










                                answered 51 mins ago









                                Keith BackmanKeith Backman

                                1,5341812




                                1,5341812























                                    1












                                    $begingroup$

                                    Euler's Theorem tells us $2^6 equiv 1 pmod 9$ and direct calculation shows so



                                    $2^{6k + i; i=0...5}equiv 1,2,4,8,7,5 pmod 9$.



                                    So $2^m - 2^k equiv 3 pmod 9$ if



                                    $kequiv 0 pmod 6;2^kequiv 1pmod 9$ and $mequiv 2pmod 6; 2^mequiv 4pmod 9$.



                                    $kequiv 1 pmod 6;2^kequiv 2pmod 9$ and $mequiv 5pmod 6; 2^mequiv 5pmod 9$.



                                    $kequiv 2 pmod 6;2^kequiv 4pmod 9$ and $mequiv 4pmod 6; 2^mequiv 7pmod 9$.



                                    $kequiv 3 pmod 6;2^kequiv 8pmod 9$ and $mequiv 1pmod 6; 2^mequiv 2pmod 9$ (So $2^m - 2^k equiv 2-8equiv -6equiv 3 pmod 9$).



                                    $kequiv 4 pmod 6;2^kequiv 7pmod 9$ and $mequiv 0pmod 6; 2^mequiv 1pmod 9$.



                                    $kequiv 5 pmod 6;2^kequiv 5pmod 9$ and $mequiv 3pmod 6; 2^mequiv 9pmod 9$.



                                    So for any $k$ there will exist infinitely many $m > k$ (Actually we don't need $m > k$ as $s$ may be negative but... nice answers are nicer) so that $2^m - 2^k equiv 3 pmod 9$.



                                    So that means for any $k$ there will exist $s$ and $m$ (actually infinitely many $s$ and $m$) so that



                                    $2^m - 2^k = 9s + 3$ or



                                    $9s+3 + 2^k$ a power of $2$.



                                    (I take a dog for a walk and three people post a similar to identical answer. sigh. Anyway hopefully this answer may (or may not) provide a possible fresh take... There's always more than one way to do or explain things.)






                                    share|cite|improve this answer











                                    $endgroup$


















                                      1












                                      $begingroup$

                                      Euler's Theorem tells us $2^6 equiv 1 pmod 9$ and direct calculation shows so



                                      $2^{6k + i; i=0...5}equiv 1,2,4,8,7,5 pmod 9$.



                                      So $2^m - 2^k equiv 3 pmod 9$ if



                                      $kequiv 0 pmod 6;2^kequiv 1pmod 9$ and $mequiv 2pmod 6; 2^mequiv 4pmod 9$.



                                      $kequiv 1 pmod 6;2^kequiv 2pmod 9$ and $mequiv 5pmod 6; 2^mequiv 5pmod 9$.



                                      $kequiv 2 pmod 6;2^kequiv 4pmod 9$ and $mequiv 4pmod 6; 2^mequiv 7pmod 9$.



                                      $kequiv 3 pmod 6;2^kequiv 8pmod 9$ and $mequiv 1pmod 6; 2^mequiv 2pmod 9$ (So $2^m - 2^k equiv 2-8equiv -6equiv 3 pmod 9$).



                                      $kequiv 4 pmod 6;2^kequiv 7pmod 9$ and $mequiv 0pmod 6; 2^mequiv 1pmod 9$.



                                      $kequiv 5 pmod 6;2^kequiv 5pmod 9$ and $mequiv 3pmod 6; 2^mequiv 9pmod 9$.



                                      So for any $k$ there will exist infinitely many $m > k$ (Actually we don't need $m > k$ as $s$ may be negative but... nice answers are nicer) so that $2^m - 2^k equiv 3 pmod 9$.



                                      So that means for any $k$ there will exist $s$ and $m$ (actually infinitely many $s$ and $m$) so that



                                      $2^m - 2^k = 9s + 3$ or



                                      $9s+3 + 2^k$ a power of $2$.



                                      (I take a dog for a walk and three people post a similar to identical answer. sigh. Anyway hopefully this answer may (or may not) provide a possible fresh take... There's always more than one way to do or explain things.)






                                      share|cite|improve this answer











                                      $endgroup$
















                                        1












                                        1








                                        1





                                        $begingroup$

                                        Euler's Theorem tells us $2^6 equiv 1 pmod 9$ and direct calculation shows so



                                        $2^{6k + i; i=0...5}equiv 1,2,4,8,7,5 pmod 9$.



                                        So $2^m - 2^k equiv 3 pmod 9$ if



                                        $kequiv 0 pmod 6;2^kequiv 1pmod 9$ and $mequiv 2pmod 6; 2^mequiv 4pmod 9$.



                                        $kequiv 1 pmod 6;2^kequiv 2pmod 9$ and $mequiv 5pmod 6; 2^mequiv 5pmod 9$.



                                        $kequiv 2 pmod 6;2^kequiv 4pmod 9$ and $mequiv 4pmod 6; 2^mequiv 7pmod 9$.



                                        $kequiv 3 pmod 6;2^kequiv 8pmod 9$ and $mequiv 1pmod 6; 2^mequiv 2pmod 9$ (So $2^m - 2^k equiv 2-8equiv -6equiv 3 pmod 9$).



                                        $kequiv 4 pmod 6;2^kequiv 7pmod 9$ and $mequiv 0pmod 6; 2^mequiv 1pmod 9$.



                                        $kequiv 5 pmod 6;2^kequiv 5pmod 9$ and $mequiv 3pmod 6; 2^mequiv 9pmod 9$.



                                        So for any $k$ there will exist infinitely many $m > k$ (Actually we don't need $m > k$ as $s$ may be negative but... nice answers are nicer) so that $2^m - 2^k equiv 3 pmod 9$.



                                        So that means for any $k$ there will exist $s$ and $m$ (actually infinitely many $s$ and $m$) so that



                                        $2^m - 2^k = 9s + 3$ or



                                        $9s+3 + 2^k$ a power of $2$.



                                        (I take a dog for a walk and three people post a similar to identical answer. sigh. Anyway hopefully this answer may (or may not) provide a possible fresh take... There's always more than one way to do or explain things.)






                                        share|cite|improve this answer











                                        $endgroup$



                                        Euler's Theorem tells us $2^6 equiv 1 pmod 9$ and direct calculation shows so



                                        $2^{6k + i; i=0...5}equiv 1,2,4,8,7,5 pmod 9$.



                                        So $2^m - 2^k equiv 3 pmod 9$ if



                                        $kequiv 0 pmod 6;2^kequiv 1pmod 9$ and $mequiv 2pmod 6; 2^mequiv 4pmod 9$.



                                        $kequiv 1 pmod 6;2^kequiv 2pmod 9$ and $mequiv 5pmod 6; 2^mequiv 5pmod 9$.



                                        $kequiv 2 pmod 6;2^kequiv 4pmod 9$ and $mequiv 4pmod 6; 2^mequiv 7pmod 9$.



                                        $kequiv 3 pmod 6;2^kequiv 8pmod 9$ and $mequiv 1pmod 6; 2^mequiv 2pmod 9$ (So $2^m - 2^k equiv 2-8equiv -6equiv 3 pmod 9$).



                                        $kequiv 4 pmod 6;2^kequiv 7pmod 9$ and $mequiv 0pmod 6; 2^mequiv 1pmod 9$.



                                        $kequiv 5 pmod 6;2^kequiv 5pmod 9$ and $mequiv 3pmod 6; 2^mequiv 9pmod 9$.



                                        So for any $k$ there will exist infinitely many $m > k$ (Actually we don't need $m > k$ as $s$ may be negative but... nice answers are nicer) so that $2^m - 2^k equiv 3 pmod 9$.



                                        So that means for any $k$ there will exist $s$ and $m$ (actually infinitely many $s$ and $m$) so that



                                        $2^m - 2^k = 9s + 3$ or



                                        $9s+3 + 2^k$ a power of $2$.



                                        (I take a dog for a walk and three people post a similar to identical answer. sigh. Anyway hopefully this answer may (or may not) provide a possible fresh take... There's always more than one way to do or explain things.)







                                        share|cite|improve this answer














                                        share|cite|improve this answer



                                        share|cite|improve this answer








                                        edited 11 mins ago

























                                        answered 18 mins ago









                                        fleabloodfleablood

                                        73.6k22891




                                        73.6k22891























                                            0












                                            $begingroup$

                                            If $9s+3 = 3cdot 2^k$,
                                            this will work.



                                            Then
                                            $3s+1 = 2^k$,
                                            so $3|2^k-1$.



                                            This works for even $k$.



                                            More generally,
                                            it works if
                                            $9s+3 = (2^m-1)2^k$
                                            for some $m$.



                                            To get rid of the 3
                                            requires $m$ even,
                                            so write this as
                                            $9s+3
                                            = (4^m-1)2^k
                                            = 3sum_{j=0}^{m-1}4^j2^k
                                            $

                                            or
                                            $3s+1
                                            = 2^ksum_{j=0}^{m-1}4^j
                                            $
                                            .



                                            Mod 3,
                                            we want
                                            $1
                                            =2^ksum_{j=0}^{m-1}4^j
                                            =2^km
                                            $

                                            so if
                                            $2^km = 1 bmod 3$
                                            we are done,
                                            and this can always be done.






                                            share|cite|improve this answer









                                            $endgroup$


















                                              0












                                              $begingroup$

                                              If $9s+3 = 3cdot 2^k$,
                                              this will work.



                                              Then
                                              $3s+1 = 2^k$,
                                              so $3|2^k-1$.



                                              This works for even $k$.



                                              More generally,
                                              it works if
                                              $9s+3 = (2^m-1)2^k$
                                              for some $m$.



                                              To get rid of the 3
                                              requires $m$ even,
                                              so write this as
                                              $9s+3
                                              = (4^m-1)2^k
                                              = 3sum_{j=0}^{m-1}4^j2^k
                                              $

                                              or
                                              $3s+1
                                              = 2^ksum_{j=0}^{m-1}4^j
                                              $
                                              .



                                              Mod 3,
                                              we want
                                              $1
                                              =2^ksum_{j=0}^{m-1}4^j
                                              =2^km
                                              $

                                              so if
                                              $2^km = 1 bmod 3$
                                              we are done,
                                              and this can always be done.






                                              share|cite|improve this answer









                                              $endgroup$
















                                                0












                                                0








                                                0





                                                $begingroup$

                                                If $9s+3 = 3cdot 2^k$,
                                                this will work.



                                                Then
                                                $3s+1 = 2^k$,
                                                so $3|2^k-1$.



                                                This works for even $k$.



                                                More generally,
                                                it works if
                                                $9s+3 = (2^m-1)2^k$
                                                for some $m$.



                                                To get rid of the 3
                                                requires $m$ even,
                                                so write this as
                                                $9s+3
                                                = (4^m-1)2^k
                                                = 3sum_{j=0}^{m-1}4^j2^k
                                                $

                                                or
                                                $3s+1
                                                = 2^ksum_{j=0}^{m-1}4^j
                                                $
                                                .



                                                Mod 3,
                                                we want
                                                $1
                                                =2^ksum_{j=0}^{m-1}4^j
                                                =2^km
                                                $

                                                so if
                                                $2^km = 1 bmod 3$
                                                we are done,
                                                and this can always be done.






                                                share|cite|improve this answer









                                                $endgroup$



                                                If $9s+3 = 3cdot 2^k$,
                                                this will work.



                                                Then
                                                $3s+1 = 2^k$,
                                                so $3|2^k-1$.



                                                This works for even $k$.



                                                More generally,
                                                it works if
                                                $9s+3 = (2^m-1)2^k$
                                                for some $m$.



                                                To get rid of the 3
                                                requires $m$ even,
                                                so write this as
                                                $9s+3
                                                = (4^m-1)2^k
                                                = 3sum_{j=0}^{m-1}4^j2^k
                                                $

                                                or
                                                $3s+1
                                                = 2^ksum_{j=0}^{m-1}4^j
                                                $
                                                .



                                                Mod 3,
                                                we want
                                                $1
                                                =2^ksum_{j=0}^{m-1}4^j
                                                =2^km
                                                $

                                                so if
                                                $2^km = 1 bmod 3$
                                                we are done,
                                                and this can always be done.







                                                share|cite|improve this answer












                                                share|cite|improve this answer



                                                share|cite|improve this answer










                                                answered 1 hour ago









                                                marty cohenmarty cohen

                                                74.9k549130




                                                74.9k549130























                                                    0












                                                    $begingroup$

                                                    Suppose $k in mathbb{N} = mathbb{Z}_{>0}$ is given.



                                                    Set begin{align*}
                                                    s &= 2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) text{, and} \
                                                    n &= (-1)^{k+1} + k + 3 text{.}
                                                    end{align*}



                                                    Then $s$ and $n$ are positive integers and
                                                    $$ 9s + 3 + 2^k = 2^n text{.} $$



                                                    This looks like a job for induction, but we can show it directly.



                                                    The expression for $n$ is a sum of integers, so $n$ is an integer, and the value of the expression lies in $[k+3-1, k+3+1]$. Since $k > 0$, this entire interval contains only positive numbers, so $n$ is a positive integer.



                                                    For $s$, note that $(-2)^{k+1} - 1 cong 1^{k+1} - 1 cong 1 - 1 cong 0 pmod{3}$, so the division by $3$ yields an integer. We wish to ensure $s > 0$, so begin{align*}
                                                    2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) overset{?}{>} 0 \
                                                    2^k + frac{1}{3} left( (-1)^{k+1}2^{k+1} - 1 right) overset{?}{>} 0 \
                                                    1 + frac{1}{3} left( (-1)^{k+1}2^{1} - 2^{-k} right) overset{?}{>} 0
                                                    end{align*}

                                                    If $k$ is even, begin{align*}
                                                    1 + frac{1}{3} left( -2 - 2^{-k} right) overset{?}{>} 0 text{,}
                                                    end{align*}

                                                    $-2 -2^{-k} in (-3,-2)$, so $1 + frac{1}{3} left( -2 - 2^{-k} right) in (0,1/3)$, all elements of which are positive, so $s$ is positive when $k$ is even. If $k$ is odd, begin{align*}
                                                    1 + frac{1}{3} left( 2 - 2^{-k} right) overset{?}{>} 0 text{,}
                                                    end{align*}

                                                    $2 - 2^{-k} in (1,2)$, so $1 + frac{1}{3} left( 2 - 2^{-k} right) in (4/3, 5/3)$, all elements of which are positive, so $s$ is an integer when $k$ is odd. Therefore, $s$ is positive when $k$ is odd. Therefore, $s$ is always a positive integer.



                                                    Plugging in the above expressions into the given equation, we have
                                                    $$ 9 left( 2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) right) + 3 + 2^k = 2^{(-1)^{k+1} + k + 3} text{.} $$
                                                    After a little manipulation, this is
                                                    $$ 2^{(-1)^{k+1} + k + 2} = 5 cdot 2^k - 3(-2)^k text{.} tag{1} $$



                                                    First suppose $k$ is even, so $k = 2m$. Substituting this into (1) and simplifying a little, we have
                                                    $$ 2^{-1 + 2m + 2} = 2 cdot 2^{2m} text{,} $$
                                                    a tautology.



                                                    Then suppose $k$ is odd, so $k = 2m+1$. Sustituting this into (1) and simplifying a little, we have
                                                    $$ 2^{2m + 4} = 8 cdot 2^{2m+1} text{,} $$
                                                    a tautology.



                                                    Therefore, the given $s$ and $n$ are positive integers which satisfy the given equation.



                                                    Aside: The above choices for $s$ and $n$ do not exhaust the solution set. For instance $(k,s,n) = (2, 131,176,846,746,379,033,713, 70)$ is another solution. (This is implicit in the other answers that use the fact that the powers of $2$ are cyclic modulo $9$.)






                                                    share|cite|improve this answer









                                                    $endgroup$


















                                                      0












                                                      $begingroup$

                                                      Suppose $k in mathbb{N} = mathbb{Z}_{>0}$ is given.



                                                      Set begin{align*}
                                                      s &= 2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) text{, and} \
                                                      n &= (-1)^{k+1} + k + 3 text{.}
                                                      end{align*}



                                                      Then $s$ and $n$ are positive integers and
                                                      $$ 9s + 3 + 2^k = 2^n text{.} $$



                                                      This looks like a job for induction, but we can show it directly.



                                                      The expression for $n$ is a sum of integers, so $n$ is an integer, and the value of the expression lies in $[k+3-1, k+3+1]$. Since $k > 0$, this entire interval contains only positive numbers, so $n$ is a positive integer.



                                                      For $s$, note that $(-2)^{k+1} - 1 cong 1^{k+1} - 1 cong 1 - 1 cong 0 pmod{3}$, so the division by $3$ yields an integer. We wish to ensure $s > 0$, so begin{align*}
                                                      2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) overset{?}{>} 0 \
                                                      2^k + frac{1}{3} left( (-1)^{k+1}2^{k+1} - 1 right) overset{?}{>} 0 \
                                                      1 + frac{1}{3} left( (-1)^{k+1}2^{1} - 2^{-k} right) overset{?}{>} 0
                                                      end{align*}

                                                      If $k$ is even, begin{align*}
                                                      1 + frac{1}{3} left( -2 - 2^{-k} right) overset{?}{>} 0 text{,}
                                                      end{align*}

                                                      $-2 -2^{-k} in (-3,-2)$, so $1 + frac{1}{3} left( -2 - 2^{-k} right) in (0,1/3)$, all elements of which are positive, so $s$ is positive when $k$ is even. If $k$ is odd, begin{align*}
                                                      1 + frac{1}{3} left( 2 - 2^{-k} right) overset{?}{>} 0 text{,}
                                                      end{align*}

                                                      $2 - 2^{-k} in (1,2)$, so $1 + frac{1}{3} left( 2 - 2^{-k} right) in (4/3, 5/3)$, all elements of which are positive, so $s$ is an integer when $k$ is odd. Therefore, $s$ is positive when $k$ is odd. Therefore, $s$ is always a positive integer.



                                                      Plugging in the above expressions into the given equation, we have
                                                      $$ 9 left( 2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) right) + 3 + 2^k = 2^{(-1)^{k+1} + k + 3} text{.} $$
                                                      After a little manipulation, this is
                                                      $$ 2^{(-1)^{k+1} + k + 2} = 5 cdot 2^k - 3(-2)^k text{.} tag{1} $$



                                                      First suppose $k$ is even, so $k = 2m$. Substituting this into (1) and simplifying a little, we have
                                                      $$ 2^{-1 + 2m + 2} = 2 cdot 2^{2m} text{,} $$
                                                      a tautology.



                                                      Then suppose $k$ is odd, so $k = 2m+1$. Sustituting this into (1) and simplifying a little, we have
                                                      $$ 2^{2m + 4} = 8 cdot 2^{2m+1} text{,} $$
                                                      a tautology.



                                                      Therefore, the given $s$ and $n$ are positive integers which satisfy the given equation.



                                                      Aside: The above choices for $s$ and $n$ do not exhaust the solution set. For instance $(k,s,n) = (2, 131,176,846,746,379,033,713, 70)$ is another solution. (This is implicit in the other answers that use the fact that the powers of $2$ are cyclic modulo $9$.)






                                                      share|cite|improve this answer









                                                      $endgroup$
















                                                        0












                                                        0








                                                        0





                                                        $begingroup$

                                                        Suppose $k in mathbb{N} = mathbb{Z}_{>0}$ is given.



                                                        Set begin{align*}
                                                        s &= 2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) text{, and} \
                                                        n &= (-1)^{k+1} + k + 3 text{.}
                                                        end{align*}



                                                        Then $s$ and $n$ are positive integers and
                                                        $$ 9s + 3 + 2^k = 2^n text{.} $$



                                                        This looks like a job for induction, but we can show it directly.



                                                        The expression for $n$ is a sum of integers, so $n$ is an integer, and the value of the expression lies in $[k+3-1, k+3+1]$. Since $k > 0$, this entire interval contains only positive numbers, so $n$ is a positive integer.



                                                        For $s$, note that $(-2)^{k+1} - 1 cong 1^{k+1} - 1 cong 1 - 1 cong 0 pmod{3}$, so the division by $3$ yields an integer. We wish to ensure $s > 0$, so begin{align*}
                                                        2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) overset{?}{>} 0 \
                                                        2^k + frac{1}{3} left( (-1)^{k+1}2^{k+1} - 1 right) overset{?}{>} 0 \
                                                        1 + frac{1}{3} left( (-1)^{k+1}2^{1} - 2^{-k} right) overset{?}{>} 0
                                                        end{align*}

                                                        If $k$ is even, begin{align*}
                                                        1 + frac{1}{3} left( -2 - 2^{-k} right) overset{?}{>} 0 text{,}
                                                        end{align*}

                                                        $-2 -2^{-k} in (-3,-2)$, so $1 + frac{1}{3} left( -2 - 2^{-k} right) in (0,1/3)$, all elements of which are positive, so $s$ is positive when $k$ is even. If $k$ is odd, begin{align*}
                                                        1 + frac{1}{3} left( 2 - 2^{-k} right) overset{?}{>} 0 text{,}
                                                        end{align*}

                                                        $2 - 2^{-k} in (1,2)$, so $1 + frac{1}{3} left( 2 - 2^{-k} right) in (4/3, 5/3)$, all elements of which are positive, so $s$ is an integer when $k$ is odd. Therefore, $s$ is positive when $k$ is odd. Therefore, $s$ is always a positive integer.



                                                        Plugging in the above expressions into the given equation, we have
                                                        $$ 9 left( 2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) right) + 3 + 2^k = 2^{(-1)^{k+1} + k + 3} text{.} $$
                                                        After a little manipulation, this is
                                                        $$ 2^{(-1)^{k+1} + k + 2} = 5 cdot 2^k - 3(-2)^k text{.} tag{1} $$



                                                        First suppose $k$ is even, so $k = 2m$. Substituting this into (1) and simplifying a little, we have
                                                        $$ 2^{-1 + 2m + 2} = 2 cdot 2^{2m} text{,} $$
                                                        a tautology.



                                                        Then suppose $k$ is odd, so $k = 2m+1$. Sustituting this into (1) and simplifying a little, we have
                                                        $$ 2^{2m + 4} = 8 cdot 2^{2m+1} text{,} $$
                                                        a tautology.



                                                        Therefore, the given $s$ and $n$ are positive integers which satisfy the given equation.



                                                        Aside: The above choices for $s$ and $n$ do not exhaust the solution set. For instance $(k,s,n) = (2, 131,176,846,746,379,033,713, 70)$ is another solution. (This is implicit in the other answers that use the fact that the powers of $2$ are cyclic modulo $9$.)






                                                        share|cite|improve this answer









                                                        $endgroup$



                                                        Suppose $k in mathbb{N} = mathbb{Z}_{>0}$ is given.



                                                        Set begin{align*}
                                                        s &= 2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) text{, and} \
                                                        n &= (-1)^{k+1} + k + 3 text{.}
                                                        end{align*}



                                                        Then $s$ and $n$ are positive integers and
                                                        $$ 9s + 3 + 2^k = 2^n text{.} $$



                                                        This looks like a job for induction, but we can show it directly.



                                                        The expression for $n$ is a sum of integers, so $n$ is an integer, and the value of the expression lies in $[k+3-1, k+3+1]$. Since $k > 0$, this entire interval contains only positive numbers, so $n$ is a positive integer.



                                                        For $s$, note that $(-2)^{k+1} - 1 cong 1^{k+1} - 1 cong 1 - 1 cong 0 pmod{3}$, so the division by $3$ yields an integer. We wish to ensure $s > 0$, so begin{align*}
                                                        2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) overset{?}{>} 0 \
                                                        2^k + frac{1}{3} left( (-1)^{k+1}2^{k+1} - 1 right) overset{?}{>} 0 \
                                                        1 + frac{1}{3} left( (-1)^{k+1}2^{1} - 2^{-k} right) overset{?}{>} 0
                                                        end{align*}

                                                        If $k$ is even, begin{align*}
                                                        1 + frac{1}{3} left( -2 - 2^{-k} right) overset{?}{>} 0 text{,}
                                                        end{align*}

                                                        $-2 -2^{-k} in (-3,-2)$, so $1 + frac{1}{3} left( -2 - 2^{-k} right) in (0,1/3)$, all elements of which are positive, so $s$ is positive when $k$ is even. If $k$ is odd, begin{align*}
                                                        1 + frac{1}{3} left( 2 - 2^{-k} right) overset{?}{>} 0 text{,}
                                                        end{align*}

                                                        $2 - 2^{-k} in (1,2)$, so $1 + frac{1}{3} left( 2 - 2^{-k} right) in (4/3, 5/3)$, all elements of which are positive, so $s$ is an integer when $k$ is odd. Therefore, $s$ is positive when $k$ is odd. Therefore, $s$ is always a positive integer.



                                                        Plugging in the above expressions into the given equation, we have
                                                        $$ 9 left( 2^k + frac{1}{3} left( (-2)^{k+1} - 1 right) right) + 3 + 2^k = 2^{(-1)^{k+1} + k + 3} text{.} $$
                                                        After a little manipulation, this is
                                                        $$ 2^{(-1)^{k+1} + k + 2} = 5 cdot 2^k - 3(-2)^k text{.} tag{1} $$



                                                        First suppose $k$ is even, so $k = 2m$. Substituting this into (1) and simplifying a little, we have
                                                        $$ 2^{-1 + 2m + 2} = 2 cdot 2^{2m} text{,} $$
                                                        a tautology.



                                                        Then suppose $k$ is odd, so $k = 2m+1$. Sustituting this into (1) and simplifying a little, we have
                                                        $$ 2^{2m + 4} = 8 cdot 2^{2m+1} text{,} $$
                                                        a tautology.



                                                        Therefore, the given $s$ and $n$ are positive integers which satisfy the given equation.



                                                        Aside: The above choices for $s$ and $n$ do not exhaust the solution set. For instance $(k,s,n) = (2, 131,176,846,746,379,033,713, 70)$ is another solution. (This is implicit in the other answers that use the fact that the powers of $2$ are cyclic modulo $9$.)







                                                        share|cite|improve this answer












                                                        share|cite|improve this answer



                                                        share|cite|improve this answer










                                                        answered 11 mins ago









                                                        Eric TowersEric Towers

                                                        33.3k22370




                                                        33.3k22370






























                                                            draft saved

                                                            draft discarded




















































                                                            Thanks for contributing an answer to Mathematics Stack Exchange!


                                                            • Please be sure to answer the question. Provide details and share your research!

                                                            But avoid



                                                            • Asking for help, clarification, or responding to other answers.

                                                            • Making statements based on opinion; back them up with references or personal experience.


                                                            Use MathJax to format equations. MathJax reference.


                                                            To learn more, see our tips on writing great answers.




                                                            draft saved


                                                            draft discarded














                                                            StackExchange.ready(
                                                            function () {
                                                            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3168962%2fhow-to-prove-a-simple-equation%23new-answer', 'question_page');
                                                            }
                                                            );

                                                            Post as a guest















                                                            Required, but never shown





















































                                                            Required, but never shown














                                                            Required, but never shown












                                                            Required, but never shown







                                                            Required, but never shown

































                                                            Required, but never shown














                                                            Required, but never shown












                                                            Required, but never shown







                                                            Required, but never shown







                                                            Popular posts from this blog

                                                            Knooppunt Holsloot

                                                            Altaar (religie)

                                                            Gregoriusmis