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$
Easy to read palindrome checker
Bartok - Syncopation (1): Meaning of notes in between Grand Staff
Why the difference in type-inference over the as-pattern in two similar function definitions?
Can we say or write : "No, it'sn't"?
Make solar eclipses exceedingly rare, but still have new moons
Why did CATV standarize in 75 ohms and everyone else in 50?
Running a General Election and the European Elections together
What does "Its cash flow is deeply negative" mean?
Is the D&D universe the same as the Forgotten Realms universe?
Writing differences on a blackboard
Prepend last line of stdin to entire stdin
Is it professional to write unrelated content in an almost-empty email?
Would a grinding machine be a simple and workable propulsion system for an interplanetary spacecraft?
Is it okay to majorly distort historical facts while writing a fiction story?
How to count occurrences of text in a file?
How did people program for Consoles with multiple CPUs?
Is there a difference between "Fahrstuhl" and "Aufzug"
0 rank tensor vs 1D vector
Why do airplanes bank sharply to the right after air-to-air refueling?
A small doubt about the dominated convergence theorem
Won the lottery - how do I keep the money?
Are police here, aren't itthey?
Unclear about dynamic binding
Do I need to write [sic] when a number is less than 10 but isn't written out?
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$
$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.
number-theory discrete-mathematics recreational-mathematics
$endgroup$
add a comment |
$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.
number-theory discrete-mathematics recreational-mathematics
$endgroup$
add a comment |
$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.
number-theory discrete-mathematics recreational-mathematics
$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
number-theory discrete-mathematics recreational-mathematics
asked 1 hour ago
ReverseFlowReverseFlow
604513
604513
add a comment |
add a comment |
5 Answers
5
active
oldest
votes
$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$.
$endgroup$
add a comment |
$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.
$endgroup$
add a comment |
$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.)
$endgroup$
add a comment |
$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.
$endgroup$
add a comment |
$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$.)
$endgroup$
add a comment |
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
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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$.
$endgroup$
add a comment |
$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$.
$endgroup$
add a comment |
$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$.
$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$.
answered 1 hour ago
FredHFredH
3,2951022
3,2951022
add a comment |
add a comment |
$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.
$endgroup$
add a comment |
$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.
$endgroup$
add a comment |
$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.
$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.
answered 1 hour ago
Keith BackmanKeith Backman
1,5341812
1,5341812
add a comment |
add a comment |
$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.)
$endgroup$
add a comment |
$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.)
$endgroup$
add a comment |
$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.)
$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.)
edited 38 mins ago
answered 46 mins ago
fleabloodfleablood
73.6k22891
73.6k22891
add a comment |
add a comment |
$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.
$endgroup$
add a comment |
$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.
$endgroup$
add a comment |
$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.
$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.
answered 1 hour ago
marty cohenmarty cohen
74.9k549130
74.9k549130
add a comment |
add a comment |
$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$.)
$endgroup$
add a comment |
$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$.)
$endgroup$
add a comment |
$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$.)
$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$.)
answered 39 mins ago
Eric TowersEric Towers
33.3k22370
33.3k22370
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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