Prove that $4^n-1$ is divided by $3^k$ if and only if $n=3^k-1t$How many powers of 2 are easy to double?Counting an orbit length in $mathbbZ/q^alphamathbbZ$Simple prime no. quesitonSum of all possible remainders when $2^n$, where n is a nonnegative integer, is divided by 1000Assume that 495 divides the integer $overline273x49y5$ where $x,y in 0,1,2…9$. Find $x$ and $y$.Generalization of the fact that $sum_i=1^nfrac 1 i$ is not an integer for all $n>1$.Prove that gcd between two consecutive terms in a sequence is constant (and find it)Equivalence between a limit and Pillai's ConjectureExpression for the highest power of 2 dividing $3^aleft(2b-1right)-1$Using least common multiple to prove there exists a prime between $2x$ and $3x$
How can saying a song's name be a copyright violation?
If human space travel is limited by the G force vulnerability, is there a way to counter G forces?
Doing something right before you need it - expression for this?
Would Slavery Reparations be considered Bills of Attainder and hence Illegal?
Where does SFDX store details about scratch orgs?
How much of data wrangling is a data scientist's job?
Can I ask the recruiters in my resume to put the reason why I am rejected?
What mechanic is there to disable a threat instead of killing it?
Brothers & sisters
Etiquette around loan refinance - decision is going to cost first broker a lot of money
What's the difference between 'rename' and 'mv'?
Stopping power of mountain vs road bike
1960's book about a plague that kills all white people
How to model explosives?
In Romance of the Three Kingdoms why do people still use bamboo sticks when papers are already invented?
How can I prevent hyper evolved versions of regular creatures from wiping out their cousins?
How can I make my BBEG immortal short of making them a Lich or Vampire?
Arrow those variables!
Why "Having chlorophyll without photosynthesis is actually very dangerous" and "like living with a bomb"?
Python: return float 1.0 as int 1 but float 1.5 as float 1.5
Did Shadowfax go to Valinor?
In a Spin are Both Wings Stalled?
SSH "lag" in LAN on some machines, mixed distros
How to say in German "enjoying home comforts"
Prove that $4^n-1$ is divided by $3^k$ if and only if $n=3^k-1t$
How many powers of 2 are easy to double?Counting an orbit length in $mathbbZ/q^alphamathbbZ$Simple prime no. quesitonSum of all possible remainders when $2^n$, where n is a nonnegative integer, is divided by 1000Assume that 495 divides the integer $overline273x49y5$ where $x,y in 0,1,2…9$. Find $x$ and $y$.Generalization of the fact that $sum_i=1^nfrac 1 i$ is not an integer for all $n>1$.Prove that gcd between two consecutive terms in a sequence is constant (and find it)Equivalence between a limit and Pillai's ConjectureExpression for the highest power of 2 dividing $3^aleft(2b-1right)-1$Using least common multiple to prove there exists a prime between $2x$ and $3x$
$begingroup$
I am aware that $3$ always divides $2^2n-1$, which is easy to prove. To deal with some automorphism groups, I am trying to generalise this to find the highest power of $3$ that can divide $2^n -1$.
A reasonable conjecture is that $2^2n-1$ is divided by $3^k$ if and only if $n=3^k-1m$. An example would be that $4^3n+t = 1 mod 9$ if and only if $t=0$ (where, of course, $0 leq t leq 5$). This is easily proved by showing $2^6n+t neq 1 mod 9$ when $t neq 0$.
I can't, however, find an easy argument to show this for $4^n - 1$, since checking every value of $t$ separately is not a viable strategy.
number-theory elementary-number-theory
asked Mar 21 at 13:21
AnalysisStudent0414AnalysisStudent0414
4,408928
$endgroup$
add a comment |
$begingroup$
I am aware that $3$ always divides $2^2n-1$, which is easy to prove. To deal with some automorphism groups, I am trying to generalise this to find the highest power of $3$ that can divide $2^n -1$.
A reasonable conjecture is that $2^2n-1$ is divided by $3^k$ if and only if $n=3^k-1m$. An example would be that $4^3n+t = 1 mod 9$ if and only if $t=0$ (where, of course, $0 leq t leq 5$). This is easily proved by showing $2^6n+t neq 1 mod 9$ when $t neq 0$.
I can't, however, find an easy argument to show this for $4^n - 1$, since checking every value of $t$ separately is not a viable strategy.
number-theory elementary-number-theory
asked Mar 21 at 13:21
AnalysisStudent0414AnalysisStudent0414
4,408928
$endgroup$
add a comment |
$begingroup$
I am aware that $3$ always divides $2^2n-1$, which is easy to prove. To deal with some automorphism groups, I am trying to generalise this to find the highest power of $3$ that can divide $2^n -1$.
A reasonable conjecture is that $2^2n-1$ is divided by $3^k$ if and only if $n=3^k-1m$. An example would be that $4^3n+t = 1 mod 9$ if and only if $t=0$ (where, of course, $0 leq t leq 5$). This is easily proved by showing $2^6n+t neq 1 mod 9$ when $t neq 0$.
I can't, however, find an easy argument to show this for $4^n - 1$, since checking every value of $t$ separately is not a viable strategy.
number-theory elementary-number-theory
asked Mar 21 at 13:21
AnalysisStudent0414AnalysisStudent0414
4,408928
$endgroup$
I am aware that $3$ always divides $2^2n-1$, which is easy to prove. To deal with some automorphism groups, I am trying to generalise this to find the highest power of $3$ that can divide $2^n -1$.
A reasonable conjecture is that $2^2n-1$ is divided by $3^k$ if and only if $n=3^k-1m$. An example would be that $4^3n+t = 1 mod 9$ if and only if $t=0$ (where, of course, $0 leq t leq 5$). This is easily proved by showing $2^6n+t neq 1 mod 9$ when $t neq 0$.
I can't, however, find an easy argument to show this for $4^n - 1$, since checking every value of $t$ separately is not a viable strategy.
number-theory elementary-number-theory
number-theory elementary-number-theory
asked Mar 21 at 13:21
AnalysisStudent0414AnalysisStudent0414
4,408928
asked Mar 21 at 13:21
AnalysisStudent0414AnalysisStudent0414
4,408928
asked Mar 21 at 13:21
AnalysisStudent0414AnalysisStudent0414
4,408928
asked Mar 21 at 13:21
AnalysisStudent0414AnalysisStudent0414
4,408928
asked Mar 21 at 13:21
AnalysisStudent0414AnalysisStudent0414
4,408928
4,408928
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
In general if the multiplicative order of $a$ mod $p^k$ is $r$ (where $p$ is prime and $a > 1$ is not divisible by $p$), then the order of $a$ mod $p^k+1$ divides $r p$. However, in some cases it is just $r$. I want to prove that doesn't happen in the case $p=3$, $a=2$.
Let $nu_p(x)$ denote the highest exponent $k$ such that $p^k | x$.
Note that $a^3r - 1 = (a^r-1)(a^2r + a^r + 1)$, so $nu_3(a^3r-1) = nu_3(a^r-1) + nu_3(a^2r + a^r + 1)$. If $a^r equiv 1 mod 3$, $a^2r + a^r + 1 equiv 0 mod 3$. However, since $x^2 + x + 1 equiv 0 bmod 9$ has no solutions, it is not $0 bmod 9$. Thus $nu_3(a^2r+a^r+1) = 1$, and $nu_3(a^3r-1) = nu_3(a^r-1) + 1$. By induction, $nu_3(a^3^k r-1) = nu_3(a^r-1) + k$. Since $nu_3(2^2-1) = nu_3(3) = 1$, we have
$nu_3(2^2cdot 3^k-1) = k+1$.
answered Mar 21 at 14:19
Robert IsraelRobert Israel
330k23219473
$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');
);
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%2f3156820%2fprove-that-4n-1-is-divided-by-3k-if-and-only-if-n-3k-1t%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
In general if the multiplicative order of $a$ mod $p^k$ is $r$ (where $p$ is prime and $a > 1$ is not divisible by $p$), then the order of $a$ mod $p^k+1$ divides $r p$. However, in some cases it is just $r$. I want to prove that doesn't happen in the case $p=3$, $a=2$.
Let $nu_p(x)$ denote the highest exponent $k$ such that $p^k | x$.
Note that $a^3r - 1 = (a^r-1)(a^2r + a^r + 1)$, so $nu_3(a^3r-1) = nu_3(a^r-1) + nu_3(a^2r + a^r + 1)$. If $a^r equiv 1 mod 3$, $a^2r + a^r + 1 equiv 0 mod 3$. However, since $x^2 + x + 1 equiv 0 bmod 9$ has no solutions, it is not $0 bmod 9$. Thus $nu_3(a^2r+a^r+1) = 1$, and $nu_3(a^3r-1) = nu_3(a^r-1) + 1$. By induction, $nu_3(a^3^k r-1) = nu_3(a^r-1) + k$. Since $nu_3(2^2-1) = nu_3(3) = 1$, we have
$nu_3(2^2cdot 3^k-1) = k+1$.
answered Mar 21 at 14:19
Robert IsraelRobert Israel
330k23219473
$endgroup$
add a comment |
$begingroup$
In general if the multiplicative order of $a$ mod $p^k$ is $r$ (where $p$ is prime and $a > 1$ is not divisible by $p$), then the order of $a$ mod $p^k+1$ divides $r p$. However, in some cases it is just $r$. I want to prove that doesn't happen in the case $p=3$, $a=2$.
Let $nu_p(x)$ denote the highest exponent $k$ such that $p^k | x$.
Note that $a^3r - 1 = (a^r-1)(a^2r + a^r + 1)$, so $nu_3(a^3r-1) = nu_3(a^r-1) + nu_3(a^2r + a^r + 1)$. If $a^r equiv 1 mod 3$, $a^2r + a^r + 1 equiv 0 mod 3$. However, since $x^2 + x + 1 equiv 0 bmod 9$ has no solutions, it is not $0 bmod 9$. Thus $nu_3(a^2r+a^r+1) = 1$, and $nu_3(a^3r-1) = nu_3(a^r-1) + 1$. By induction, $nu_3(a^3^k r-1) = nu_3(a^r-1) + k$. Since $nu_3(2^2-1) = nu_3(3) = 1$, we have
$nu_3(2^2cdot 3^k-1) = k+1$.
answered Mar 21 at 14:19
Robert IsraelRobert Israel
330k23219473
$endgroup$
add a comment |
$begingroup$
In general if the multiplicative order of $a$ mod $p^k$ is $r$ (where $p$ is prime and $a > 1$ is not divisible by $p$), then the order of $a$ mod $p^k+1$ divides $r p$. However, in some cases it is just $r$. I want to prove that doesn't happen in the case $p=3$, $a=2$.
Let $nu_p(x)$ denote the highest exponent $k$ such that $p^k | x$.
Note that $a^3r - 1 = (a^r-1)(a^2r + a^r + 1)$, so $nu_3(a^3r-1) = nu_3(a^r-1) + nu_3(a^2r + a^r + 1)$. If $a^r equiv 1 mod 3$, $a^2r + a^r + 1 equiv 0 mod 3$. However, since $x^2 + x + 1 equiv 0 bmod 9$ has no solutions, it is not $0 bmod 9$. Thus $nu_3(a^2r+a^r+1) = 1$, and $nu_3(a^3r-1) = nu_3(a^r-1) + 1$. By induction, $nu_3(a^3^k r-1) = nu_3(a^r-1) + k$. Since $nu_3(2^2-1) = nu_3(3) = 1$, we have
$nu_3(2^2cdot 3^k-1) = k+1$.
answered Mar 21 at 14:19
Robert IsraelRobert Israel
330k23219473
$endgroup$
In general if the multiplicative order of $a$ mod $p^k$ is $r$ (where $p$ is prime and $a > 1$ is not divisible by $p$), then the order of $a$ mod $p^k+1$ divides $r p$. However, in some cases it is just $r$. I want to prove that doesn't happen in the case $p=3$, $a=2$.
Let $nu_p(x)$ denote the highest exponent $k$ such that $p^k | x$.
Note that $a^3r - 1 = (a^r-1)(a^2r + a^r + 1)$, so $nu_3(a^3r-1) = nu_3(a^r-1) + nu_3(a^2r + a^r + 1)$. If $a^r equiv 1 mod 3$, $a^2r + a^r + 1 equiv 0 mod 3$. However, since $x^2 + x + 1 equiv 0 bmod 9$ has no solutions, it is not $0 bmod 9$. Thus $nu_3(a^2r+a^r+1) = 1$, and $nu_3(a^3r-1) = nu_3(a^r-1) + 1$. By induction, $nu_3(a^3^k r-1) = nu_3(a^r-1) + k$. Since $nu_3(2^2-1) = nu_3(3) = 1$, we have
$nu_3(2^2cdot 3^k-1) = k+1$.
answered Mar 21 at 14:19
Robert IsraelRobert Israel
330k23219473
edited Mar 21 at 18:40
answered Mar 21 at 14:19
Robert IsraelRobert Israel
330k23219473
answered Mar 21 at 14:19
Robert IsraelRobert Israel
330k23219473
answered Mar 21 at 14:19
Robert IsraelRobert Israel
330k23219473
330k23219473
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');
);
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%2f3156820%2fprove-that-4n-1-is-divided-by-3k-if-and-only-if-n-3k-1t%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');
);
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');
);
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');
);
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
