Mixing
Last digit of power explanation
$begingroup$
This question follows up on an example from brilliant.org
Look at the example of finding the last three digits of $4^{2^{42}}$
Euler's totient function is used, but I think incorrectly so I want to clear my doubts. The author uses it for reducing the exponent. Concretely this is the issue:
$2^{42} equiv 2^2 equiv 4$ (mod 100)
How is it possible to use Euler's theorem to reduce this exponent if $2$ and $100$ are not coprime?
modular-arithmetic problem-solving
asked Jan 22 at 19:58
Michael MuntaMichael Munta
8011
$endgroup$
add a comment |
$begingroup$
This question follows up on an example from brilliant.org
Look at the example of finding the last three digits of $4^{2^{42}}$
Euler's totient function is used, but I think incorrectly so I want to clear my doubts. The author uses it for reducing the exponent. Concretely this is the issue:
$2^{42} equiv 2^2 equiv 4$ (mod 100)
How is it possible to use Euler's theorem to reduce this exponent if $2$ and $100$ are not coprime?
modular-arithmetic problem-solving
asked Jan 22 at 19:58
Michael MuntaMichael Munta
8011
$endgroup$
$begingroup$
Indeed, even though $varphi(100)=40$ we have $2^{40}equiv 76pmod {100}$. Still, it's not hard to verify that $2^{42}equiv 4 pmod {100}$.
$endgroup$
– lulu
Jan 22 at 20:05
$begingroup$
I know it is easy to verify, but the point is not to use a calculator and I was trying to understand how can that be usage of Euler's theorem so I did not use CRT. So you agree it is an error?
$endgroup$
– Michael Munta
Jan 22 at 20:22
1
$begingroup$
Shouldn't need a calculator. $varphi(25)=20$ so $2^{40}equiv 1 pmod {25}$ so $2^{42}equiv 4pmod {25}$. Clearly $2^{42}equiv 0 pmod 4$ and the chinese remainder theorem immediately settles the point.
$endgroup$
– lulu
Jan 22 at 20:27
$begingroup$
Not sure I'd call what they wrote an error, though I'd agree it was unhelpfully terse. Euler's Theorem is the way to go here. You just have to realize that you should apply it to $25$, not $100$.
$endgroup$
– lulu
Jan 22 at 20:28
add a comment |
$begingroup$
This question follows up on an example from brilliant.org
Look at the example of finding the last three digits of $4^{2^{42}}$
Euler's totient function is used, but I think incorrectly so I want to clear my doubts. The author uses it for reducing the exponent. Concretely this is the issue:
$2^{42} equiv 2^2 equiv 4$ (mod 100)
How is it possible to use Euler's theorem to reduce this exponent if $2$ and $100$ are not coprime?
modular-arithmetic problem-solving
asked Jan 22 at 19:58
Michael MuntaMichael Munta
8011
$endgroup$
This question follows up on an example from brilliant.org
Look at the example of finding the last three digits of $4^{2^{42}}$
Euler's totient function is used, but I think incorrectly so I want to clear my doubts. The author uses it for reducing the exponent. Concretely this is the issue:
$2^{42} equiv 2^2 equiv 4$ (mod 100)
How is it possible to use Euler's theorem to reduce this exponent if $2$ and $100$ are not coprime?
modular-arithmetic problem-solving
modular-arithmetic problem-solving
asked Jan 22 at 19:58
Michael MuntaMichael Munta
8011
asked Jan 22 at 19:58
Michael MuntaMichael Munta
8011
asked Jan 22 at 19:58
Michael MuntaMichael Munta
8011
asked Jan 22 at 19:58
Michael MuntaMichael Munta
8011
asked Jan 22 at 19:58
Michael MuntaMichael Munta
8011
8011
$begingroup$
Indeed, even though $varphi(100)=40$ we have $2^{40}equiv 76pmod {100}$. Still, it's not hard to verify that $2^{42}equiv 4 pmod {100}$.
$endgroup$
– lulu
Jan 22 at 20:05
$begingroup$
I know it is easy to verify, but the point is not to use a calculator and I was trying to understand how can that be usage of Euler's theorem so I did not use CRT. So you agree it is an error?
$endgroup$
– Michael Munta
Jan 22 at 20:22
1
$begingroup$
Shouldn't need a calculator. $varphi(25)=20$ so $2^{40}equiv 1 pmod {25}$ so $2^{42}equiv 4pmod {25}$. Clearly $2^{42}equiv 0 pmod 4$ and the chinese remainder theorem immediately settles the point.
$endgroup$
– lulu
Jan 22 at 20:27
$begingroup$
Not sure I'd call what they wrote an error, though I'd agree it was unhelpfully terse. Euler's Theorem is the way to go here. You just have to realize that you should apply it to $25$, not $100$.
$endgroup$
– lulu
Jan 22 at 20:28
add a comment |
$begingroup$
Indeed, even though $varphi(100)=40$ we have $2^{40}equiv 76pmod {100}$. Still, it's not hard to verify that $2^{42}equiv 4 pmod {100}$.
$endgroup$
– lulu
Jan 22 at 20:05
$begingroup$
I know it is easy to verify, but the point is not to use a calculator and I was trying to understand how can that be usage of Euler's theorem so I did not use CRT. So you agree it is an error?
$endgroup$
– Michael Munta
Jan 22 at 20:22
1
$begingroup$
Shouldn't need a calculator. $varphi(25)=20$ so $2^{40}equiv 1 pmod {25}$ so $2^{42}equiv 4pmod {25}$. Clearly $2^{42}equiv 0 pmod 4$ and the chinese remainder theorem immediately settles the point.
$endgroup$
– lulu
Jan 22 at 20:27
$begingroup$
Not sure I'd call what they wrote an error, though I'd agree it was unhelpfully terse. Euler's Theorem is the way to go here. You just have to realize that you should apply it to $25$, not $100$.
$endgroup$
– lulu
Jan 22 at 20:28
$begingroup$
Indeed, even though $varphi(100)=40$ we have $2^{40}equiv 76pmod {100}$. Still, it's not hard to verify that $2^{42}equiv 4 pmod {100}$.
$endgroup$
– lulu
Jan 22 at 20:05
$begingroup$
Indeed, even though $varphi(100)=40$ we have $2^{40}equiv 76pmod {100}$. Still, it's not hard to verify that $2^{42}equiv 4 pmod {100}$.
$endgroup$
– lulu
Jan 22 at 20:05
$begingroup$
I know it is easy to verify, but the point is not to use a calculator and I was trying to understand how can that be usage of Euler's theorem so I did not use CRT. So you agree it is an error?
$endgroup$
– Michael Munta
Jan 22 at 20:22
$begingroup$
I know it is easy to verify, but the point is not to use a calculator and I was trying to understand how can that be usage of Euler's theorem so I did not use CRT. So you agree it is an error?
$endgroup$
– Michael Munta
Jan 22 at 20:22
1
1
$begingroup$
Shouldn't need a calculator. $varphi(25)=20$ so $2^{40}equiv 1 pmod {25}$ so $2^{42}equiv 4pmod {25}$. Clearly $2^{42}equiv 0 pmod 4$ and the chinese remainder theorem immediately settles the point.
$endgroup$
– lulu
Jan 22 at 20:27
$begingroup$
Shouldn't need a calculator. $varphi(25)=20$ so $2^{40}equiv 1 pmod {25}$ so $2^{42}equiv 4pmod {25}$. Clearly $2^{42}equiv 0 pmod 4$ and the chinese remainder theorem immediately settles the point.
$endgroup$
– lulu
Jan 22 at 20:27
$begingroup$
Not sure I'd call what they wrote an error, though I'd agree it was unhelpfully terse. Euler's Theorem is the way to go here. You just have to realize that you should apply it to $25$, not $100$.
$endgroup$
– lulu
Jan 22 at 20:28
$begingroup$
Not sure I'd call what they wrote an error, though I'd agree it was unhelpfully terse. Euler's Theorem is the way to go here. You just have to realize that you should apply it to $25$, not $100$.
$endgroup$
– lulu
Jan 22 at 20:28
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
$100 = 2^2 cdot 5^2$, so any value mod $100$ depends on that value mod $2^2$ and mod $5^2$. Mod $2^2$ is easy: $2^j equiv 0 mod 2^2$ if $j ge 2$. Mod $5^2$ you use Euler.
answered Jan 22 at 20:05
Robert IsraelRobert Israel
327k23216469
$endgroup$
$begingroup$
Yes, I did not see that. It is confusing because in the article the author does not show this and says that Euler's theorem was used which I think is an incorrect usage because $2$ and $100$ are not coprime.
$endgroup$
– Michael Munta
Jan 22 at 20:13
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%2f3083634%2flast-digit-of-power-explanation%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$
$100 = 2^2 cdot 5^2$, so any value mod $100$ depends on that value mod $2^2$ and mod $5^2$. Mod $2^2$ is easy: $2^j equiv 0 mod 2^2$ if $j ge 2$. Mod $5^2$ you use Euler.
answered Jan 22 at 20:05
Robert IsraelRobert Israel
327k23216469
$endgroup$
$begingroup$
Yes, I did not see that. It is confusing because in the article the author does not show this and says that Euler's theorem was used which I think is an incorrect usage because $2$ and $100$ are not coprime.
$endgroup$
– Michael Munta
Jan 22 at 20:13
add a comment |
$begingroup$
$100 = 2^2 cdot 5^2$, so any value mod $100$ depends on that value mod $2^2$ and mod $5^2$. Mod $2^2$ is easy: $2^j equiv 0 mod 2^2$ if $j ge 2$. Mod $5^2$ you use Euler.
answered Jan 22 at 20:05
Robert IsraelRobert Israel
327k23216469
$endgroup$
$begingroup$
Yes, I did not see that. It is confusing because in the article the author does not show this and says that Euler's theorem was used which I think is an incorrect usage because $2$ and $100$ are not coprime.
$endgroup$
– Michael Munta
Jan 22 at 20:13
add a comment |
$begingroup$
$100 = 2^2 cdot 5^2$, so any value mod $100$ depends on that value mod $2^2$ and mod $5^2$. Mod $2^2$ is easy: $2^j equiv 0 mod 2^2$ if $j ge 2$. Mod $5^2$ you use Euler.
answered Jan 22 at 20:05
Robert IsraelRobert Israel
327k23216469
$endgroup$
$100 = 2^2 cdot 5^2$, so any value mod $100$ depends on that value mod $2^2$ and mod $5^2$. Mod $2^2$ is easy: $2^j equiv 0 mod 2^2$ if $j ge 2$. Mod $5^2$ you use Euler.
answered Jan 22 at 20:05
Robert IsraelRobert Israel
327k23216469
answered Jan 22 at 20:05
Robert IsraelRobert Israel
327k23216469
answered Jan 22 at 20:05
Robert IsraelRobert Israel
327k23216469
answered Jan 22 at 20:05
Robert IsraelRobert Israel
327k23216469
327k23216469
$begingroup$
Yes, I did not see that. It is confusing because in the article the author does not show this and says that Euler's theorem was used which I think is an incorrect usage because $2$ and $100$ are not coprime.
$endgroup$
– Michael Munta
Jan 22 at 20:13
add a comment |
$begingroup$
Yes, I did not see that. It is confusing because in the article the author does not show this and says that Euler's theorem was used which I think is an incorrect usage because $2$ and $100$ are not coprime.
$endgroup$
– Michael Munta
Jan 22 at 20:13
$begingroup$
Yes, I did not see that. It is confusing because in the article the author does not show this and says that Euler's theorem was used which I think is an incorrect usage because $2$ and $100$ are not coprime.
$endgroup$
– Michael Munta
Jan 22 at 20:13
$begingroup$
Yes, I did not see that. It is confusing because in the article the author does not show this and says that Euler's theorem was used which I think is an incorrect usage because $2$ and $100$ are not coprime.
$endgroup$
– Michael Munta
Jan 22 at 20:13
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%2f3083634%2flast-digit-of-power-explanation%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$
Indeed, even though $varphi(100)=40$ we have $2^{40}equiv 76pmod {100}$. Still, it's not hard to verify that $2^{42}equiv 4 pmod {100}$.
$endgroup$
– lulu
Jan 22 at 20:05
$begingroup$
I know it is easy to verify, but the point is not to use a calculator and I was trying to understand how can that be usage of Euler's theorem so I did not use CRT. So you agree it is an error?
$endgroup$
– Michael Munta
Jan 22 at 20:22
1
$begingroup$
Shouldn't need a calculator. $varphi(25)=20$ so $2^{40}equiv 1 pmod {25}$ so $2^{42}equiv 4pmod {25}$. Clearly $2^{42}equiv 0 pmod 4$ and the chinese remainder theorem immediately settles the point.
$endgroup$
– lulu
Jan 22 at 20:27
$begingroup$
Not sure I'd call what they wrote an error, though I'd agree it was unhelpfully terse. Euler's Theorem is the way to go here. You just have to realize that you should apply it to $25$, not $100$.
$endgroup$
– lulu
Jan 22 at 20:28