Correct answer to this modulo
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
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
add a comment |Â
up vote
2
down vote
favorite
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
3
How can it be $0$? $3$ does not divide $26$, so $12 (= 3 times 4)$ can't divide $26^32$
â ab123
1 hour ago
1
So the answer 4 is correct?
â Naruto Uzumaki
1 hour ago
1
yes the answer $4$ is correct
â ab123
1 hour ago
2
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.
â Sam Streeter
1 hour ago
Alpha failing on such a "basic" computation is more than unlikely. Even the Windows calculator returns $4$ ! (by chance ?)
â Yves Daoust
5 mins ago
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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
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 1 hour ago
amWhy
191k27223437
191k27223437
asked 1 hour ago
Naruto Uzumaki
185
185
3
How can it be $0$? $3$ does not divide $26$, so $12 (= 3 times 4)$ can't divide $26^32$
â ab123
1 hour ago
1
So the answer 4 is correct?
â Naruto Uzumaki
1 hour ago
1
yes the answer $4$ is correct
â ab123
1 hour ago
2
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.
â Sam Streeter
1 hour ago
Alpha failing on such a "basic" computation is more than unlikely. Even the Windows calculator returns $4$ ! (by chance ?)
â Yves Daoust
5 mins ago
add a comment |Â
3
How can it be $0$? $3$ does not divide $26$, so $12 (= 3 times 4)$ can't divide $26^32$
â ab123
1 hour ago
1
So the answer 4 is correct?
â Naruto Uzumaki
1 hour ago
1
yes the answer $4$ is correct
â ab123
1 hour ago
2
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.
â Sam Streeter
1 hour ago
Alpha failing on such a "basic" computation is more than unlikely. Even the Windows calculator returns $4$ ! (by chance ?)
â Yves Daoust
5 mins ago
3
3
How can it be $0$? $3$ does not divide $26$, so $12 (= 3 times 4)$ can't divide $26^32$
â ab123
1 hour ago
How can it be $0$? $3$ does not divide $26$, so $12 (= 3 times 4)$ can't divide $26^32$
â ab123
1 hour ago
1
1
So the answer 4 is correct?
â Naruto Uzumaki
1 hour ago
So the answer 4 is correct?
â Naruto Uzumaki
1 hour ago
1
1
yes the answer $4$ is correct
â ab123
1 hour ago
yes the answer $4$ is correct
â ab123
1 hour ago
2
2
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.
â Sam Streeter
1 hour ago
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.
â Sam Streeter
1 hour ago
Alpha failing on such a "basic" computation is more than unlikely. Even the Windows calculator returns $4$ ! (by chance ?)
â Yves Daoust
5 mins ago
Alpha failing on such a "basic" computation is more than unlikely. Even the Windows calculator returns $4$ ! (by chance ?)
â Yves Daoust
5 mins ago
add a comment |Â
4 Answers
4
active
oldest
votes
up vote
2
down vote
accepted
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.
add a comment |Â
up vote
1
down vote
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^2nequiv(-1)^2nequiv1pmod3$ where $n$ is any integer
$implies26^2n+2equiv1cdot26^2pmod3cdot26^2$
$implies26^2n+2equiv26^2pmod3cdot2^2equiv?$
add a comment |Â
up vote
1
down vote
Note that $26equiv 2pmod12$, so we can as well compute $r=2^32bmod 12$.
We have $2^32=12q+r$, so clearly $r=4s$, so we are reduced to compute $2^30bmod 3$ and now we can apply FermatâÂÂs little theorem: $2^2equiv 1pmod 3$; thus $2^30equiv 1=spmod3$ and therefore $r=4$.
add a comment |Â
up vote
0
down vote
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$.
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.
â Mark Bennet
14 mins ago
add a comment |Â
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
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.
add a comment |Â
up vote
2
down vote
accepted
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.
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
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.
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 1 hour ago
Sam Streeter
840217
840217
add a comment |Â
add a comment |Â
up vote
1
down vote
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^2nequiv(-1)^2nequiv1pmod3$ where $n$ is any integer
$implies26^2n+2equiv1cdot26^2pmod3cdot26^2$
$implies26^2n+2equiv26^2pmod3cdot2^2equiv?$
add a comment |Â
up vote
1
down vote
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^2nequiv(-1)^2nequiv1pmod3$ where $n$ is any integer
$implies26^2n+2equiv1cdot26^2pmod3cdot26^2$
$implies26^2n+2equiv26^2pmod3cdot2^2equiv?$
add a comment |Â
up vote
1
down vote
up vote
1
down vote
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^2nequiv(-1)^2nequiv1pmod3$ where $n$ is any integer
$implies26^2n+2equiv1cdot26^2pmod3cdot26^2$
$implies26^2n+2equiv26^2pmod3cdot2^2equiv?$
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^2nequiv(-1)^2nequiv1pmod3$ where $n$ is any integer
$implies26^2n+2equiv1cdot26^2pmod3cdot26^2$
$implies26^2n+2equiv26^2pmod3cdot2^2equiv?$
answered 1 hour ago
lab bhattacharjee
218k14153268
218k14153268
add a comment |Â
add a comment |Â
up vote
1
down vote
Note that $26equiv 2pmod12$, so we can as well compute $r=2^32bmod 12$.
We have $2^32=12q+r$, so clearly $r=4s$, so we are reduced to compute $2^30bmod 3$ and now we can apply FermatâÂÂs little theorem: $2^2equiv 1pmod 3$; thus $2^30equiv 1=spmod3$ and therefore $r=4$.
add a comment |Â
up vote
1
down vote
Note that $26equiv 2pmod12$, so we can as well compute $r=2^32bmod 12$.
We have $2^32=12q+r$, so clearly $r=4s$, so we are reduced to compute $2^30bmod 3$ and now we can apply FermatâÂÂs little theorem: $2^2equiv 1pmod 3$; thus $2^30equiv 1=spmod3$ and therefore $r=4$.
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Note that $26equiv 2pmod12$, so we can as well compute $r=2^32bmod 12$.
We have $2^32=12q+r$, so clearly $r=4s$, so we are reduced to compute $2^30bmod 3$ and now we can apply FermatâÂÂs little theorem: $2^2equiv 1pmod 3$; thus $2^30equiv 1=spmod3$ and therefore $r=4$.
Note that $26equiv 2pmod12$, so we can as well compute $r=2^32bmod 12$.
We have $2^32=12q+r$, so clearly $r=4s$, so we are reduced to compute $2^30bmod 3$ and now we can apply FermatâÂÂs little theorem: $2^2equiv 1pmod 3$; thus $2^30equiv 1=spmod3$ and therefore $r=4$.
answered 39 mins ago
egreg
171k1283193
171k1283193
add a comment |Â
add a comment |Â
up vote
0
down vote
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$.
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.
â Mark Bennet
14 mins ago
add a comment |Â
up vote
0
down vote
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$.
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.
â Mark Bennet
14 mins ago
add a comment |Â
up vote
0
down vote
up vote
0
down vote
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$.
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 18 mins ago
Mark Bennet
79k877177
79k877177
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.
â Mark Bennet
14 mins ago
add a comment |Â
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.
â Mark Bennet
14 mins ago
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.
â Mark Bennet
14 mins ago
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.
â Mark Bennet
14 mins ago
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2973194%2fcorrect-answer-to-this-modulo%23new-answer', 'question_page');
);
Post as a guest
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
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
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
3
How can it be $0$? $3$ does not divide $26$, so $12 (= 3 times 4)$ can't divide $26^32$
â ab123
1 hour ago
1
So the answer 4 is correct?
â Naruto Uzumaki
1 hour ago
1
yes the answer $4$ is correct
â ab123
1 hour ago
2
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.
â Sam Streeter
1 hour ago
Alpha failing on such a "basic" computation is more than unlikely. Even the Windows calculator returns $4$ ! (by chance ?)
â Yves Daoust
5 mins ago