How to prove a simple equation? The Next CEO of Stack OverflowProof: For all integers $x$ and $y$, if $x^3+x = y^3+y$ then $x = y$Simple question about proof by contrapositivity.Does there exist a $(m,n)inmathbb N$ such that $m^3-2^n=3$?Proof: For all integers $x$ and $y$, if $x^2+ y^2= 0$ then $x =0$ and $y =0$disprove : $forall n in mathbbN exists m in mathbbN$ such that $n<m<n^2$Proof writing involving propositional logic: (x ∨ y) ≡ ( x ∧ y ) → x ≡ yIs the following statement about rationals true or false?How many massively palindromic primes exist?The Number Theoretic Statement is …Show that $n^2-1+nsqrtd$ is the fundamental unit in $mathbbZ[sqrtd]$ for all $ngeq 3$

0 rank tensor vs 1D vector

Is it possible to replace duplicates of a character with one character using tr

What was the first Unix version to run on a microcomputer?

Why do remote US companies require working in the US?

"misplaced omit" error when >centering columns

Why do airplanes bank sharply to the right after air-to-air refueling?

Legal workarounds for testamentary trust perceived as unfair

Some questions about different axiomatic systems for neighbourhoods

Flying from Cape Town to England and return to another province

Domestic-to-international connection at Orlando (MCO)

WOW air has ceased operation, can I get my tickets refunded?

Solving system of ODEs with extra parameter

The exact meaning of 'Mom made me a sandwich'

Does increasing your ability score affect your main stat?

How to get from Geneva Airport to Metabief, Doubs, France by public transport?

Is there always a complete, orthogonal set of unitary matrices?

Won the lottery - how do I keep the money?

Is French Guiana a (hard) EU border?

Why does standard notation not preserve intervals (visually)

How to invert MapIndexed on a ragged structure? How to construct a tree from rules?

Why didn't Khan get resurrected in the Genesis Explosion?

Is it my responsibility to learn a new technology in my own time my employer wants to implement?

If Nick Fury and Coulson already knew about aliens (Kree and Skrull) why did they wait until Thor's appearance to start making weapons?

Is there a way to save my career from absolute disaster?



How to prove a simple equation?



The Next CEO of Stack OverflowProof: For all integers $x$ and $y$, if $x^3+x = y^3+y$ then $x = y$Simple question about proof by contrapositivity.Does there exist a $(m,n)inmathbb N$ such that $m^3-2^n=3$?Proof: For all integers $x$ and $y$, if $x^2+ y^2= 0$ then $x =0$ and $y =0$disprove : $forall n in mathbbN exists m in mathbbN$ such that $n<m<n^2$Proof writing involving propositional logic: (x ∨ y) ≡ ( x ∧ y ) → x ≡ yIs the following statement about rationals true or false?How many massively palindromic primes exist?The Number Theoretic Statement is …Show that $n^2-1+nsqrtd$ is the fundamental unit in $mathbbZ[sqrtd]$ for all $ngeq 3$










1












$begingroup$


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



