Mixing
Nested powers remainder problem.
$begingroup$
I'm struggling a little with a question concerning power towers.
I have this number $2018^{large {2017}^{Large 16050464}}!$ and I want to find the remainder when it is divided by 1001.
I have managed to reduce it down to $16^{large {2017}^{Large 224}}$ but I can't get any further past this point. I feel like I need to reduce $2017^{224}$ to an integer but I am unsure of how to do this.
Just a side note: I have to do it without the Chinese remainder theorem.
Any help is welcome, thanks.
elementary-number-theory modular-arithmetic exponentiation power-towers
$endgroup$
|
show 3 more comments
$begingroup$
I'm struggling a little with a question concerning power towers.
I have this number $2018^{large {2017}^{Large 16050464}}!$ and I want to find the remainder when it is divided by 1001.
I have managed to reduce it down to $16^{large {2017}^{Large 224}}$ but I can't get any further past this point. I feel like I need to reduce $2017^{224}$ to an integer but I am unsure of how to do this.
Just a side note: I have to do it without the Chinese remainder theorem.
Any help is welcome, thanks.
elementary-number-theory modular-arithmetic exponentiation power-towers
$endgroup$
$begingroup$
Take a look at my answer on this question - math.stackexchange.com/questions/3081806/finding-remainders/…
$endgroup$
– user626177
Jan 22 at 18:42
$begingroup$
@someone is it possible to do without the Chinese remainder theorem?
$endgroup$
– user637295
Jan 22 at 18:51
$begingroup$
Chinese remainder theorem is not used in that answer. Feel free to ask if something is not clear.
$endgroup$
– user626177
Jan 22 at 18:54
$begingroup$
@someone The method you use there is in fact one form of CRT.
$endgroup$
– Bill Dubuque
Jan 22 at 19:15
$begingroup$
@BillDubuque Well the fact that I didn't even know about that shows that you don't have to be familiar with CRT to be able to do that calculation, right ?
$endgroup$
– user626177
Jan 22 at 19:53
|
show 3 more comments
$begingroup$
I'm struggling a little with a question concerning power towers.
I have this number $2018^{large {2017}^{Large 16050464}}!$ and I want to find the remainder when it is divided by 1001.
I have managed to reduce it down to $16^{large {2017}^{Large 224}}$ but I can't get any further past this point. I feel like I need to reduce $2017^{224}$ to an integer but I am unsure of how to do this.
Just a side note: I have to do it without the Chinese remainder theorem.
Any help is welcome, thanks.
elementary-number-theory modular-arithmetic exponentiation power-towers
$endgroup$
I'm struggling a little with a question concerning power towers.
I have this number $2018^{large {2017}^{Large 16050464}}!$ and I want to find the remainder when it is divided by 1001.
I have managed to reduce it down to $16^{large {2017}^{Large 224}}$ but I can't get any further past this point. I feel like I need to reduce $2017^{224}$ to an integer but I am unsure of how to do this.
Just a side note: I have to do it without the Chinese remainder theorem.
Any help is welcome, thanks.
elementary-number-theory modular-arithmetic exponentiation power-towers
elementary-number-theory modular-arithmetic exponentiation power-towers
edited Jan 22 at 18:50
asked Jan 22 at 18:30
user637295
$begingroup$
Take a look at my answer on this question - math.stackexchange.com/questions/3081806/finding-remainders/…
$endgroup$
– user626177
Jan 22 at 18:42
$begingroup$
@someone is it possible to do without the Chinese remainder theorem?
$endgroup$
– user637295
Jan 22 at 18:51
$begingroup$
Chinese remainder theorem is not used in that answer. Feel free to ask if something is not clear.
$endgroup$
– user626177
Jan 22 at 18:54
$begingroup$
@someone The method you use there is in fact one form of CRT.
$endgroup$
– Bill Dubuque
Jan 22 at 19:15
$begingroup$
@BillDubuque Well the fact that I didn't even know about that shows that you don't have to be familiar with CRT to be able to do that calculation, right ?
$endgroup$
– user626177
Jan 22 at 19:53
|
show 3 more comments
$begingroup$
Take a look at my answer on this question - math.stackexchange.com/questions/3081806/finding-remainders/…
$endgroup$
– user626177
Jan 22 at 18:42
$begingroup$
@someone is it possible to do without the Chinese remainder theorem?
$endgroup$
– user637295
Jan 22 at 18:51
$begingroup$
Chinese remainder theorem is not used in that answer. Feel free to ask if something is not clear.
$endgroup$
– user626177
Jan 22 at 18:54
$begingroup$
@someone The method you use there is in fact one form of CRT.
$endgroup$
– Bill Dubuque
Jan 22 at 19:15
$begingroup$
@BillDubuque Well the fact that I didn't even know about that shows that you don't have to be familiar with CRT to be able to do that calculation, right ?
$endgroup$
– user626177
Jan 22 at 19:53
$begingroup$
Take a look at my answer on this question - math.stackexchange.com/questions/3081806/finding-remainders/…
$endgroup$
– user626177
Jan 22 at 18:42
$begingroup$
Take a look at my answer on this question - math.stackexchange.com/questions/3081806/finding-remainders/…
$endgroup$
– user626177
Jan 22 at 18:42
$begingroup$
@someone is it possible to do without the Chinese remainder theorem?
$endgroup$
– user637295
Jan 22 at 18:51
$begingroup$
@someone is it possible to do without the Chinese remainder theorem?
$endgroup$
– user637295
Jan 22 at 18:51
$begingroup$
Chinese remainder theorem is not used in that answer. Feel free to ask if something is not clear.
$endgroup$
– user626177
Jan 22 at 18:54
$begingroup$
Chinese remainder theorem is not used in that answer. Feel free to ask if something is not clear.
$endgroup$
– user626177
Jan 22 at 18:54
$begingroup$
@someone The method you use there is in fact one form of CRT.
$endgroup$
– Bill Dubuque
Jan 22 at 19:15
$begingroup$
@someone The method you use there is in fact one form of CRT.
$endgroup$
– Bill Dubuque
Jan 22 at 19:15
$begingroup$
@BillDubuque Well the fact that I didn't even know about that shows that you don't have to be familiar with CRT to be able to do that calculation, right ?
$endgroup$
– user626177
Jan 22 at 19:53
$begingroup$
@BillDubuque Well the fact that I didn't even know about that shows that you don't have to be familiar with CRT to be able to do that calculation, right ?
$endgroup$
– user626177
Jan 22 at 19:53
|
show 3 more comments
1 Answer
1
active
oldest
votes
$begingroup$
$16^{large 3}!equiv 1$ mod $7,&,13;,$ $16^{large 5}!equiv 1pmod{!11},$ so $,16^{largecolor{#0a0}{15}}!equiv 1,$ mod $7,11,13$ so also mod their lcm $=1001$.
Thus $bmod 1001!: 2018^{large 2017^{Large 4N}}!!!equiv 16^{large 2017^{Large 4N}!!bmodcolor{#0a0}{15}}!!equiv 16^{large color{#c00}7^{Largecolor{#c00} 4N}!!bmodcolor{#0a0}{15}}!!equiv 16^{largecolor{#c00} 1^{Large N}}!!equiv 16$
with the expt calculation: $bmodcolor{#0a0}{15}!:, 2017equiv 7, $ and $ color{#c00}7^{largecolor{#c00}4}! equiv 4^{large 2}!equivcolor{#c00} 1$
answered Jan 22 at 21:12
Bill DubuqueBill Dubuque
212k29195651
$endgroup$
$begingroup$
Could you just explain what you have done on the first line, so where the $16^{3}$ etc have come from? Have you chosen $16^{3}$ and $16^{5}$ because they are congruent to 1 and if so how did you know that start with? Thanks
$endgroup$
– user637295
Jan 22 at 22:12
$begingroup$
@LittleRichard They are the order of $16$ mod $p$, i.e. the least $n>0$ such that $,16^nequiv 1pmod{! p}$, e.g. mod $,p = 7!: 16^3equiv 2^3equiv 1$. By Fermat $,16^{p-1}equiv 1pmod{p>2},$ so the order must divide $,p-1.$
$endgroup$
– Bill Dubuque
Jan 22 at 22:14
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%2f3083517%2fnested-powers-remainder-problem%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$
$16^{large 3}!equiv 1$ mod $7,&,13;,$ $16^{large 5}!equiv 1pmod{!11},$ so $,16^{largecolor{#0a0}{15}}!equiv 1,$ mod $7,11,13$ so also mod their lcm $=1001$.
Thus $bmod 1001!: 2018^{large 2017^{Large 4N}}!!!equiv 16^{large 2017^{Large 4N}!!bmodcolor{#0a0}{15}}!!equiv 16^{large color{#c00}7^{Largecolor{#c00} 4N}!!bmodcolor{#0a0}{15}}!!equiv 16^{largecolor{#c00} 1^{Large N}}!!equiv 16$
with the expt calculation: $bmodcolor{#0a0}{15}!:, 2017equiv 7, $ and $ color{#c00}7^{largecolor{#c00}4}! equiv 4^{large 2}!equivcolor{#c00} 1$
answered Jan 22 at 21:12
Bill DubuqueBill Dubuque
212k29195651
$endgroup$
$begingroup$
Could you just explain what you have done on the first line, so where the $16^{3}$ etc have come from? Have you chosen $16^{3}$ and $16^{5}$ because they are congruent to 1 and if so how did you know that start with? Thanks
$endgroup$
– user637295
Jan 22 at 22:12
$begingroup$
@LittleRichard They are the order of $16$ mod $p$, i.e. the least $n>0$ such that $,16^nequiv 1pmod{! p}$, e.g. mod $,p = 7!: 16^3equiv 2^3equiv 1$. By Fermat $,16^{p-1}equiv 1pmod{p>2},$ so the order must divide $,p-1.$
$endgroup$
– Bill Dubuque
Jan 22 at 22:14
add a comment |
$begingroup$
$16^{large 3}!equiv 1$ mod $7,&,13;,$ $16^{large 5}!equiv 1pmod{!11},$ so $,16^{largecolor{#0a0}{15}}!equiv 1,$ mod $7,11,13$ so also mod their lcm $=1001$.
Thus $bmod 1001!: 2018^{large 2017^{Large 4N}}!!!equiv 16^{large 2017^{Large 4N}!!bmodcolor{#0a0}{15}}!!equiv 16^{large color{#c00}7^{Largecolor{#c00} 4N}!!bmodcolor{#0a0}{15}}!!equiv 16^{largecolor{#c00} 1^{Large N}}!!equiv 16$
with the expt calculation: $bmodcolor{#0a0}{15}!:, 2017equiv 7, $ and $ color{#c00}7^{largecolor{#c00}4}! equiv 4^{large 2}!equivcolor{#c00} 1$
answered Jan 22 at 21:12
Bill DubuqueBill Dubuque
212k29195651
$endgroup$
$begingroup$
Could you just explain what you have done on the first line, so where the $16^{3}$ etc have come from? Have you chosen $16^{3}$ and $16^{5}$ because they are congruent to 1 and if so how did you know that start with? Thanks
$endgroup$
– user637295
Jan 22 at 22:12
$begingroup$
@LittleRichard They are the order of $16$ mod $p$, i.e. the least $n>0$ such that $,16^nequiv 1pmod{! p}$, e.g. mod $,p = 7!: 16^3equiv 2^3equiv 1$. By Fermat $,16^{p-1}equiv 1pmod{p>2},$ so the order must divide $,p-1.$
$endgroup$
– Bill Dubuque
Jan 22 at 22:14
add a comment |
$begingroup$
$16^{large 3}!equiv 1$ mod $7,&,13;,$ $16^{large 5}!equiv 1pmod{!11},$ so $,16^{largecolor{#0a0}{15}}!equiv 1,$ mod $7,11,13$ so also mod their lcm $=1001$.
Thus $bmod 1001!: 2018^{large 2017^{Large 4N}}!!!equiv 16^{large 2017^{Large 4N}!!bmodcolor{#0a0}{15}}!!equiv 16^{large color{#c00}7^{Largecolor{#c00} 4N}!!bmodcolor{#0a0}{15}}!!equiv 16^{largecolor{#c00} 1^{Large N}}!!equiv 16$
with the expt calculation: $bmodcolor{#0a0}{15}!:, 2017equiv 7, $ and $ color{#c00}7^{largecolor{#c00}4}! equiv 4^{large 2}!equivcolor{#c00} 1$
answered Jan 22 at 21:12
Bill DubuqueBill Dubuque
212k29195651
$endgroup$
$16^{large 3}!equiv 1$ mod $7,&,13;,$ $16^{large 5}!equiv 1pmod{!11},$ so $,16^{largecolor{#0a0}{15}}!equiv 1,$ mod $7,11,13$ so also mod their lcm $=1001$.
Thus $bmod 1001!: 2018^{large 2017^{Large 4N}}!!!equiv 16^{large 2017^{Large 4N}!!bmodcolor{#0a0}{15}}!!equiv 16^{large color{#c00}7^{Largecolor{#c00} 4N}!!bmodcolor{#0a0}{15}}!!equiv 16^{largecolor{#c00} 1^{Large N}}!!equiv 16$
with the expt calculation: $bmodcolor{#0a0}{15}!:, 2017equiv 7, $ and $ color{#c00}7^{largecolor{#c00}4}! equiv 4^{large 2}!equivcolor{#c00} 1$
answered Jan 22 at 21:12
Bill DubuqueBill Dubuque
212k29195651
edited Jan 22 at 21:25
answered Jan 22 at 21:12
Bill DubuqueBill Dubuque
212k29195651
answered Jan 22 at 21:12
Bill DubuqueBill Dubuque
212k29195651
answered Jan 22 at 21:12
Bill DubuqueBill Dubuque
212k29195651
212k29195651
$begingroup$
Could you just explain what you have done on the first line, so where the $16^{3}$ etc have come from? Have you chosen $16^{3}$ and $16^{5}$ because they are congruent to 1 and if so how did you know that start with? Thanks
$endgroup$
– user637295
Jan 22 at 22:12
$begingroup$
@LittleRichard They are the order of $16$ mod $p$, i.e. the least $n>0$ such that $,16^nequiv 1pmod{! p}$, e.g. mod $,p = 7!: 16^3equiv 2^3equiv 1$. By Fermat $,16^{p-1}equiv 1pmod{p>2},$ so the order must divide $,p-1.$
$endgroup$
– Bill Dubuque
Jan 22 at 22:14
add a comment |
$begingroup$
Could you just explain what you have done on the first line, so where the $16^{3}$ etc have come from? Have you chosen $16^{3}$ and $16^{5}$ because they are congruent to 1 and if so how did you know that start with? Thanks
$endgroup$
– user637295
Jan 22 at 22:12
$begingroup$
@LittleRichard They are the order of $16$ mod $p$, i.e. the least $n>0$ such that $,16^nequiv 1pmod{! p}$, e.g. mod $,p = 7!: 16^3equiv 2^3equiv 1$. By Fermat $,16^{p-1}equiv 1pmod{p>2},$ so the order must divide $,p-1.$
$endgroup$
– Bill Dubuque
Jan 22 at 22:14
$begingroup$
Could you just explain what you have done on the first line, so where the $16^{3}$ etc have come from? Have you chosen $16^{3}$ and $16^{5}$ because they are congruent to 1 and if so how did you know that start with? Thanks
$endgroup$
– user637295
Jan 22 at 22:12
$begingroup$
Could you just explain what you have done on the first line, so where the $16^{3}$ etc have come from? Have you chosen $16^{3}$ and $16^{5}$ because they are congruent to 1 and if so how did you know that start with? Thanks
$endgroup$
– user637295
Jan 22 at 22:12
$begingroup$
@LittleRichard They are the order of $16$ mod $p$, i.e. the least $n>0$ such that $,16^nequiv 1pmod{! p}$, e.g. mod $,p = 7!: 16^3equiv 2^3equiv 1$. By Fermat $,16^{p-1}equiv 1pmod{p>2},$ so the order must divide $,p-1.$
$endgroup$
– Bill Dubuque
Jan 22 at 22:14
$begingroup$
@LittleRichard They are the order of $16$ mod $p$, i.e. the least $n>0$ such that $,16^nequiv 1pmod{! p}$, e.g. mod $,p = 7!: 16^3equiv 2^3equiv 1$. By Fermat $,16^{p-1}equiv 1pmod{p>2},$ so the order must divide $,p-1.$
$endgroup$
– Bill Dubuque
Jan 22 at 22:14
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%2f3083517%2fnested-powers-remainder-problem%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
$begingroup$
Take a look at my answer on this question - math.stackexchange.com/questions/3081806/finding-remainders/…
$endgroup$
– user626177
Jan 22 at 18:42
$begingroup$
@someone is it possible to do without the Chinese remainder theorem?
$endgroup$
– user637295
Jan 22 at 18:51
$begingroup$
Chinese remainder theorem is not used in that answer. Feel free to ask if something is not clear.
$endgroup$
– user626177
Jan 22 at 18:54
$begingroup$
@someone The method you use there is in fact one form of CRT.
$endgroup$
– Bill Dubuque
Jan 22 at 19:15
$begingroup$
@BillDubuque Well the fact that I didn't even know about that shows that you don't have to be familiar with CRT to be able to do that calculation, right ?
$endgroup$
– user626177
Jan 22 at 19:53