Mixing
What is $26^{32}bmod 12$?
$begingroup$
What is the correct answer to this expression:
$26^{32} pmod {12}$
When I tried in Wolfram Alpha the answer is $4$, this is also my answer using Fermat's little theorem, but in a calculator the answer is different, $0.$
modular-arithmetic
edited Oct 27 '18 at 19:41
David Richerby
2,25511324
asked Oct 27 '18 at 9:34
Naruto UzumakiNaruto Uzumaki
235
$endgroup$
|
show 3 more comments
$begingroup$
What is the correct answer to this expression:
$26^{32} pmod {12}$
When I tried in Wolfram Alpha the answer is $4$, this is also my answer using Fermat's little theorem, but in a calculator the answer is different, $0.$
modular-arithmetic
edited Oct 27 '18 at 19:41
David Richerby
2,25511324
asked Oct 27 '18 at 9:34
Naruto UzumakiNaruto Uzumaki
235
$endgroup$
7
$begingroup$
How can it be $0$? $3$ does not divide $26$, so $12 (= 3 times 4)$ can't divide $26^{32}$
$endgroup$
– ab123
Oct 27 '18 at 9:39
1
$begingroup$
So the answer 4 is correct?
$endgroup$
– Naruto Uzumaki
Oct 27 '18 at 9:43
1
$begingroup$
yes the answer $4$ is correct
$endgroup$
– ab123
Oct 27 '18 at 9:46
4
$begingroup$
I would suggest that, depending on exactly how you did this on a calculator, at some stage the calculator encountered a very large exponent and truncated the result, throwing off the rest of the calculation.
$endgroup$
– Sam Streeter
Oct 27 '18 at 9:51
$begingroup$
Alpha failing on such a "basic" computation is more than unlikely. Even the Windows calculator returns $4$ ! (by chance ?)
$endgroup$
– Yves Daoust
Oct 27 '18 at 11:03
|
show 3 more comments
$begingroup$
What is the correct answer to this expression:
$26^{32} pmod {12}$
When I tried in Wolfram Alpha the answer is $4$, this is also my answer using Fermat's little theorem, but in a calculator the answer is different, $0.$
modular-arithmetic
edited Oct 27 '18 at 19:41
David Richerby
2,25511324
asked Oct 27 '18 at 9:34
Naruto UzumakiNaruto Uzumaki
235
$endgroup$
What is the correct answer to this expression:
$26^{32} pmod {12}$
When I tried in Wolfram Alpha the answer is $4$, this is also my answer using Fermat's little theorem, but in a calculator the answer is different, $0.$
modular-arithmetic
modular-arithmetic
edited Oct 27 '18 at 19:41
David Richerby
2,25511324
asked Oct 27 '18 at 9:34
Naruto UzumakiNaruto Uzumaki
235
edited Oct 27 '18 at 19:41
David Richerby
2,25511324
asked Oct 27 '18 at 9:34
Naruto UzumakiNaruto Uzumaki
235
edited Oct 27 '18 at 19:41
David Richerby
2,25511324
edited Oct 27 '18 at 19:41
David Richerby
2,25511324
edited Oct 27 '18 at 19:41
David Richerby
2,25511324
2,25511324
asked Oct 27 '18 at 9:34
Naruto UzumakiNaruto Uzumaki
235
asked Oct 27 '18 at 9:34
Naruto UzumakiNaruto Uzumaki
235
asked Oct 27 '18 at 9:34
Naruto UzumakiNaruto Uzumaki
235
235
7
$begingroup$
How can it be $0$? $3$ does not divide $26$, so $12 (= 3 times 4)$ can't divide $26^{32}$
$endgroup$
– ab123
Oct 27 '18 at 9:39
1
$begingroup$
So the answer 4 is correct?
$endgroup$
– Naruto Uzumaki
Oct 27 '18 at 9:43
1
$begingroup$
yes the answer $4$ is correct
$endgroup$
– ab123
Oct 27 '18 at 9:46
4
$begingroup$
I would suggest that, depending on exactly how you did this on a calculator, at some stage the calculator encountered a very large exponent and truncated the result, throwing off the rest of the calculation.
$endgroup$
– Sam Streeter
Oct 27 '18 at 9:51
$begingroup$
Alpha failing on such a "basic" computation is more than unlikely. Even the Windows calculator returns $4$ ! (by chance ?)
$endgroup$
– Yves Daoust
Oct 27 '18 at 11:03
|
show 3 more comments
7
$begingroup$
How can it be $0$? $3$ does not divide $26$, so $12 (= 3 times 4)$ can't divide $26^{32}$
$endgroup$
– ab123
Oct 27 '18 at 9:39
1
$begingroup$
So the answer 4 is correct?
$endgroup$
– Naruto Uzumaki
Oct 27 '18 at 9:43
1
$begingroup$
yes the answer $4$ is correct
$endgroup$
– ab123
Oct 27 '18 at 9:46
4
$begingroup$
I would suggest that, depending on exactly how you did this on a calculator, at some stage the calculator encountered a very large exponent and truncated the result, throwing off the rest of the calculation.
$endgroup$
– Sam Streeter
Oct 27 '18 at 9:51
$begingroup$
Alpha failing on such a "basic" computation is more than unlikely. Even the Windows calculator returns $4$ ! (by chance ?)
$endgroup$
– Yves Daoust
Oct 27 '18 at 11:03
7
7
$begingroup$
How can it be $0$? $3$ does not divide $26$, so $12 (= 3 times 4)$ can't divide $26^{32}$
$endgroup$
– ab123
Oct 27 '18 at 9:39
$begingroup$
How can it be $0$? $3$ does not divide $26$, so $12 (= 3 times 4)$ can't divide $26^{32}$
$endgroup$
– ab123
Oct 27 '18 at 9:39
1
1
$begingroup$
So the answer 4 is correct?
$endgroup$
– Naruto Uzumaki
Oct 27 '18 at 9:43
$begingroup$
So the answer 4 is correct?
$endgroup$
– Naruto Uzumaki
Oct 27 '18 at 9:43
1
1
$begingroup$
yes the answer $4$ is correct
$endgroup$
– ab123
Oct 27 '18 at 9:46
$begingroup$
yes the answer $4$ is correct
$endgroup$
– ab123
Oct 27 '18 at 9:46
4
4
$begingroup$
I would suggest that, depending on exactly how you did this on a calculator, at some stage the calculator encountered a very large exponent and truncated the result, throwing off the rest of the calculation.
$endgroup$
– Sam Streeter
Oct 27 '18 at 9:51
$begingroup$
I would suggest that, depending on exactly how you did this on a calculator, at some stage the calculator encountered a very large exponent and truncated the result, throwing off the rest of the calculation.
$endgroup$
– Sam Streeter
Oct 27 '18 at 9:51
$begingroup$
Alpha failing on such a "basic" computation is more than unlikely. Even the Windows calculator returns $4$ ! (by chance ?)
$endgroup$
– Yves Daoust
Oct 27 '18 at 11:03
$begingroup$
Alpha failing on such a "basic" computation is more than unlikely. Even the Windows calculator returns $4$ ! (by chance ?)
$endgroup$
– Yves Daoust
Oct 27 '18 at 11:03
|
show 3 more comments
5 Answers
5
active
oldest
votes
$begingroup$
First, note that $26 equiv 2 pmod {12}$, so $26^{32} equiv 2^{32} pmod {12}$.
Next, note that $2^4 equiv 16 equiv 4 pmod {12}$, so $2^{32} equiv left(2^4right)^8 equiv 4 ^8 pmod {12}$, and $4^2 equiv 4 pmod {12}$.
Finally, $4^8 equiv left(4^2right)^4 equiv 4^4 equiv left(4^2right)^2 equiv 4^2 equiv 4 pmod {12}$.
Then we get the result.
There are slicker solutions with just a few results from elementary number theory, but this is a very basic method which should be easy enough to follow.
answered Oct 27 '18 at 9:45
Sam StreeterSam Streeter
1,489418
$endgroup$
$begingroup$
I elaborated on the algebraic essence in my answer, since for beginners that may not be clear from above.
$endgroup$
– Bill Dubuque
Oct 29 '18 at 16:50
add a comment |
$begingroup$
Like
Get the last two digits of $16^{100}$ and $17^{100}$
How to find last two digits of $2^{2016}$
last two digits of $14^{5532}$?
Find the last two digits of $2^{2156789}$
$$26equiv-1pmod3$$
$implies26^{2n}equiv(-1)^{2n}equiv1pmod3$ where $n$ is any integer
$implies26^{2n+2}equiv1cdot26^2pmod{3cdot26^2}$
$implies26^{2n+2}equiv26^2pmod{3cdot2^2}equiv?$
answered Oct 27 '18 at 9:37
lab bhattacharjeelab bhattacharjee
228k15158279
$endgroup$
add a comment |
$begingroup$
Note that $26equiv 2pmod{12}$, so we can as well compute $r=2^{32}bmod 12$.
We have $2^{32}=12q+r$, so clearly $r=4s$, so we are reduced to compute $2^{30}bmod 3$ and now we can apply Fermat’s little theorem: $2^2equiv 1pmod 3$; thus $2^{30}equiv 1=spmod{3}$ and therefore $r=4$.
answered Oct 27 '18 at 10:29
egregegreg
185k1486208
$endgroup$
$begingroup$
Readers may be interested to know that this factoring out of $4$ can be done efficiently operationally using the mod distributive law (an operational reformulation of CRT) - see my answer.
$endgroup$
– Bill Dubuque
Oct 27 '18 at 18:50
add a comment |
$begingroup$
$smash[b]{text{Note that } overbrace{color{#0a0}{26}^{large 32}!bmod 12
= color{#0a0}2^{large 32}!bmod{12}}^{Large color{#0a0}{26 equiv 2}pmod{!12}}
,=, 2^{large 2}overbrace{(color{#c00}2^{large 30}!bmod 3) = 4((color{#c00}{-1})^{large 30}!bmod 3)}^{Large color{#c00}{2 equiv -1}pmod{!3}} = 4}$
$smash[t]{text{The middle equality uses }, overbrace{ab bmod ac = a (,b bmod c)}}, =,$ mod Distributive Law.
Or $ $ we can notice that $,color{#c00}{4^{large n}equiv 4}pmod{!12},$ since it is true mod $3$ & $4!:$ $,1^{large n}!equiv 1,$ & $,0^{large n}!equiv 0$
So $bmod 12!: 26^{large 32}!equiv 2^{large 32}!equiv color{#c00}{4^{large 16}!equiv 4}. $ This is the idea behind Sam's answer.
Remark $ $ Numbers like $4$ above with $a^2=a$ are called idempotents. This implies $,a^{large n} = a,$ for all $nge 2$ either as above or by a simple induction $,a^{large n+1}! = a,a^{large n} = acdot a = a.,$ Said more conceptually: note $a$ is a fixed point of $,f(x) = ax,$ i.e. $,f(a) = a,,$ and fixed points always stay fixed on iteration by a simple induction: if $,color{#c00}{f^n(a) = a},$ then $,f^{large n+1}(a) = f(color{#c00}{f^{large n}(a)}) = f(color{#c00}a) = a$.
Idempotents $!bmod n$ play a fundament role in factorization of integers (and rings) since they correspond to splittings of $n$ into coprime factors, cf. last paragraph here,. However, the first method is more general since the base is generally not idempotent in such exponentiation problems (in fact the mod Distributive Law is essentially an operational form of CRT = Chinese Remainder Theorem - which yields a general way of solving this and related problems).
answered Oct 27 '18 at 18:29
Bill DubuqueBill Dubuque
214k29196655
$endgroup$
add a comment |
$begingroup$
Note that $26^{32}$ is clearly divisible by $4$ but not by $3$, so the possible congruence classes modulo $12$ are immediately only (represented by) $4$ and $8$. We have $4equiv 1 bmod 3$ and $8equiv 2 equiv -1 bmod 3$, so to distinguish between them we only need to know the answer modulo $3$.
This comes down to $(-1)^{32}=1$ (or we can use little Fermat to the same effect) and the answer is therefore $4$.
answered Oct 27 '18 at 10:50
Mark BennetMark Bennet
81.9k984183
$endgroup$
$begingroup$
Splitting the $12$ into the coprime factors $4$ and $3$ is a technique which is substantially generalised in the Chinese Remainder Theorem. The observations in this case are elementary and don't need complex machinery, but it is there if needed to steer the analysis of more complex cases.
$endgroup$
– Mark Bennet
Oct 27 '18 at 10:54
$begingroup$
This implicit factoring out of 4 can be explicitly achieved operationally using the mod distributive law (an operational reformulation of CRT) - see my answer.
$endgroup$
– Bill Dubuque
Oct 27 '18 at 19:07
$begingroup$
@BillDubuque A useful and interesting perspective as usual!
$endgroup$
– Mark Bennet
Oct 27 '18 at 20:51
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%2f2973194%2fwhat-is-2632-bmod-12%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$
First, note that $26 equiv 2 pmod {12}$, so $26^{32} equiv 2^{32} pmod {12}$.
Next, note that $2^4 equiv 16 equiv 4 pmod {12}$, so $2^{32} equiv left(2^4right)^8 equiv 4 ^8 pmod {12}$, and $4^2 equiv 4 pmod {12}$.
Finally, $4^8 equiv left(4^2right)^4 equiv 4^4 equiv left(4^2right)^2 equiv 4^2 equiv 4 pmod {12}$.
Then we get the result.
There are slicker solutions with just a few results from elementary number theory, but this is a very basic method which should be easy enough to follow.
answered Oct 27 '18 at 9:45
Sam StreeterSam Streeter
1,489418
$endgroup$
$begingroup$
I elaborated on the algebraic essence in my answer, since for beginners that may not be clear from above.
$endgroup$
– Bill Dubuque
Oct 29 '18 at 16:50
add a comment |
$begingroup$
First, note that $26 equiv 2 pmod {12}$, so $26^{32} equiv 2^{32} pmod {12}$.
Next, note that $2^4 equiv 16 equiv 4 pmod {12}$, so $2^{32} equiv left(2^4right)^8 equiv 4 ^8 pmod {12}$, and $4^2 equiv 4 pmod {12}$.
Finally, $4^8 equiv left(4^2right)^4 equiv 4^4 equiv left(4^2right)^2 equiv 4^2 equiv 4 pmod {12}$.
Then we get the result.
There are slicker solutions with just a few results from elementary number theory, but this is a very basic method which should be easy enough to follow.
answered Oct 27 '18 at 9:45
Sam StreeterSam Streeter
1,489418
$endgroup$
$begingroup$
I elaborated on the algebraic essence in my answer, since for beginners that may not be clear from above.
$endgroup$
– Bill Dubuque
Oct 29 '18 at 16:50
add a comment |
$begingroup$
First, note that $26 equiv 2 pmod {12}$, so $26^{32} equiv 2^{32} pmod {12}$.
Next, note that $2^4 equiv 16 equiv 4 pmod {12}$, so $2^{32} equiv left(2^4right)^8 equiv 4 ^8 pmod {12}$, and $4^2 equiv 4 pmod {12}$.
Finally, $4^8 equiv left(4^2right)^4 equiv 4^4 equiv left(4^2right)^2 equiv 4^2 equiv 4 pmod {12}$.
Then we get the result.
There are slicker solutions with just a few results from elementary number theory, but this is a very basic method which should be easy enough to follow.
answered Oct 27 '18 at 9:45
Sam StreeterSam Streeter
1,489418
$endgroup$
First, note that $26 equiv 2 pmod {12}$, so $26^{32} equiv 2^{32} pmod {12}$.
Next, note that $2^4 equiv 16 equiv 4 pmod {12}$, so $2^{32} equiv left(2^4right)^8 equiv 4 ^8 pmod {12}$, and $4^2 equiv 4 pmod {12}$.
Finally, $4^8 equiv left(4^2right)^4 equiv 4^4 equiv left(4^2right)^2 equiv 4^2 equiv 4 pmod {12}$.
Then we get the result.
There are slicker solutions with just a few results from elementary number theory, but this is a very basic method which should be easy enough to follow.
answered Oct 27 '18 at 9:45
Sam StreeterSam Streeter
1,489418
edited Oct 27 '18 at 20:24
answered Oct 27 '18 at 9:45
Sam StreeterSam Streeter
1,489418
answered Oct 27 '18 at 9:45
Sam StreeterSam Streeter
1,489418
answered Oct 27 '18 at 9:45
Sam StreeterSam Streeter
1,489418
1,489418
$begingroup$
I elaborated on the algebraic essence in my answer, since for beginners that may not be clear from above.
$endgroup$
– Bill Dubuque
Oct 29 '18 at 16:50
add a comment |
$begingroup$
I elaborated on the algebraic essence in my answer, since for beginners that may not be clear from above.
$endgroup$
– Bill Dubuque
Oct 29 '18 at 16:50
$begingroup$
I elaborated on the algebraic essence in my answer, since for beginners that may not be clear from above.
$endgroup$
– Bill Dubuque
Oct 29 '18 at 16:50
$begingroup$
I elaborated on the algebraic essence in my answer, since for beginners that may not be clear from above.
$endgroup$
– Bill Dubuque
Oct 29 '18 at 16:50
add a comment |
$begingroup$
Like
Get the last two digits of $16^{100}$ and $17^{100}$
How to find last two digits of $2^{2016}$
last two digits of $14^{5532}$?
Find the last two digits of $2^{2156789}$
$$26equiv-1pmod3$$
$implies26^{2n}equiv(-1)^{2n}equiv1pmod3$ where $n$ is any integer
$implies26^{2n+2}equiv1cdot26^2pmod{3cdot26^2}$
$implies26^{2n+2}equiv26^2pmod{3cdot2^2}equiv?$
answered Oct 27 '18 at 9:37
lab bhattacharjeelab bhattacharjee
228k15158279
$endgroup$
add a comment |
$begingroup$
Like
Get the last two digits of $16^{100}$ and $17^{100}$
How to find last two digits of $2^{2016}$
last two digits of $14^{5532}$?
Find the last two digits of $2^{2156789}$
$$26equiv-1pmod3$$
$implies26^{2n}equiv(-1)^{2n}equiv1pmod3$ where $n$ is any integer
$implies26^{2n+2}equiv1cdot26^2pmod{3cdot26^2}$
$implies26^{2n+2}equiv26^2pmod{3cdot2^2}equiv?$
answered Oct 27 '18 at 9:37
lab bhattacharjeelab bhattacharjee
228k15158279
$endgroup$
add a comment |
$begingroup$
Like
Get the last two digits of $16^{100}$ and $17^{100}$
How to find last two digits of $2^{2016}$
last two digits of $14^{5532}$?
Find the last two digits of $2^{2156789}$
$$26equiv-1pmod3$$
$implies26^{2n}equiv(-1)^{2n}equiv1pmod3$ where $n$ is any integer
$implies26^{2n+2}equiv1cdot26^2pmod{3cdot26^2}$
$implies26^{2n+2}equiv26^2pmod{3cdot2^2}equiv?$
answered Oct 27 '18 at 9:37
lab bhattacharjeelab bhattacharjee
228k15158279
$endgroup$
Like
Get the last two digits of $16^{100}$ and $17^{100}$
How to find last two digits of $2^{2016}$
last two digits of $14^{5532}$?
Find the last two digits of $2^{2156789}$
$$26equiv-1pmod3$$
$implies26^{2n}equiv(-1)^{2n}equiv1pmod3$ where $n$ is any integer
$implies26^{2n+2}equiv1cdot26^2pmod{3cdot26^2}$
$implies26^{2n+2}equiv26^2pmod{3cdot2^2}equiv?$
answered Oct 27 '18 at 9:37
lab bhattacharjeelab bhattacharjee
228k15158279
answered Oct 27 '18 at 9:37
lab bhattacharjeelab bhattacharjee
228k15158279
answered Oct 27 '18 at 9:37
lab bhattacharjeelab bhattacharjee
228k15158279
answered Oct 27 '18 at 9:37
lab bhattacharjeelab bhattacharjee
228k15158279
228k15158279
add a comment |
add a comment |
$begingroup$
Note that $26equiv 2pmod{12}$, so we can as well compute $r=2^{32}bmod 12$.
We have $2^{32}=12q+r$, so clearly $r=4s$, so we are reduced to compute $2^{30}bmod 3$ and now we can apply Fermat’s little theorem: $2^2equiv 1pmod 3$; thus $2^{30}equiv 1=spmod{3}$ and therefore $r=4$.
answered Oct 27 '18 at 10:29
egregegreg
185k1486208
$endgroup$
$begingroup$
Readers may be interested to know that this factoring out of $4$ can be done efficiently operationally using the mod distributive law (an operational reformulation of CRT) - see my answer.
$endgroup$
– Bill Dubuque
Oct 27 '18 at 18:50
add a comment |
$begingroup$
Note that $26equiv 2pmod{12}$, so we can as well compute $r=2^{32}bmod 12$.
We have $2^{32}=12q+r$, so clearly $r=4s$, so we are reduced to compute $2^{30}bmod 3$ and now we can apply Fermat’s little theorem: $2^2equiv 1pmod 3$; thus $2^{30}equiv 1=spmod{3}$ and therefore $r=4$.
answered Oct 27 '18 at 10:29
egregegreg
185k1486208
$endgroup$
$begingroup$
Readers may be interested to know that this factoring out of $4$ can be done efficiently operationally using the mod distributive law (an operational reformulation of CRT) - see my answer.
$endgroup$
– Bill Dubuque
Oct 27 '18 at 18:50
add a comment |
$begingroup$
Note that $26equiv 2pmod{12}$, so we can as well compute $r=2^{32}bmod 12$.
We have $2^{32}=12q+r$, so clearly $r=4s$, so we are reduced to compute $2^{30}bmod 3$ and now we can apply Fermat’s little theorem: $2^2equiv 1pmod 3$; thus $2^{30}equiv 1=spmod{3}$ and therefore $r=4$.
answered Oct 27 '18 at 10:29
egregegreg
185k1486208
$endgroup$
Note that $26equiv 2pmod{12}$, so we can as well compute $r=2^{32}bmod 12$.
We have $2^{32}=12q+r$, so clearly $r=4s$, so we are reduced to compute $2^{30}bmod 3$ and now we can apply Fermat’s little theorem: $2^2equiv 1pmod 3$; thus $2^{30}equiv 1=spmod{3}$ and therefore $r=4$.
answered Oct 27 '18 at 10:29
egregegreg
185k1486208
answered Oct 27 '18 at 10:29
egregegreg
185k1486208
answered Oct 27 '18 at 10:29
egregegreg
185k1486208
answered Oct 27 '18 at 10:29
egregegreg
185k1486208
185k1486208
$begingroup$
Readers may be interested to know that this factoring out of $4$ can be done efficiently operationally using the mod distributive law (an operational reformulation of CRT) - see my answer.
$endgroup$
– Bill Dubuque
Oct 27 '18 at 18:50
add a comment |
$begingroup$
Readers may be interested to know that this factoring out of $4$ can be done efficiently operationally using the mod distributive law (an operational reformulation of CRT) - see my answer.
$endgroup$
– Bill Dubuque
Oct 27 '18 at 18:50
$begingroup$
Readers may be interested to know that this factoring out of $4$ can be done efficiently operationally using the mod distributive law (an operational reformulation of CRT) - see my answer.
$endgroup$
– Bill Dubuque
Oct 27 '18 at 18:50
$begingroup$
Readers may be interested to know that this factoring out of $4$ can be done efficiently operationally using the mod distributive law (an operational reformulation of CRT) - see my answer.
$endgroup$
– Bill Dubuque
Oct 27 '18 at 18:50
add a comment |
$begingroup$
$smash[b]{text{Note that } overbrace{color{#0a0}{26}^{large 32}!bmod 12
= color{#0a0}2^{large 32}!bmod{12}}^{Large color{#0a0}{26 equiv 2}pmod{!12}}
,=, 2^{large 2}overbrace{(color{#c00}2^{large 30}!bmod 3) = 4((color{#c00}{-1})^{large 30}!bmod 3)}^{Large color{#c00}{2 equiv -1}pmod{!3}} = 4}$
$smash[t]{text{The middle equality uses }, overbrace{ab bmod ac = a (,b bmod c)}}, =,$ mod Distributive Law.
Or $ $ we can notice that $,color{#c00}{4^{large n}equiv 4}pmod{!12},$ since it is true mod $3$ & $4!:$ $,1^{large n}!equiv 1,$ & $,0^{large n}!equiv 0$
So $bmod 12!: 26^{large 32}!equiv 2^{large 32}!equiv color{#c00}{4^{large 16}!equiv 4}. $ This is the idea behind Sam's answer.
Remark $ $ Numbers like $4$ above with $a^2=a$ are called idempotents. This implies $,a^{large n} = a,$ for all $nge 2$ either as above or by a simple induction $,a^{large n+1}! = a,a^{large n} = acdot a = a.,$ Said more conceptually: note $a$ is a fixed point of $,f(x) = ax,$ i.e. $,f(a) = a,,$ and fixed points always stay fixed on iteration by a simple induction: if $,color{#c00}{f^n(a) = a},$ then $,f^{large n+1}(a) = f(color{#c00}{f^{large n}(a)}) = f(color{#c00}a) = a$.
Idempotents $!bmod n$ play a fundament role in factorization of integers (and rings) since they correspond to splittings of $n$ into coprime factors, cf. last paragraph here,. However, the first method is more general since the base is generally not idempotent in such exponentiation problems (in fact the mod Distributive Law is essentially an operational form of CRT = Chinese Remainder Theorem - which yields a general way of solving this and related problems).
answered Oct 27 '18 at 18:29
Bill DubuqueBill Dubuque
214k29196655
$endgroup$
add a comment |
$begingroup$
$smash[b]{text{Note that } overbrace{color{#0a0}{26}^{large 32}!bmod 12
= color{#0a0}2^{large 32}!bmod{12}}^{Large color{#0a0}{26 equiv 2}pmod{!12}}
,=, 2^{large 2}overbrace{(color{#c00}2^{large 30}!bmod 3) = 4((color{#c00}{-1})^{large 30}!bmod 3)}^{Large color{#c00}{2 equiv -1}pmod{!3}} = 4}$
$smash[t]{text{The middle equality uses }, overbrace{ab bmod ac = a (,b bmod c)}}, =,$ mod Distributive Law.
Or $ $ we can notice that $,color{#c00}{4^{large n}equiv 4}pmod{!12},$ since it is true mod $3$ & $4!:$ $,1^{large n}!equiv 1,$ & $,0^{large n}!equiv 0$
So $bmod 12!: 26^{large 32}!equiv 2^{large 32}!equiv color{#c00}{4^{large 16}!equiv 4}. $ This is the idea behind Sam's answer.
Remark $ $ Numbers like $4$ above with $a^2=a$ are called idempotents. This implies $,a^{large n} = a,$ for all $nge 2$ either as above or by a simple induction $,a^{large n+1}! = a,a^{large n} = acdot a = a.,$ Said more conceptually: note $a$ is a fixed point of $,f(x) = ax,$ i.e. $,f(a) = a,,$ and fixed points always stay fixed on iteration by a simple induction: if $,color{#c00}{f^n(a) = a},$ then $,f^{large n+1}(a) = f(color{#c00}{f^{large n}(a)}) = f(color{#c00}a) = a$.
Idempotents $!bmod n$ play a fundament role in factorization of integers (and rings) since they correspond to splittings of $n$ into coprime factors, cf. last paragraph here,. However, the first method is more general since the base is generally not idempotent in such exponentiation problems (in fact the mod Distributive Law is essentially an operational form of CRT = Chinese Remainder Theorem - which yields a general way of solving this and related problems).
answered Oct 27 '18 at 18:29
Bill DubuqueBill Dubuque
214k29196655
$endgroup$
add a comment |
$begingroup$
$smash[b]{text{Note that } overbrace{color{#0a0}{26}^{large 32}!bmod 12
= color{#0a0}2^{large 32}!bmod{12}}^{Large color{#0a0}{26 equiv 2}pmod{!12}}
,=, 2^{large 2}overbrace{(color{#c00}2^{large 30}!bmod 3) = 4((color{#c00}{-1})^{large 30}!bmod 3)}^{Large color{#c00}{2 equiv -1}pmod{!3}} = 4}$
$smash[t]{text{The middle equality uses }, overbrace{ab bmod ac = a (,b bmod c)}}, =,$ mod Distributive Law.
Or $ $ we can notice that $,color{#c00}{4^{large n}equiv 4}pmod{!12},$ since it is true mod $3$ & $4!:$ $,1^{large n}!equiv 1,$ & $,0^{large n}!equiv 0$
So $bmod 12!: 26^{large 32}!equiv 2^{large 32}!equiv color{#c00}{4^{large 16}!equiv 4}. $ This is the idea behind Sam's answer.
Remark $ $ Numbers like $4$ above with $a^2=a$ are called idempotents. This implies $,a^{large n} = a,$ for all $nge 2$ either as above or by a simple induction $,a^{large n+1}! = a,a^{large n} = acdot a = a.,$ Said more conceptually: note $a$ is a fixed point of $,f(x) = ax,$ i.e. $,f(a) = a,,$ and fixed points always stay fixed on iteration by a simple induction: if $,color{#c00}{f^n(a) = a},$ then $,f^{large n+1}(a) = f(color{#c00}{f^{large n}(a)}) = f(color{#c00}a) = a$.
Idempotents $!bmod n$ play a fundament role in factorization of integers (and rings) since they correspond to splittings of $n$ into coprime factors, cf. last paragraph here,. However, the first method is more general since the base is generally not idempotent in such exponentiation problems (in fact the mod Distributive Law is essentially an operational form of CRT = Chinese Remainder Theorem - which yields a general way of solving this and related problems).
answered Oct 27 '18 at 18:29
Bill DubuqueBill Dubuque
214k29196655
$endgroup$
$smash[b]{text{Note that } overbrace{color{#0a0}{26}^{large 32}!bmod 12
= color{#0a0}2^{large 32}!bmod{12}}^{Large color{#0a0}{26 equiv 2}pmod{!12}}
,=, 2^{large 2}overbrace{(color{#c00}2^{large 30}!bmod 3) = 4((color{#c00}{-1})^{large 30}!bmod 3)}^{Large color{#c00}{2 equiv -1}pmod{!3}} = 4}$
$smash[t]{text{The middle equality uses }, overbrace{ab bmod ac = a (,b bmod c)}}, =,$ mod Distributive Law.
Or $ $ we can notice that $,color{#c00}{4^{large n}equiv 4}pmod{!12},$ since it is true mod $3$ & $4!:$ $,1^{large n}!equiv 1,$ & $,0^{large n}!equiv 0$
So $bmod 12!: 26^{large 32}!equiv 2^{large 32}!equiv color{#c00}{4^{large 16}!equiv 4}. $ This is the idea behind Sam's answer.
Remark $ $ Numbers like $4$ above with $a^2=a$ are called idempotents. This implies $,a^{large n} = a,$ for all $nge 2$ either as above or by a simple induction $,a^{large n+1}! = a,a^{large n} = acdot a = a.,$ Said more conceptually: note $a$ is a fixed point of $,f(x) = ax,$ i.e. $,f(a) = a,,$ and fixed points always stay fixed on iteration by a simple induction: if $,color{#c00}{f^n(a) = a},$ then $,f^{large n+1}(a) = f(color{#c00}{f^{large n}(a)}) = f(color{#c00}a) = a$.
Idempotents $!bmod n$ play a fundament role in factorization of integers (and rings) since they correspond to splittings of $n$ into coprime factors, cf. last paragraph here,. However, the first method is more general since the base is generally not idempotent in such exponentiation problems (in fact the mod Distributive Law is essentially an operational form of CRT = Chinese Remainder Theorem - which yields a general way of solving this and related problems).
answered Oct 27 '18 at 18:29
Bill DubuqueBill Dubuque
214k29196655
edited Apr 1 at 16:57
answered Oct 27 '18 at 18:29
Bill DubuqueBill Dubuque
214k29196655
answered Oct 27 '18 at 18:29
Bill DubuqueBill Dubuque
214k29196655
answered Oct 27 '18 at 18:29
Bill DubuqueBill Dubuque
214k29196655
214k29196655
add a comment |
add a comment |
$begingroup$
Note that $26^{32}$ is clearly divisible by $4$ but not by $3$, so the possible congruence classes modulo $12$ are immediately only (represented by) $4$ and $8$. We have $4equiv 1 bmod 3$ and $8equiv 2 equiv -1 bmod 3$, so to distinguish between them we only need to know the answer modulo $3$.
This comes down to $(-1)^{32}=1$ (or we can use little Fermat to the same effect) and the answer is therefore $4$.
answered Oct 27 '18 at 10:50
Mark BennetMark Bennet
81.9k984183
$endgroup$
$begingroup$
Splitting the $12$ into the coprime factors $4$ and $3$ is a technique which is substantially generalised in the Chinese Remainder Theorem. The observations in this case are elementary and don't need complex machinery, but it is there if needed to steer the analysis of more complex cases.
$endgroup$
– Mark Bennet
Oct 27 '18 at 10:54
$begingroup$
This implicit factoring out of 4 can be explicitly achieved operationally using the mod distributive law (an operational reformulation of CRT) - see my answer.
$endgroup$
– Bill Dubuque
Oct 27 '18 at 19:07
$begingroup$
@BillDubuque A useful and interesting perspective as usual!
$endgroup$
– Mark Bennet
Oct 27 '18 at 20:51
add a comment |
$begingroup$
Note that $26^{32}$ is clearly divisible by $4$ but not by $3$, so the possible congruence classes modulo $12$ are immediately only (represented by) $4$ and $8$. We have $4equiv 1 bmod 3$ and $8equiv 2 equiv -1 bmod 3$, so to distinguish between them we only need to know the answer modulo $3$.
This comes down to $(-1)^{32}=1$ (or we can use little Fermat to the same effect) and the answer is therefore $4$.
answered Oct 27 '18 at 10:50
Mark BennetMark Bennet
81.9k984183
$endgroup$
$begingroup$
Splitting the $12$ into the coprime factors $4$ and $3$ is a technique which is substantially generalised in the Chinese Remainder Theorem. The observations in this case are elementary and don't need complex machinery, but it is there if needed to steer the analysis of more complex cases.
$endgroup$
– Mark Bennet
Oct 27 '18 at 10:54
$begingroup$
This implicit factoring out of 4 can be explicitly achieved operationally using the mod distributive law (an operational reformulation of CRT) - see my answer.
$endgroup$
– Bill Dubuque
Oct 27 '18 at 19:07
$begingroup$
@BillDubuque A useful and interesting perspective as usual!
$endgroup$
– Mark Bennet
Oct 27 '18 at 20:51
add a comment |
$begingroup$
Note that $26^{32}$ is clearly divisible by $4$ but not by $3$, so the possible congruence classes modulo $12$ are immediately only (represented by) $4$ and $8$. We have $4equiv 1 bmod 3$ and $8equiv 2 equiv -1 bmod 3$, so to distinguish between them we only need to know the answer modulo $3$.
This comes down to $(-1)^{32}=1$ (or we can use little Fermat to the same effect) and the answer is therefore $4$.
answered Oct 27 '18 at 10:50
Mark BennetMark Bennet
81.9k984183
$endgroup$
Note that $26^{32}$ is clearly divisible by $4$ but not by $3$, so the possible congruence classes modulo $12$ are immediately only (represented by) $4$ and $8$. We have $4equiv 1 bmod 3$ and $8equiv 2 equiv -1 bmod 3$, so to distinguish between them we only need to know the answer modulo $3$.
This comes down to $(-1)^{32}=1$ (or we can use little Fermat to the same effect) and the answer is therefore $4$.
answered Oct 27 '18 at 10:50
Mark BennetMark Bennet
81.9k984183
answered Oct 27 '18 at 10:50
Mark BennetMark Bennet
81.9k984183
answered Oct 27 '18 at 10:50
Mark BennetMark Bennet
81.9k984183
answered Oct 27 '18 at 10:50
Mark BennetMark Bennet
81.9k984183
81.9k984183
$begingroup$
Splitting the $12$ into the coprime factors $4$ and $3$ is a technique which is substantially generalised in the Chinese Remainder Theorem. The observations in this case are elementary and don't need complex machinery, but it is there if needed to steer the analysis of more complex cases.
$endgroup$
– Mark Bennet
Oct 27 '18 at 10:54
$begingroup$
This implicit factoring out of 4 can be explicitly achieved operationally using the mod distributive law (an operational reformulation of CRT) - see my answer.
$endgroup$
– Bill Dubuque
Oct 27 '18 at 19:07
$begingroup$
@BillDubuque A useful and interesting perspective as usual!
$endgroup$
– Mark Bennet
Oct 27 '18 at 20:51
add a comment |
$begingroup$
Splitting the $12$ into the coprime factors $4$ and $3$ is a technique which is substantially generalised in the Chinese Remainder Theorem. The observations in this case are elementary and don't need complex machinery, but it is there if needed to steer the analysis of more complex cases.
$endgroup$
– Mark Bennet
Oct 27 '18 at 10:54
$begingroup$
This implicit factoring out of 4 can be explicitly achieved operationally using the mod distributive law (an operational reformulation of CRT) - see my answer.
$endgroup$
– Bill Dubuque
Oct 27 '18 at 19:07
$begingroup$
@BillDubuque A useful and interesting perspective as usual!
$endgroup$
– Mark Bennet
Oct 27 '18 at 20:51
$begingroup$
Splitting the $12$ into the coprime factors $4$ and $3$ is a technique which is substantially generalised in the Chinese Remainder Theorem. The observations in this case are elementary and don't need complex machinery, but it is there if needed to steer the analysis of more complex cases.
$endgroup$
– Mark Bennet
Oct 27 '18 at 10:54
$begingroup$
Splitting the $12$ into the coprime factors $4$ and $3$ is a technique which is substantially generalised in the Chinese Remainder Theorem. The observations in this case are elementary and don't need complex machinery, but it is there if needed to steer the analysis of more complex cases.
$endgroup$
– Mark Bennet
Oct 27 '18 at 10:54
$begingroup$
This implicit factoring out of 4 can be explicitly achieved operationally using the mod distributive law (an operational reformulation of CRT) - see my answer.
$endgroup$
– Bill Dubuque
Oct 27 '18 at 19:07
$begingroup$
This implicit factoring out of 4 can be explicitly achieved operationally using the mod distributive law (an operational reformulation of CRT) - see my answer.
$endgroup$
– Bill Dubuque
Oct 27 '18 at 19:07
$begingroup$
@BillDubuque A useful and interesting perspective as usual!
$endgroup$
– Mark Bennet
Oct 27 '18 at 20:51
$begingroup$
@BillDubuque A useful and interesting perspective as usual!
$endgroup$
– Mark Bennet
Oct 27 '18 at 20:51
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%2f2973194%2fwhat-is-2632-bmod-12%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
7
$begingroup$
How can it be $0$? $3$ does not divide $26$, so $12 (= 3 times 4)$ can't divide $26^{32}$
$endgroup$
– ab123
Oct 27 '18 at 9:39
1
$begingroup$
So the answer 4 is correct?
$endgroup$
– Naruto Uzumaki
Oct 27 '18 at 9:43
1
$begingroup$
yes the answer $4$ is correct
$endgroup$
– ab123
Oct 27 '18 at 9:46
4
$begingroup$
I would suggest that, depending on exactly how you did this on a calculator, at some stage the calculator encountered a very large exponent and truncated the result, throwing off the rest of the calculation.
$endgroup$
– Sam Streeter
Oct 27 '18 at 9:51
$begingroup$
Alpha failing on such a "basic" computation is more than unlikely. Even the Windows calculator returns $4$ ! (by chance ?)
$endgroup$
– Yves Daoust
Oct 27 '18 at 11:03