For what values of n (where n is a natural number) is this statement true: $3^n - n - 1 ≡ 0pmod5$
$begingroup$
I'm clueless as where to start with this, $3^n$ seems to be of period 4, where $ - n - 1$ is of period 5.
modular-arithmetic
edited Dec 28 '18 at 23:33
Bernard
123k741116
asked Dec 28 '18 at 23:15
Elhamer YacineElhamer Yacine
102
$endgroup$
add a comment |
$begingroup$
I'm clueless as where to start with this, $3^n$ seems to be of period 4, where $ - n - 1$ is of period 5.
modular-arithmetic
edited Dec 28 '18 at 23:33
Bernard
123k741116
asked Dec 28 '18 at 23:15
Elhamer YacineElhamer Yacine
102
$endgroup$
add a comment |
$begingroup$
I'm clueless as where to start with this, $3^n$ seems to be of period 4, where $ - n - 1$ is of period 5.
modular-arithmetic
edited Dec 28 '18 at 23:33
Bernard
123k741116
asked Dec 28 '18 at 23:15
Elhamer YacineElhamer Yacine
102
$endgroup$
I'm clueless as where to start with this, $3^n$ seems to be of period 4, where $ - n - 1$ is of period 5.
modular-arithmetic
modular-arithmetic
edited Dec 28 '18 at 23:33
Bernard
123k741116
asked Dec 28 '18 at 23:15
Elhamer YacineElhamer Yacine
102
edited Dec 28 '18 at 23:33
Bernard
123k741116
asked Dec 28 '18 at 23:15
Elhamer YacineElhamer Yacine
102
edited Dec 28 '18 at 23:33
Bernard
123k741116
edited Dec 28 '18 at 23:33
Bernard
123k741116
edited Dec 28 '18 at 23:33
Bernard
123k741116
123k741116
asked Dec 28 '18 at 23:15
Elhamer YacineElhamer Yacine
102
asked Dec 28 '18 at 23:15
Elhamer YacineElhamer Yacine
102
asked Dec 28 '18 at 23:15
Elhamer YacineElhamer Yacine
102
102
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
$, n = 4q!+!r, 0le rle 3.,$ $bmod 5!: color{#0a0}1 equiv 3^{large n}!-nequiv 3^{large r} overbrace{(3^{large 4})^{large q}}^{large 3^{Large 4} equiv 1}!-4q!-!requiv color{#0a0}{3^{large r}!+q-r}$
$,r=0,Rightarrow color{#0a0}{1equiv 3^{large 0}!+q-0} $ so $,color{#c00}{qequiv 0pmod{!5}},$ so $,n = 4color{#c00}q!+!r=4(color{#c00}{0!+!5k})!+!0 = 20k$
$,r = 1,2,3,$ are done the same way. You'll find the $rmcolor{#c00}{solutions}$ enumerated below. $!!begin{array}{|r|r|}
hline
n & 0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19\
hline
n!+!1bmod 5 &color{#c00}1&2&3&4&0&1&2&3&4&0&1&color{#c00}2&3&4&0&1&2&color{#c00}3&color{#c00}4&0\
hline
3^nbmod 5 &color{#c00}1&3&4&2&1&3&4&2&1&3&4&color{#c00}2&1&3&4&2&1&color{#c00}3&color{#c00} 4&2\
hline
end{array}$
answered Dec 29 '18 at 0:18
Bill DubuqueBill Dubuque
212k29195654
$endgroup$
$begingroup$
Yeah this a nice addition. Anyways, suppose the expression was instead in the form: $a^n - n - 1 ≡ 0 ( mod 5 )$ where $a^n$ is of period 5, here I wouldn't have to go the long route, since both of the conjoined expressions are of the same period, there are only 5 possibilities (that is $n=5k+r$ where $0≤r≤5$). furthermore, when we have two conjoined expressions with different cycling periods their lcm is equal to the number of "possibilities", right?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:36
$begingroup$
@Elhamer By Fermat, $bmod 5!: anotequiv 0,Rightarrow, a^4equiv 1,$ so $a$ has order a divisor of $4$ (so it can't have period $5) $
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:42
$begingroup$
Hmm, can you please link me the specific theorem?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:46
$begingroup$
also, is the lcm part of my first response correct?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:47
$begingroup$
Fermat's little Theorem. Yes, lcm arguments like that work in the appropriate context.
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:51
|
show 2 more comments
$begingroup$
I would say that's a pretty good start! So $3^n-n-1$ has period $20$. Now write down $3^n bmod 5$ for $n=1$ to $20$, and $n+1bmod 5$ for $n=1$ to $20$, and see where they match. Of course you only need to compute $3^n$ for $n=1$ to $4$, because it repeats after that.
answered Dec 28 '18 at 23:21
TonyKTonyK
43.5k357136
$endgroup$
1
$begingroup$
Sorry, but how do I exactly prove that $3^n - n - 1$ has period 20? I know that $3^n$ is of period 4, and $n+1 mod 5$ is of a 5 one. I assume there's a specific theorem or something to credit in the written solution.
$endgroup$
– Elhamer Yacine
Dec 28 '18 at 23:39
$begingroup$
$20$ is the least common multiple of $4$ and $5$. Think about it a bit.
$endgroup$
– TonyK
Dec 29 '18 at 0:39
add a comment |
$begingroup$
As ord$_53=4,$
it's sufficient to all $4$ distinct residuals.
For example,
Case$#1:$
if $n=4m,3^n-n-1equiv(3^4)^m-4m-1equiv1^m-4m-1pmod5$
So, we need $5|-4miff5|miff 20|4m=n$
Case$#4:$
If $n=4m+3,3^n-n-1equiv3^3-(4m+3)-1equiv23-4mpmod5$
$iff4mequiv23pmod5equiv23+5iff mequiv7equiv2, m=5r+2$(say)
$n=4m+3=4(5r+2)+3equiv11pmod{20}$
Can you please try with $n=4m+1,4m+2$
answered Dec 28 '18 at 23:45
lab bhattacharjeelab bhattacharjee
227k15158275
$endgroup$
$begingroup$
Yeah, this is a nicer solution, exactly what I was looking for. the final results are: $n = {20k, 20k+17, 20k+18, 20k+11}$.
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:16
$begingroup$
@ElhamerYacine We don't need to repeat the whole derivation for each remainder $, r = nbmod 4.,$ Rather we can do it once $rmcolor{#0a0}{generically}$ then substitute for each $,r,,$ e.g. see my answer.
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:23
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%2f3055377%2ffor-what-values-of-n-where-n-is-a-natural-number-is-this-statement-true-3n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
$, n = 4q!+!r, 0le rle 3.,$ $bmod 5!: color{#0a0}1 equiv 3^{large n}!-nequiv 3^{large r} overbrace{(3^{large 4})^{large q}}^{large 3^{Large 4} equiv 1}!-4q!-!requiv color{#0a0}{3^{large r}!+q-r}$
$,r=0,Rightarrow color{#0a0}{1equiv 3^{large 0}!+q-0} $ so $,color{#c00}{qequiv 0pmod{!5}},$ so $,n = 4color{#c00}q!+!r=4(color{#c00}{0!+!5k})!+!0 = 20k$
$,r = 1,2,3,$ are done the same way. You'll find the $rmcolor{#c00}{solutions}$ enumerated below. $!!begin{array}{|r|r|}
hline
n & 0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19\
hline
n!+!1bmod 5 &color{#c00}1&2&3&4&0&1&2&3&4&0&1&color{#c00}2&3&4&0&1&2&color{#c00}3&color{#c00}4&0\
hline
3^nbmod 5 &color{#c00}1&3&4&2&1&3&4&2&1&3&4&color{#c00}2&1&3&4&2&1&color{#c00}3&color{#c00} 4&2\
hline
end{array}$
answered Dec 29 '18 at 0:18
Bill DubuqueBill Dubuque
212k29195654
$endgroup$
$begingroup$
Yeah this a nice addition. Anyways, suppose the expression was instead in the form: $a^n - n - 1 ≡ 0 ( mod 5 )$ where $a^n$ is of period 5, here I wouldn't have to go the long route, since both of the conjoined expressions are of the same period, there are only 5 possibilities (that is $n=5k+r$ where $0≤r≤5$). furthermore, when we have two conjoined expressions with different cycling periods their lcm is equal to the number of "possibilities", right?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:36
$begingroup$
@Elhamer By Fermat, $bmod 5!: anotequiv 0,Rightarrow, a^4equiv 1,$ so $a$ has order a divisor of $4$ (so it can't have period $5) $
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:42
$begingroup$
Hmm, can you please link me the specific theorem?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:46
$begingroup$
also, is the lcm part of my first response correct?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:47
$begingroup$
Fermat's little Theorem. Yes, lcm arguments like that work in the appropriate context.
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:51
|
show 2 more comments
$begingroup$
$, n = 4q!+!r, 0le rle 3.,$ $bmod 5!: color{#0a0}1 equiv 3^{large n}!-nequiv 3^{large r} overbrace{(3^{large 4})^{large q}}^{large 3^{Large 4} equiv 1}!-4q!-!requiv color{#0a0}{3^{large r}!+q-r}$
$,r=0,Rightarrow color{#0a0}{1equiv 3^{large 0}!+q-0} $ so $,color{#c00}{qequiv 0pmod{!5}},$ so $,n = 4color{#c00}q!+!r=4(color{#c00}{0!+!5k})!+!0 = 20k$
$,r = 1,2,3,$ are done the same way. You'll find the $rmcolor{#c00}{solutions}$ enumerated below. $!!begin{array}{|r|r|}
hline
n & 0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19\
hline
n!+!1bmod 5 &color{#c00}1&2&3&4&0&1&2&3&4&0&1&color{#c00}2&3&4&0&1&2&color{#c00}3&color{#c00}4&0\
hline
3^nbmod 5 &color{#c00}1&3&4&2&1&3&4&2&1&3&4&color{#c00}2&1&3&4&2&1&color{#c00}3&color{#c00} 4&2\
hline
end{array}$
answered Dec 29 '18 at 0:18
Bill DubuqueBill Dubuque
212k29195654
$endgroup$
$begingroup$
Yeah this a nice addition. Anyways, suppose the expression was instead in the form: $a^n - n - 1 ≡ 0 ( mod 5 )$ where $a^n$ is of period 5, here I wouldn't have to go the long route, since both of the conjoined expressions are of the same period, there are only 5 possibilities (that is $n=5k+r$ where $0≤r≤5$). furthermore, when we have two conjoined expressions with different cycling periods their lcm is equal to the number of "possibilities", right?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:36
$begingroup$
@Elhamer By Fermat, $bmod 5!: anotequiv 0,Rightarrow, a^4equiv 1,$ so $a$ has order a divisor of $4$ (so it can't have period $5) $
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:42
$begingroup$
Hmm, can you please link me the specific theorem?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:46
$begingroup$
also, is the lcm part of my first response correct?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:47
$begingroup$
Fermat's little Theorem. Yes, lcm arguments like that work in the appropriate context.
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:51
|
show 2 more comments
$begingroup$
$, n = 4q!+!r, 0le rle 3.,$ $bmod 5!: color{#0a0}1 equiv 3^{large n}!-nequiv 3^{large r} overbrace{(3^{large 4})^{large q}}^{large 3^{Large 4} equiv 1}!-4q!-!requiv color{#0a0}{3^{large r}!+q-r}$
$,r=0,Rightarrow color{#0a0}{1equiv 3^{large 0}!+q-0} $ so $,color{#c00}{qequiv 0pmod{!5}},$ so $,n = 4color{#c00}q!+!r=4(color{#c00}{0!+!5k})!+!0 = 20k$
$,r = 1,2,3,$ are done the same way. You'll find the $rmcolor{#c00}{solutions}$ enumerated below. $!!begin{array}{|r|r|}
hline
n & 0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19\
hline
n!+!1bmod 5 &color{#c00}1&2&3&4&0&1&2&3&4&0&1&color{#c00}2&3&4&0&1&2&color{#c00}3&color{#c00}4&0\
hline
3^nbmod 5 &color{#c00}1&3&4&2&1&3&4&2&1&3&4&color{#c00}2&1&3&4&2&1&color{#c00}3&color{#c00} 4&2\
hline
end{array}$
answered Dec 29 '18 at 0:18
Bill DubuqueBill Dubuque
212k29195654
$endgroup$
$, n = 4q!+!r, 0le rle 3.,$ $bmod 5!: color{#0a0}1 equiv 3^{large n}!-nequiv 3^{large r} overbrace{(3^{large 4})^{large q}}^{large 3^{Large 4} equiv 1}!-4q!-!requiv color{#0a0}{3^{large r}!+q-r}$
$,r=0,Rightarrow color{#0a0}{1equiv 3^{large 0}!+q-0} $ so $,color{#c00}{qequiv 0pmod{!5}},$ so $,n = 4color{#c00}q!+!r=4(color{#c00}{0!+!5k})!+!0 = 20k$
$,r = 1,2,3,$ are done the same way. You'll find the $rmcolor{#c00}{solutions}$ enumerated below. $!!begin{array}{|r|r|}
hline
n & 0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19\
hline
n!+!1bmod 5 &color{#c00}1&2&3&4&0&1&2&3&4&0&1&color{#c00}2&3&4&0&1&2&color{#c00}3&color{#c00}4&0\
hline
3^nbmod 5 &color{#c00}1&3&4&2&1&3&4&2&1&3&4&color{#c00}2&1&3&4&2&1&color{#c00}3&color{#c00} 4&2\
hline
end{array}$
answered Dec 29 '18 at 0:18
Bill DubuqueBill Dubuque
212k29195654
edited Dec 29 '18 at 1:07
answered Dec 29 '18 at 0:18
Bill DubuqueBill Dubuque
212k29195654
answered Dec 29 '18 at 0:18
Bill DubuqueBill Dubuque
212k29195654
answered Dec 29 '18 at 0:18
Bill DubuqueBill Dubuque
212k29195654
212k29195654
$begingroup$
Yeah this a nice addition. Anyways, suppose the expression was instead in the form: $a^n - n - 1 ≡ 0 ( mod 5 )$ where $a^n$ is of period 5, here I wouldn't have to go the long route, since both of the conjoined expressions are of the same period, there are only 5 possibilities (that is $n=5k+r$ where $0≤r≤5$). furthermore, when we have two conjoined expressions with different cycling periods their lcm is equal to the number of "possibilities", right?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:36
$begingroup$
@Elhamer By Fermat, $bmod 5!: anotequiv 0,Rightarrow, a^4equiv 1,$ so $a$ has order a divisor of $4$ (so it can't have period $5) $
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:42
$begingroup$
Hmm, can you please link me the specific theorem?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:46
$begingroup$
also, is the lcm part of my first response correct?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:47
$begingroup$
Fermat's little Theorem. Yes, lcm arguments like that work in the appropriate context.
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:51
|
show 2 more comments
$begingroup$
Yeah this a nice addition. Anyways, suppose the expression was instead in the form: $a^n - n - 1 ≡ 0 ( mod 5 )$ where $a^n$ is of period 5, here I wouldn't have to go the long route, since both of the conjoined expressions are of the same period, there are only 5 possibilities (that is $n=5k+r$ where $0≤r≤5$). furthermore, when we have two conjoined expressions with different cycling periods their lcm is equal to the number of "possibilities", right?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:36
$begingroup$
@Elhamer By Fermat, $bmod 5!: anotequiv 0,Rightarrow, a^4equiv 1,$ so $a$ has order a divisor of $4$ (so it can't have period $5) $
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:42
$begingroup$
Hmm, can you please link me the specific theorem?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:46
$begingroup$
also, is the lcm part of my first response correct?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:47
$begingroup$
Fermat's little Theorem. Yes, lcm arguments like that work in the appropriate context.
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:51
$begingroup$
Yeah this a nice addition. Anyways, suppose the expression was instead in the form: $a^n - n - 1 ≡ 0 ( mod 5 )$ where $a^n$ is of period 5, here I wouldn't have to go the long route, since both of the conjoined expressions are of the same period, there are only 5 possibilities (that is $n=5k+r$ where $0≤r≤5$). furthermore, when we have two conjoined expressions with different cycling periods their lcm is equal to the number of "possibilities", right?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:36
$begingroup$
Yeah this a nice addition. Anyways, suppose the expression was instead in the form: $a^n - n - 1 ≡ 0 ( mod 5 )$ where $a^n$ is of period 5, here I wouldn't have to go the long route, since both of the conjoined expressions are of the same period, there are only 5 possibilities (that is $n=5k+r$ where $0≤r≤5$). furthermore, when we have two conjoined expressions with different cycling periods their lcm is equal to the number of "possibilities", right?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:36
$begingroup$
@Elhamer By Fermat, $bmod 5!: anotequiv 0,Rightarrow, a^4equiv 1,$ so $a$ has order a divisor of $4$ (so it can't have period $5) $
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:42
$begingroup$
@Elhamer By Fermat, $bmod 5!: anotequiv 0,Rightarrow, a^4equiv 1,$ so $a$ has order a divisor of $4$ (so it can't have period $5) $
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:42
$begingroup$
Hmm, can you please link me the specific theorem?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:46
$begingroup$
Hmm, can you please link me the specific theorem?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:46
$begingroup$
also, is the lcm part of my first response correct?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:47
$begingroup$
also, is the lcm part of my first response correct?
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:47
$begingroup$
Fermat's little Theorem. Yes, lcm arguments like that work in the appropriate context.
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:51
$begingroup$
Fermat's little Theorem. Yes, lcm arguments like that work in the appropriate context.
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:51
|
show 2 more comments
$begingroup$
I would say that's a pretty good start! So $3^n-n-1$ has period $20$. Now write down $3^n bmod 5$ for $n=1$ to $20$, and $n+1bmod 5$ for $n=1$ to $20$, and see where they match. Of course you only need to compute $3^n$ for $n=1$ to $4$, because it repeats after that.
answered Dec 28 '18 at 23:21
TonyKTonyK
43.5k357136
$endgroup$
1
$begingroup$
Sorry, but how do I exactly prove that $3^n - n - 1$ has period 20? I know that $3^n$ is of period 4, and $n+1 mod 5$ is of a 5 one. I assume there's a specific theorem or something to credit in the written solution.
$endgroup$
– Elhamer Yacine
Dec 28 '18 at 23:39
$begingroup$
$20$ is the least common multiple of $4$ and $5$. Think about it a bit.
$endgroup$
– TonyK
Dec 29 '18 at 0:39
add a comment |
$begingroup$
I would say that's a pretty good start! So $3^n-n-1$ has period $20$. Now write down $3^n bmod 5$ for $n=1$ to $20$, and $n+1bmod 5$ for $n=1$ to $20$, and see where they match. Of course you only need to compute $3^n$ for $n=1$ to $4$, because it repeats after that.
answered Dec 28 '18 at 23:21
TonyKTonyK
43.5k357136
$endgroup$
1
$begingroup$
Sorry, but how do I exactly prove that $3^n - n - 1$ has period 20? I know that $3^n$ is of period 4, and $n+1 mod 5$ is of a 5 one. I assume there's a specific theorem or something to credit in the written solution.
$endgroup$
– Elhamer Yacine
Dec 28 '18 at 23:39
$begingroup$
$20$ is the least common multiple of $4$ and $5$. Think about it a bit.
$endgroup$
– TonyK
Dec 29 '18 at 0:39
add a comment |
$begingroup$
I would say that's a pretty good start! So $3^n-n-1$ has period $20$. Now write down $3^n bmod 5$ for $n=1$ to $20$, and $n+1bmod 5$ for $n=1$ to $20$, and see where they match. Of course you only need to compute $3^n$ for $n=1$ to $4$, because it repeats after that.
answered Dec 28 '18 at 23:21
TonyKTonyK
43.5k357136
$endgroup$
I would say that's a pretty good start! So $3^n-n-1$ has period $20$. Now write down $3^n bmod 5$ for $n=1$ to $20$, and $n+1bmod 5$ for $n=1$ to $20$, and see where they match. Of course you only need to compute $3^n$ for $n=1$ to $4$, because it repeats after that.
answered Dec 28 '18 at 23:21
TonyKTonyK
43.5k357136
answered Dec 28 '18 at 23:21
TonyKTonyK
43.5k357136
answered Dec 28 '18 at 23:21
TonyKTonyK
43.5k357136
answered Dec 28 '18 at 23:21
TonyKTonyK
43.5k357136
43.5k357136
1
$begingroup$
Sorry, but how do I exactly prove that $3^n - n - 1$ has period 20? I know that $3^n$ is of period 4, and $n+1 mod 5$ is of a 5 one. I assume there's a specific theorem or something to credit in the written solution.
$endgroup$
– Elhamer Yacine
Dec 28 '18 at 23:39
$begingroup$
$20$ is the least common multiple of $4$ and $5$. Think about it a bit.
$endgroup$
– TonyK
Dec 29 '18 at 0:39
add a comment |
1
$begingroup$
Sorry, but how do I exactly prove that $3^n - n - 1$ has period 20? I know that $3^n$ is of period 4, and $n+1 mod 5$ is of a 5 one. I assume there's a specific theorem or something to credit in the written solution.
$endgroup$
– Elhamer Yacine
Dec 28 '18 at 23:39
$begingroup$
$20$ is the least common multiple of $4$ and $5$. Think about it a bit.
$endgroup$
– TonyK
Dec 29 '18 at 0:39
1
1
$begingroup$
Sorry, but how do I exactly prove that $3^n - n - 1$ has period 20? I know that $3^n$ is of period 4, and $n+1 mod 5$ is of a 5 one. I assume there's a specific theorem or something to credit in the written solution.
$endgroup$
– Elhamer Yacine
Dec 28 '18 at 23:39
$begingroup$
Sorry, but how do I exactly prove that $3^n - n - 1$ has period 20? I know that $3^n$ is of period 4, and $n+1 mod 5$ is of a 5 one. I assume there's a specific theorem or something to credit in the written solution.
$endgroup$
– Elhamer Yacine
Dec 28 '18 at 23:39
$begingroup$
$20$ is the least common multiple of $4$ and $5$. Think about it a bit.
$endgroup$
– TonyK
Dec 29 '18 at 0:39
$begingroup$
$20$ is the least common multiple of $4$ and $5$. Think about it a bit.
$endgroup$
– TonyK
Dec 29 '18 at 0:39
add a comment |
$begingroup$
As ord$_53=4,$
it's sufficient to all $4$ distinct residuals.
For example,
Case$#1:$
if $n=4m,3^n-n-1equiv(3^4)^m-4m-1equiv1^m-4m-1pmod5$
So, we need $5|-4miff5|miff 20|4m=n$
Case$#4:$
If $n=4m+3,3^n-n-1equiv3^3-(4m+3)-1equiv23-4mpmod5$
$iff4mequiv23pmod5equiv23+5iff mequiv7equiv2, m=5r+2$(say)
$n=4m+3=4(5r+2)+3equiv11pmod{20}$
Can you please try with $n=4m+1,4m+2$
answered Dec 28 '18 at 23:45
lab bhattacharjeelab bhattacharjee
227k15158275
$endgroup$
$begingroup$
Yeah, this is a nicer solution, exactly what I was looking for. the final results are: $n = {20k, 20k+17, 20k+18, 20k+11}$.
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:16
$begingroup$
@ElhamerYacine We don't need to repeat the whole derivation for each remainder $, r = nbmod 4.,$ Rather we can do it once $rmcolor{#0a0}{generically}$ then substitute for each $,r,,$ e.g. see my answer.
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:23
add a comment |
$begingroup$
As ord$_53=4,$
it's sufficient to all $4$ distinct residuals.
For example,
Case$#1:$
if $n=4m,3^n-n-1equiv(3^4)^m-4m-1equiv1^m-4m-1pmod5$
So, we need $5|-4miff5|miff 20|4m=n$
Case$#4:$
If $n=4m+3,3^n-n-1equiv3^3-(4m+3)-1equiv23-4mpmod5$
$iff4mequiv23pmod5equiv23+5iff mequiv7equiv2, m=5r+2$(say)
$n=4m+3=4(5r+2)+3equiv11pmod{20}$
Can you please try with $n=4m+1,4m+2$
answered Dec 28 '18 at 23:45
lab bhattacharjeelab bhattacharjee
227k15158275
$endgroup$
$begingroup$
Yeah, this is a nicer solution, exactly what I was looking for. the final results are: $n = {20k, 20k+17, 20k+18, 20k+11}$.
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:16
$begingroup$
@ElhamerYacine We don't need to repeat the whole derivation for each remainder $, r = nbmod 4.,$ Rather we can do it once $rmcolor{#0a0}{generically}$ then substitute for each $,r,,$ e.g. see my answer.
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:23
add a comment |
$begingroup$
As ord$_53=4,$
it's sufficient to all $4$ distinct residuals.
For example,
Case$#1:$
if $n=4m,3^n-n-1equiv(3^4)^m-4m-1equiv1^m-4m-1pmod5$
So, we need $5|-4miff5|miff 20|4m=n$
Case$#4:$
If $n=4m+3,3^n-n-1equiv3^3-(4m+3)-1equiv23-4mpmod5$
$iff4mequiv23pmod5equiv23+5iff mequiv7equiv2, m=5r+2$(say)
$n=4m+3=4(5r+2)+3equiv11pmod{20}$
Can you please try with $n=4m+1,4m+2$
answered Dec 28 '18 at 23:45
lab bhattacharjeelab bhattacharjee
227k15158275
$endgroup$
As ord$_53=4,$
it's sufficient to all $4$ distinct residuals.
For example,
Case$#1:$
if $n=4m,3^n-n-1equiv(3^4)^m-4m-1equiv1^m-4m-1pmod5$
So, we need $5|-4miff5|miff 20|4m=n$
Case$#4:$
If $n=4m+3,3^n-n-1equiv3^3-(4m+3)-1equiv23-4mpmod5$
$iff4mequiv23pmod5equiv23+5iff mequiv7equiv2, m=5r+2$(say)
$n=4m+3=4(5r+2)+3equiv11pmod{20}$
Can you please try with $n=4m+1,4m+2$
answered Dec 28 '18 at 23:45
lab bhattacharjeelab bhattacharjee
227k15158275
answered Dec 28 '18 at 23:45
lab bhattacharjeelab bhattacharjee
227k15158275
answered Dec 28 '18 at 23:45
lab bhattacharjeelab bhattacharjee
227k15158275
answered Dec 28 '18 at 23:45
lab bhattacharjeelab bhattacharjee
227k15158275
227k15158275
$begingroup$
Yeah, this is a nicer solution, exactly what I was looking for. the final results are: $n = {20k, 20k+17, 20k+18, 20k+11}$.
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:16
$begingroup$
@ElhamerYacine We don't need to repeat the whole derivation for each remainder $, r = nbmod 4.,$ Rather we can do it once $rmcolor{#0a0}{generically}$ then substitute for each $,r,,$ e.g. see my answer.
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:23
add a comment |
$begingroup$
Yeah, this is a nicer solution, exactly what I was looking for. the final results are: $n = {20k, 20k+17, 20k+18, 20k+11}$.
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:16
$begingroup$
@ElhamerYacine We don't need to repeat the whole derivation for each remainder $, r = nbmod 4.,$ Rather we can do it once $rmcolor{#0a0}{generically}$ then substitute for each $,r,,$ e.g. see my answer.
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:23
$begingroup$
Yeah, this is a nicer solution, exactly what I was looking for. the final results are: $n = {20k, 20k+17, 20k+18, 20k+11}$.
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:16
$begingroup$
Yeah, this is a nicer solution, exactly what I was looking for. the final results are: $n = {20k, 20k+17, 20k+18, 20k+11}$.
$endgroup$
– Elhamer Yacine
Dec 29 '18 at 0:16
$begingroup$
@ElhamerYacine We don't need to repeat the whole derivation for each remainder $, r = nbmod 4.,$ Rather we can do it once $rmcolor{#0a0}{generically}$ then substitute for each $,r,,$ e.g. see my answer.
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:23
$begingroup$
@ElhamerYacine We don't need to repeat the whole derivation for each remainder $, r = nbmod 4.,$ Rather we can do it once $rmcolor{#0a0}{generically}$ then substitute for each $,r,,$ e.g. see my answer.
$endgroup$
– Bill Dubuque
Dec 29 '18 at 0:23
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%2f3055377%2ffor-what-values-of-n-where-n-is-a-natural-number-is-this-statement-true-3n%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