For any $k in mathbbN$, there exist $s in mathbbN$ 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 mathbbN$, there exist $s in mathbbN$ 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 mathbbN$, there exist $s in mathbbN$ 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 mathbbN$, there exist $s in mathbbN$ 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 $sinBbbN$ 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...5equiv 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-14^j2^k
                $

                or
                $3s+1
                = 2^ksum_j=0^m-14^j
                $
                .



                Mod 3,
                we want
                $1
                =2^ksum_j=0^m-14^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 mathbbN = mathbbZ_>0$ is given.



                  Set beginalign*
                  s &= 2^k + frac13 left( (-2)^k+1 - 1 right) text, and \
                  n &= (-1)^k+1 + k + 3 text.
                  endalign*



                  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 pmod3$, so the division by $3$ yields an integer. We wish to ensure $s > 0$, so beginalign*
                  2^k + frac13 left( (-2)^k+1 - 1 right) overset?> 0 \
                  2^k + frac13 left( (-1)^k+12^k+1 - 1 right) overset?> 0 \
                  1 + frac13 left( (-1)^k+12^1 - 2^-k right) overset?> 0
                  endalign*

                  If $k$ is even, beginalign*
                  1 + frac13 left( -2 - 2^-k right) overset?> 0 text,
                  endalign*

                  $-2 -2^-k in (-3,-2)$, so $1 + frac13 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, beginalign*
                  1 + frac13 left( 2 - 2^-k right) overset?> 0 text,
                  endalign*

                  $2 - 2^-k in (1,2)$, so $1 + frac13 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 + frac13 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. tag1 $$



                  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 $sinBbbN$ 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 $sinBbbN$ 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 $sinBbbN$ 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 $sinBbbN$ 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...5equiv 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...5equiv 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...5equiv 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...5equiv 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-14^j2^k
                                            $

                                            or
                                            $3s+1
                                            = 2^ksum_j=0^m-14^j
                                            $
                                            .



                                            Mod 3,
                                            we want
                                            $1
                                            =2^ksum_j=0^m-14^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-14^j2^k
                                              $

                                              or
                                              $3s+1
                                              = 2^ksum_j=0^m-14^j
                                              $
                                              .



                                              Mod 3,
                                              we want
                                              $1
                                              =2^ksum_j=0^m-14^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-14^j2^k
                                                $

                                                or
                                                $3s+1
                                                = 2^ksum_j=0^m-14^j
                                                $
                                                .



                                                Mod 3,
                                                we want
                                                $1
                                                =2^ksum_j=0^m-14^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-14^j2^k
                                                $

                                                or
                                                $3s+1
                                                = 2^ksum_j=0^m-14^j
                                                $
                                                .



                                                Mod 3,
                                                we want
                                                $1
                                                =2^ksum_j=0^m-14^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 mathbbN = mathbbZ_>0$ is given.



                                                    Set beginalign*
                                                    s &= 2^k + frac13 left( (-2)^k+1 - 1 right) text, and \
                                                    n &= (-1)^k+1 + k + 3 text.
                                                    endalign*



                                                    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 pmod3$, so the division by $3$ yields an integer. We wish to ensure $s > 0$, so beginalign*
                                                    2^k + frac13 left( (-2)^k+1 - 1 right) overset?> 0 \
                                                    2^k + frac13 left( (-1)^k+12^k+1 - 1 right) overset?> 0 \
                                                    1 + frac13 left( (-1)^k+12^1 - 2^-k right) overset?> 0
                                                    endalign*

                                                    If $k$ is even, beginalign*
                                                    1 + frac13 left( -2 - 2^-k right) overset?> 0 text,
                                                    endalign*

                                                    $-2 -2^-k in (-3,-2)$, so $1 + frac13 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, beginalign*
                                                    1 + frac13 left( 2 - 2^-k right) overset?> 0 text,
                                                    endalign*

                                                    $2 - 2^-k in (1,2)$, so $1 + frac13 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 + frac13 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. tag1 $$



                                                    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 mathbbN = mathbbZ_>0$ is given.



                                                      Set beginalign*
                                                      s &= 2^k + frac13 left( (-2)^k+1 - 1 right) text, and \
                                                      n &= (-1)^k+1 + k + 3 text.
                                                      endalign*



                                                      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 pmod3$, so the division by $3$ yields an integer. We wish to ensure $s > 0$, so beginalign*
                                                      2^k + frac13 left( (-2)^k+1 - 1 right) overset?> 0 \
                                                      2^k + frac13 left( (-1)^k+12^k+1 - 1 right) overset?> 0 \
                                                      1 + frac13 left( (-1)^k+12^1 - 2^-k right) overset?> 0
                                                      endalign*

                                                      If $k$ is even, beginalign*
                                                      1 + frac13 left( -2 - 2^-k right) overset?> 0 text,
                                                      endalign*

                                                      $-2 -2^-k in (-3,-2)$, so $1 + frac13 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, beginalign*
                                                      1 + frac13 left( 2 - 2^-k right) overset?> 0 text,
                                                      endalign*

                                                      $2 - 2^-k in (1,2)$, so $1 + frac13 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 + frac13 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. tag1 $$



                                                      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 mathbbN = mathbbZ_>0$ is given.



                                                        Set beginalign*
                                                        s &= 2^k + frac13 left( (-2)^k+1 - 1 right) text, and \
                                                        n &= (-1)^k+1 + k + 3 text.
                                                        endalign*



                                                        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 pmod3$, so the division by $3$ yields an integer. We wish to ensure $s > 0$, so beginalign*
                                                        2^k + frac13 left( (-2)^k+1 - 1 right) overset?> 0 \
                                                        2^k + frac13 left( (-1)^k+12^k+1 - 1 right) overset?> 0 \
                                                        1 + frac13 left( (-1)^k+12^1 - 2^-k right) overset?> 0
                                                        endalign*

                                                        If $k$ is even, beginalign*
                                                        1 + frac13 left( -2 - 2^-k right) overset?> 0 text,
                                                        endalign*

                                                        $-2 -2^-k in (-3,-2)$, so $1 + frac13 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, beginalign*
                                                        1 + frac13 left( 2 - 2^-k right) overset?> 0 text,
                                                        endalign*

                                                        $2 - 2^-k in (1,2)$, so $1 + frac13 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 + frac13 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. tag1 $$



                                                        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 mathbbN = mathbbZ_>0$ is given.



                                                        Set beginalign*
                                                        s &= 2^k + frac13 left( (-2)^k+1 - 1 right) text, and \
                                                        n &= (-1)^k+1 + k + 3 text.
                                                        endalign*



                                                        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 pmod3$, so the division by $3$ yields an integer. We wish to ensure $s > 0$, so beginalign*
                                                        2^k + frac13 left( (-2)^k+1 - 1 right) overset?> 0 \
                                                        2^k + frac13 left( (-1)^k+12^k+1 - 1 right) overset?> 0 \
                                                        1 + frac13 left( (-1)^k+12^1 - 2^-k right) overset?> 0
                                                        endalign*

                                                        If $k$ is even, beginalign*
                                                        1 + frac13 left( -2 - 2^-k right) overset?> 0 text,
                                                        endalign*

                                                        $-2 -2^-k in (-3,-2)$, so $1 + frac13 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, beginalign*
                                                        1 + frac13 left( 2 - 2^-k right) overset?> 0 text,
                                                        endalign*

                                                        $2 - 2^-k in (1,2)$, so $1 + frac13 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 + frac13 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. tag1 $$



                                                        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

                                                            Oświęcim Innehåll Historia | Källor | Externa länkar | Navigeringsmeny50°2′18″N 19°13′17″Ö / 50.03833°N 19.22139°Ö / 50.03833; 19.2213950°2′18″N 19°13′17″Ö / 50.03833°N 19.22139°Ö / 50.03833; 19.221393089658Nordisk familjebok, AuschwitzInsidan tro och existensJewish Community i OświęcimAuschwitz Jewish Center: MuseumAuschwitz Jewish Center

                                                            Valle di Casies Indice Geografia fisica | Origini del nome | Storia | Società | Amministrazione | Sport | Note | Bibliografia | Voci correlate | Altri progetti | Collegamenti esterni | Menu di navigazione46°46′N 12°11′E / 46.766667°N 12.183333°E46.766667; 12.183333 (Valle di Casies)46°46′N 12°11′E / 46.766667°N 12.183333°E46.766667; 12.183333 (Valle di Casies)Sito istituzionaleAstat Censimento della popolazione 2011 - Determinazione della consistenza dei tre gruppi linguistici della Provincia Autonoma di Bolzano-Alto Adige - giugno 2012Numeri e fattiValle di CasiesDato IstatTabella dei gradi/giorno dei Comuni italiani raggruppati per Regione e Provincia26 agosto 1993, n. 412Heraldry of the World: GsiesStatistiche I.StatValCasies.comWikimedia CommonsWikimedia CommonsValle di CasiesSito ufficialeValle di CasiesMM14870458910042978-6

                                                            Typsetting diagram chases (with TikZ?) Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)How to define the default vertical distance between nodes?Draw edge on arcNumerical conditional within tikz keys?TikZ: Drawing an arc from an intersection to an intersectionDrawing rectilinear curves in Tikz, aka an Etch-a-Sketch drawingLine up nested tikz enviroments or how to get rid of themHow to place nodes in an absolute coordinate system in tikzCommutative diagram with curve connecting between nodesTikz with standalone: pinning tikz coordinates to page cmDrawing a Decision Diagram with Tikz and layout manager