Find last 3 digits of this monster numberWhen can you simplify the modulus? ($10^5^102 text mod 35$)how to find the last non-zero digit of $n$Why is $x^100 = 1 mod 1000$ if $x < 1000$ and $gcd (x,1000) = 1$?Last 3 digits of Marsenne numbersShow that $a^varphi(n)+1equiv a,mod n$.Showing that $a^5$ and $a$ have the same last digit using Euler's Theorem.Find the last ten digits of this exponential tower.Euler theorem, finding last digitsNumber Theory Linear Diophantine EquationsRSA decryption coefficientFinding the last 4 digits of a huge power
anything or something to eat
Can somebody explain Brexit in a few child-proof sentences?
How can "mimic phobia" be cured or prevented?
A Permanent Norse Presence in America
Drawing ramified coverings with tikz
How do I repair my stair bannister?
MAXDOP Settings for SQL Server 2014
Why has "pence" been used in this sentence, not "pences"?
Transformation of random variables and joint distributions
How will losing mobility of one hand affect my career as a programmer?
Have I saved too much for retirement so far?
What's the difference between 違法 and 不法?
Is a model fitted to data or is data fitted to a model?
THT: What is a squared annular “ring”?
Journal losing indexing services
Can I sign legal documents with a smiley face?
Are lightweight LN wallets vulnerable to transaction withholding?
How to align and center standalone amsmath equations?
Some numbers are more equivalent than others
Why did the HMS Bounty go back to a time when whales are already rare?
Is XSS in canonical link possible?
Will adding a BY-SA image to a blog post make the entire post BY-SA?
Could solar power be utilized and substitute coal in the 19th Century
Bob has never been a M before
Find last 3 digits of this monster number
When can you simplify the modulus? ($10^5^102 text mod 35$)how to find the last non-zero digit of $n$Why is $x^100 = 1 mod 1000$ if $x < 1000$ and $gcd (x,1000) = 1$?Last 3 digits of Marsenne numbersShow that $a^varphi(n)+1equiv a,mod n$.Showing that $a^5$ and $a$ have the same last digit using Euler's Theorem.Find the last ten digits of this exponential tower.Euler theorem, finding last digitsNumber Theory Linear Diophantine EquationsRSA decryption coefficientFinding the last 4 digits of a huge power
$begingroup$
Find the last 3 digits of this number
$$
2032^2031^2030^dots^2^1
$$
So obviously we are looking for $x$ so that
$$
2032^2031^2030^dots^2^1 equiv x quad textmodhspace0.1cm 1000
$$
I also know that usually you use Euler' theorem here, but that only works when the numbers $a$ and $n$ are coprime, but $2032$ and $1000$ are not coprime? I can easily find $varphi(1000)$, that is not a problem. Am I looking for wrong numbers to be coprime here or is there another way instead of Euler' theorem?
number-theory totient-function
$endgroup$
add a comment |
$begingroup$
Find the last 3 digits of this number
$$
2032^2031^2030^dots^2^1
$$
So obviously we are looking for $x$ so that
$$
2032^2031^2030^dots^2^1 equiv x quad textmodhspace0.1cm 1000
$$
I also know that usually you use Euler' theorem here, but that only works when the numbers $a$ and $n$ are coprime, but $2032$ and $1000$ are not coprime? I can easily find $varphi(1000)$, that is not a problem. Am I looking for wrong numbers to be coprime here or is there another way instead of Euler' theorem?
number-theory totient-function
$endgroup$
$begingroup$
The common factor here is $8$ and you should be able show that he power is divisible by $8$, so the residue modulo $1000$ can be determined by looking at the residue modulo $1000/8=125$
$endgroup$
– Mark Bennet
3 hours ago
$begingroup$
@Mark is correct, and in fact we can factor it out in a slick operational way that avoids using CRT by using the mod Distributive Law, as I show in my answer. This usually ends up being simpler than rotely applying CRT = Chinese Remainder when the base shares a common factor with the modulus.
$endgroup$
– Bill Dubuque
41 mins ago
add a comment |
$begingroup$
Find the last 3 digits of this number
$$
2032^2031^2030^dots^2^1
$$
So obviously we are looking for $x$ so that
$$
2032^2031^2030^dots^2^1 equiv x quad textmodhspace0.1cm 1000
$$
I also know that usually you use Euler' theorem here, but that only works when the numbers $a$ and $n$ are coprime, but $2032$ and $1000$ are not coprime? I can easily find $varphi(1000)$, that is not a problem. Am I looking for wrong numbers to be coprime here or is there another way instead of Euler' theorem?
number-theory totient-function
$endgroup$
Find the last 3 digits of this number
$$
2032^2031^2030^dots^2^1
$$
So obviously we are looking for $x$ so that
$$
2032^2031^2030^dots^2^1 equiv x quad textmodhspace0.1cm 1000
$$
I also know that usually you use Euler' theorem here, but that only works when the numbers $a$ and $n$ are coprime, but $2032$ and $1000$ are not coprime? I can easily find $varphi(1000)$, that is not a problem. Am I looking for wrong numbers to be coprime here or is there another way instead of Euler' theorem?
number-theory totient-function
number-theory totient-function
asked 3 hours ago
Kristin PeterselKristin Petersel
263
263
$begingroup$
The common factor here is $8$ and you should be able show that he power is divisible by $8$, so the residue modulo $1000$ can be determined by looking at the residue modulo $1000/8=125$
$endgroup$
– Mark Bennet
3 hours ago
$begingroup$
@Mark is correct, and in fact we can factor it out in a slick operational way that avoids using CRT by using the mod Distributive Law, as I show in my answer. This usually ends up being simpler than rotely applying CRT = Chinese Remainder when the base shares a common factor with the modulus.
$endgroup$
– Bill Dubuque
41 mins ago
add a comment |
$begingroup$
The common factor here is $8$ and you should be able show that he power is divisible by $8$, so the residue modulo $1000$ can be determined by looking at the residue modulo $1000/8=125$
$endgroup$
– Mark Bennet
3 hours ago
$begingroup$
@Mark is correct, and in fact we can factor it out in a slick operational way that avoids using CRT by using the mod Distributive Law, as I show in my answer. This usually ends up being simpler than rotely applying CRT = Chinese Remainder when the base shares a common factor with the modulus.
$endgroup$
– Bill Dubuque
41 mins ago
$begingroup$
The common factor here is $8$ and you should be able show that he power is divisible by $8$, so the residue modulo $1000$ can be determined by looking at the residue modulo $1000/8=125$
$endgroup$
– Mark Bennet
3 hours ago
$begingroup$
The common factor here is $8$ and you should be able show that he power is divisible by $8$, so the residue modulo $1000$ can be determined by looking at the residue modulo $1000/8=125$
$endgroup$
– Mark Bennet
3 hours ago
$begingroup$
@Mark is correct, and in fact we can factor it out in a slick operational way that avoids using CRT by using the mod Distributive Law, as I show in my answer. This usually ends up being simpler than rotely applying CRT = Chinese Remainder when the base shares a common factor with the modulus.
$endgroup$
– Bill Dubuque
41 mins ago
$begingroup$
@Mark is correct, and in fact we can factor it out in a slick operational way that avoids using CRT by using the mod Distributive Law, as I show in my answer. This usually ends up being simpler than rotely applying CRT = Chinese Remainder when the base shares a common factor with the modulus.
$endgroup$
– Bill Dubuque
41 mins ago
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
It's a lot simpler than it looks. I shall call the number $N$.
You will know the residue modulo $10^3$, thus the last three digits, if you first get the residues modulo $2^3=8$ and modulo $5^3=125$.
$N$ is obviously a multiple of $8$, thus $Nequiv 0bmod 8$. Which leaves $bmod 125$.
The base $2032equiv 32$. When this is raised to a power, the residue of this power depends only on the residue of the exponent $bmod 100$ where $100$ is the Euler totient of $125$. But the exponent on $2032$ has the form
$2031^10k=(2030+1)^10k=(textbinomial expansion)=100m+1$
So $Nequiv 32^1equiv 32bmod 125$. The only multiple of $8$ between $0$ and $999$ satisfying this result is $32$ itself so ... $Nequiv 32bmod 1000$. Meaning the last three digits were there all along, the $colorblue032$ in the base $2032$!
$endgroup$
1
$begingroup$
(+1) same answer I got, by means similar enough that I won't add another post here.
$endgroup$
– robjohn♦
2 hours ago
$begingroup$
Worth emphasis is that arguments like this can be presented completely operationally by employing the mod Distributive Law, and this clarifies and simplifies the arithmetic - see my answer.
$endgroup$
– Bill Dubuque
1 hour ago
add a comment |
$begingroup$
By the Chinese Remainder Theorem, if you want to find what remainder a given number has when divided by $1000$, you can split that into 2 problems: Find the remainder$mod 8$ and$mod 125$. Obviously
$$z_0:=2032^2031^2030^dots^2^1 equiv 0 pmod 8$$
What remains to be found is $x_0 in [0,124]$ in
$$z_0 equiv x_0 pmod 125.$$
As $z_0$ is now coprime to $125$, you can apply Euler's theorem now. With
$$z_1:=2031^2030^dots^2^1$$
and
$$phi(125)=100$$ the new problem becomes to find $x_1 in [0,99]$ in
$$z_1 equiv x_1 pmod 100$$
and then use
$$32^x_1 equiv x_0 pmod 125$$
to find $x_0$.
So this reduced the original problem$mod 1000$ to a smaller problem$mod 100$.
Applying this reduction procedure a few more times (using the Chinese Remainder Theorem if appropriate), should result in congruences with smaller and smaller module that can in the end be solved (e.g $mod 2$).
Then to solve the original problem you need to back-substitute the calculated $x_i$ to get $x_i-1$, just as outlined for $x_1,x_0$ above.
$endgroup$
add a comment |
$begingroup$
Don't be scared. If it turns into a monster and eats you, run away after you throw stones at it. Don't run away before throwing stones just because it looks like a monster.
$2032^monster$ and $1000$ are relatively prime so we can't use Euler theorem but we can break it down with Chinese remainder theorem.
$2032^monster = 0 pmod 8$ and so we just need to solve $2032^monster pmod 125$ and for that we can use Euler Theorem.
$phi(125=5^3) = (5-1)*5^3-1 = 100$.
So $2032^monster equiv 32^monster % 100$.
And $monster = 2031^littlemonsterequiv 31^littlemonsterpmod 100$
$31$ and $100$ are relatively prime and $phi(100)= 40$ so
$31^littlemonster equiv 31^littlemonster % 40 pmod 100$.
$littlemonster = 2030^smallmonster$ but $5|2030$ and as $smallmonster > 2$ we know $8|2^smallmonster$ and $2^smallmonster|2030^smallmonster$.
So $littlemonster equiv 0 pmod 40$.
$2031^littlemonster equiv 31^0 equiv 1 pmod 100$
So $2032^monster equiv 31 pmod 125$
So $2032^monster equiv 0 pmod 8$ and $2032^monster equiv 31 pmod 125$.
So $2032^monster equiv 31 + 125k pmod 1000$ where $8|31 + 125k$.
I.e. $31+125k equiv -1 - 3k equiv 0 pmod 8$ so $3k equiv -1equiv 15 pmod 8$ so $k=5$ and
$2032^monster equiv 656pmod1000$
$endgroup$
add a comment |
$begingroup$
$bmod 1000!: 32^large 2031^LARGE 2k!!equiv, 8left[dfraccolor#0a032^large 2031^LARGE 2k8 bmod color#0a0125right]! equiv 8left[dfraccolor#c00328bmod 125right]! equiv 32, $ by
$ ,beginalign !bmod color#0a0125!: color#0a032^large 2031^LARGE 2k!!
&equiv, 2^large 5cdot 2031^LARGE 2k! bmod 100 rm by 100 = phi(125) rm [Euler totient]\
&equiv,2^large 5(color#b6f2031^LARGE color#d4f2k! bmod 20) rm by mod Distributive Law\
&equiv,2^large 5(color#b6f1^LARGE k)equiv, color#c0032 rm by color#b6f2031^large 2!equiv 11^large 2equivcolor#b6f 1!!!pmod!20\
endalign $
$endgroup$
$begingroup$
We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
$endgroup$
– Bill Dubuque
1 hour ago
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%2f3161051%2ffind-last-3-digits-of-this-monster-number%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
It's a lot simpler than it looks. I shall call the number $N$.
You will know the residue modulo $10^3$, thus the last three digits, if you first get the residues modulo $2^3=8$ and modulo $5^3=125$.
$N$ is obviously a multiple of $8$, thus $Nequiv 0bmod 8$. Which leaves $bmod 125$.
The base $2032equiv 32$. When this is raised to a power, the residue of this power depends only on the residue of the exponent $bmod 100$ where $100$ is the Euler totient of $125$. But the exponent on $2032$ has the form
$2031^10k=(2030+1)^10k=(textbinomial expansion)=100m+1$
So $Nequiv 32^1equiv 32bmod 125$. The only multiple of $8$ between $0$ and $999$ satisfying this result is $32$ itself so ... $Nequiv 32bmod 1000$. Meaning the last three digits were there all along, the $colorblue032$ in the base $2032$!
$endgroup$
1
$begingroup$
(+1) same answer I got, by means similar enough that I won't add another post here.
$endgroup$
– robjohn♦
2 hours ago
$begingroup$
Worth emphasis is that arguments like this can be presented completely operationally by employing the mod Distributive Law, and this clarifies and simplifies the arithmetic - see my answer.
$endgroup$
– Bill Dubuque
1 hour ago
add a comment |
$begingroup$
It's a lot simpler than it looks. I shall call the number $N$.
You will know the residue modulo $10^3$, thus the last three digits, if you first get the residues modulo $2^3=8$ and modulo $5^3=125$.
$N$ is obviously a multiple of $8$, thus $Nequiv 0bmod 8$. Which leaves $bmod 125$.
The base $2032equiv 32$. When this is raised to a power, the residue of this power depends only on the residue of the exponent $bmod 100$ where $100$ is the Euler totient of $125$. But the exponent on $2032$ has the form
$2031^10k=(2030+1)^10k=(textbinomial expansion)=100m+1$
So $Nequiv 32^1equiv 32bmod 125$. The only multiple of $8$ between $0$ and $999$ satisfying this result is $32$ itself so ... $Nequiv 32bmod 1000$. Meaning the last three digits were there all along, the $colorblue032$ in the base $2032$!
$endgroup$
1
$begingroup$
(+1) same answer I got, by means similar enough that I won't add another post here.
$endgroup$
– robjohn♦
2 hours ago
$begingroup$
Worth emphasis is that arguments like this can be presented completely operationally by employing the mod Distributive Law, and this clarifies and simplifies the arithmetic - see my answer.
$endgroup$
– Bill Dubuque
1 hour ago
add a comment |
$begingroup$
It's a lot simpler than it looks. I shall call the number $N$.
You will know the residue modulo $10^3$, thus the last three digits, if you first get the residues modulo $2^3=8$ and modulo $5^3=125$.
$N$ is obviously a multiple of $8$, thus $Nequiv 0bmod 8$. Which leaves $bmod 125$.
The base $2032equiv 32$. When this is raised to a power, the residue of this power depends only on the residue of the exponent $bmod 100$ where $100$ is the Euler totient of $125$. But the exponent on $2032$ has the form
$2031^10k=(2030+1)^10k=(textbinomial expansion)=100m+1$
So $Nequiv 32^1equiv 32bmod 125$. The only multiple of $8$ between $0$ and $999$ satisfying this result is $32$ itself so ... $Nequiv 32bmod 1000$. Meaning the last three digits were there all along, the $colorblue032$ in the base $2032$!
$endgroup$
It's a lot simpler than it looks. I shall call the number $N$.
You will know the residue modulo $10^3$, thus the last three digits, if you first get the residues modulo $2^3=8$ and modulo $5^3=125$.
$N$ is obviously a multiple of $8$, thus $Nequiv 0bmod 8$. Which leaves $bmod 125$.
The base $2032equiv 32$. When this is raised to a power, the residue of this power depends only on the residue of the exponent $bmod 100$ where $100$ is the Euler totient of $125$. But the exponent on $2032$ has the form
$2031^10k=(2030+1)^10k=(textbinomial expansion)=100m+1$
So $Nequiv 32^1equiv 32bmod 125$. The only multiple of $8$ between $0$ and $999$ satisfying this result is $32$ itself so ... $Nequiv 32bmod 1000$. Meaning the last three digits were there all along, the $colorblue032$ in the base $2032$!
edited 3 hours ago
answered 3 hours ago
Oscar LanziOscar Lanzi
13.2k12136
13.2k12136
1
$begingroup$
(+1) same answer I got, by means similar enough that I won't add another post here.
$endgroup$
– robjohn♦
2 hours ago
$begingroup$
Worth emphasis is that arguments like this can be presented completely operationally by employing the mod Distributive Law, and this clarifies and simplifies the arithmetic - see my answer.
$endgroup$
– Bill Dubuque
1 hour ago
add a comment |
1
$begingroup$
(+1) same answer I got, by means similar enough that I won't add another post here.
$endgroup$
– robjohn♦
2 hours ago
$begingroup$
Worth emphasis is that arguments like this can be presented completely operationally by employing the mod Distributive Law, and this clarifies and simplifies the arithmetic - see my answer.
$endgroup$
– Bill Dubuque
1 hour ago
1
1
$begingroup$
(+1) same answer I got, by means similar enough that I won't add another post here.
$endgroup$
– robjohn♦
2 hours ago
$begingroup$
(+1) same answer I got, by means similar enough that I won't add another post here.
$endgroup$
– robjohn♦
2 hours ago
$begingroup$
Worth emphasis is that arguments like this can be presented completely operationally by employing the mod Distributive Law, and this clarifies and simplifies the arithmetic - see my answer.
$endgroup$
– Bill Dubuque
1 hour ago
$begingroup$
Worth emphasis is that arguments like this can be presented completely operationally by employing the mod Distributive Law, and this clarifies and simplifies the arithmetic - see my answer.
$endgroup$
– Bill Dubuque
1 hour ago
add a comment |
$begingroup$
By the Chinese Remainder Theorem, if you want to find what remainder a given number has when divided by $1000$, you can split that into 2 problems: Find the remainder$mod 8$ and$mod 125$. Obviously
$$z_0:=2032^2031^2030^dots^2^1 equiv 0 pmod 8$$
What remains to be found is $x_0 in [0,124]$ in
$$z_0 equiv x_0 pmod 125.$$
As $z_0$ is now coprime to $125$, you can apply Euler's theorem now. With
$$z_1:=2031^2030^dots^2^1$$
and
$$phi(125)=100$$ the new problem becomes to find $x_1 in [0,99]$ in
$$z_1 equiv x_1 pmod 100$$
and then use
$$32^x_1 equiv x_0 pmod 125$$
to find $x_0$.
So this reduced the original problem$mod 1000$ to a smaller problem$mod 100$.
Applying this reduction procedure a few more times (using the Chinese Remainder Theorem if appropriate), should result in congruences with smaller and smaller module that can in the end be solved (e.g $mod 2$).
Then to solve the original problem you need to back-substitute the calculated $x_i$ to get $x_i-1$, just as outlined for $x_1,x_0$ above.
$endgroup$
add a comment |
$begingroup$
By the Chinese Remainder Theorem, if you want to find what remainder a given number has when divided by $1000$, you can split that into 2 problems: Find the remainder$mod 8$ and$mod 125$. Obviously
$$z_0:=2032^2031^2030^dots^2^1 equiv 0 pmod 8$$
What remains to be found is $x_0 in [0,124]$ in
$$z_0 equiv x_0 pmod 125.$$
As $z_0$ is now coprime to $125$, you can apply Euler's theorem now. With
$$z_1:=2031^2030^dots^2^1$$
and
$$phi(125)=100$$ the new problem becomes to find $x_1 in [0,99]$ in
$$z_1 equiv x_1 pmod 100$$
and then use
$$32^x_1 equiv x_0 pmod 125$$
to find $x_0$.
So this reduced the original problem$mod 1000$ to a smaller problem$mod 100$.
Applying this reduction procedure a few more times (using the Chinese Remainder Theorem if appropriate), should result in congruences with smaller and smaller module that can in the end be solved (e.g $mod 2$).
Then to solve the original problem you need to back-substitute the calculated $x_i$ to get $x_i-1$, just as outlined for $x_1,x_0$ above.
$endgroup$
add a comment |
$begingroup$
By the Chinese Remainder Theorem, if you want to find what remainder a given number has when divided by $1000$, you can split that into 2 problems: Find the remainder$mod 8$ and$mod 125$. Obviously
$$z_0:=2032^2031^2030^dots^2^1 equiv 0 pmod 8$$
What remains to be found is $x_0 in [0,124]$ in
$$z_0 equiv x_0 pmod 125.$$
As $z_0$ is now coprime to $125$, you can apply Euler's theorem now. With
$$z_1:=2031^2030^dots^2^1$$
and
$$phi(125)=100$$ the new problem becomes to find $x_1 in [0,99]$ in
$$z_1 equiv x_1 pmod 100$$
and then use
$$32^x_1 equiv x_0 pmod 125$$
to find $x_0$.
So this reduced the original problem$mod 1000$ to a smaller problem$mod 100$.
Applying this reduction procedure a few more times (using the Chinese Remainder Theorem if appropriate), should result in congruences with smaller and smaller module that can in the end be solved (e.g $mod 2$).
Then to solve the original problem you need to back-substitute the calculated $x_i$ to get $x_i-1$, just as outlined for $x_1,x_0$ above.
$endgroup$
By the Chinese Remainder Theorem, if you want to find what remainder a given number has when divided by $1000$, you can split that into 2 problems: Find the remainder$mod 8$ and$mod 125$. Obviously
$$z_0:=2032^2031^2030^dots^2^1 equiv 0 pmod 8$$
What remains to be found is $x_0 in [0,124]$ in
$$z_0 equiv x_0 pmod 125.$$
As $z_0$ is now coprime to $125$, you can apply Euler's theorem now. With
$$z_1:=2031^2030^dots^2^1$$
and
$$phi(125)=100$$ the new problem becomes to find $x_1 in [0,99]$ in
$$z_1 equiv x_1 pmod 100$$
and then use
$$32^x_1 equiv x_0 pmod 125$$
to find $x_0$.
So this reduced the original problem$mod 1000$ to a smaller problem$mod 100$.
Applying this reduction procedure a few more times (using the Chinese Remainder Theorem if appropriate), should result in congruences with smaller and smaller module that can in the end be solved (e.g $mod 2$).
Then to solve the original problem you need to back-substitute the calculated $x_i$ to get $x_i-1$, just as outlined for $x_1,x_0$ above.
answered 3 hours ago
IngixIngix
5,032159
5,032159
add a comment |
add a comment |
$begingroup$
Don't be scared. If it turns into a monster and eats you, run away after you throw stones at it. Don't run away before throwing stones just because it looks like a monster.
$2032^monster$ and $1000$ are relatively prime so we can't use Euler theorem but we can break it down with Chinese remainder theorem.
$2032^monster = 0 pmod 8$ and so we just need to solve $2032^monster pmod 125$ and for that we can use Euler Theorem.
$phi(125=5^3) = (5-1)*5^3-1 = 100$.
So $2032^monster equiv 32^monster % 100$.
And $monster = 2031^littlemonsterequiv 31^littlemonsterpmod 100$
$31$ and $100$ are relatively prime and $phi(100)= 40$ so
$31^littlemonster equiv 31^littlemonster % 40 pmod 100$.
$littlemonster = 2030^smallmonster$ but $5|2030$ and as $smallmonster > 2$ we know $8|2^smallmonster$ and $2^smallmonster|2030^smallmonster$.
So $littlemonster equiv 0 pmod 40$.
$2031^littlemonster equiv 31^0 equiv 1 pmod 100$
So $2032^monster equiv 31 pmod 125$
So $2032^monster equiv 0 pmod 8$ and $2032^monster equiv 31 pmod 125$.
So $2032^monster equiv 31 + 125k pmod 1000$ where $8|31 + 125k$.
I.e. $31+125k equiv -1 - 3k equiv 0 pmod 8$ so $3k equiv -1equiv 15 pmod 8$ so $k=5$ and
$2032^monster equiv 656pmod1000$
$endgroup$
add a comment |
$begingroup$
Don't be scared. If it turns into a monster and eats you, run away after you throw stones at it. Don't run away before throwing stones just because it looks like a monster.
$2032^monster$ and $1000$ are relatively prime so we can't use Euler theorem but we can break it down with Chinese remainder theorem.
$2032^monster = 0 pmod 8$ and so we just need to solve $2032^monster pmod 125$ and for that we can use Euler Theorem.
$phi(125=5^3) = (5-1)*5^3-1 = 100$.
So $2032^monster equiv 32^monster % 100$.
And $monster = 2031^littlemonsterequiv 31^littlemonsterpmod 100$
$31$ and $100$ are relatively prime and $phi(100)= 40$ so
$31^littlemonster equiv 31^littlemonster % 40 pmod 100$.
$littlemonster = 2030^smallmonster$ but $5|2030$ and as $smallmonster > 2$ we know $8|2^smallmonster$ and $2^smallmonster|2030^smallmonster$.
So $littlemonster equiv 0 pmod 40$.
$2031^littlemonster equiv 31^0 equiv 1 pmod 100$
So $2032^monster equiv 31 pmod 125$
So $2032^monster equiv 0 pmod 8$ and $2032^monster equiv 31 pmod 125$.
So $2032^monster equiv 31 + 125k pmod 1000$ where $8|31 + 125k$.
I.e. $31+125k equiv -1 - 3k equiv 0 pmod 8$ so $3k equiv -1equiv 15 pmod 8$ so $k=5$ and
$2032^monster equiv 656pmod1000$
$endgroup$
add a comment |
$begingroup$
Don't be scared. If it turns into a monster and eats you, run away after you throw stones at it. Don't run away before throwing stones just because it looks like a monster.
$2032^monster$ and $1000$ are relatively prime so we can't use Euler theorem but we can break it down with Chinese remainder theorem.
$2032^monster = 0 pmod 8$ and so we just need to solve $2032^monster pmod 125$ and for that we can use Euler Theorem.
$phi(125=5^3) = (5-1)*5^3-1 = 100$.
So $2032^monster equiv 32^monster % 100$.
And $monster = 2031^littlemonsterequiv 31^littlemonsterpmod 100$
$31$ and $100$ are relatively prime and $phi(100)= 40$ so
$31^littlemonster equiv 31^littlemonster % 40 pmod 100$.
$littlemonster = 2030^smallmonster$ but $5|2030$ and as $smallmonster > 2$ we know $8|2^smallmonster$ and $2^smallmonster|2030^smallmonster$.
So $littlemonster equiv 0 pmod 40$.
$2031^littlemonster equiv 31^0 equiv 1 pmod 100$
So $2032^monster equiv 31 pmod 125$
So $2032^monster equiv 0 pmod 8$ and $2032^monster equiv 31 pmod 125$.
So $2032^monster equiv 31 + 125k pmod 1000$ where $8|31 + 125k$.
I.e. $31+125k equiv -1 - 3k equiv 0 pmod 8$ so $3k equiv -1equiv 15 pmod 8$ so $k=5$ and
$2032^monster equiv 656pmod1000$
$endgroup$
Don't be scared. If it turns into a monster and eats you, run away after you throw stones at it. Don't run away before throwing stones just because it looks like a monster.
$2032^monster$ and $1000$ are relatively prime so we can't use Euler theorem but we can break it down with Chinese remainder theorem.
$2032^monster = 0 pmod 8$ and so we just need to solve $2032^monster pmod 125$ and for that we can use Euler Theorem.
$phi(125=5^3) = (5-1)*5^3-1 = 100$.
So $2032^monster equiv 32^monster % 100$.
And $monster = 2031^littlemonsterequiv 31^littlemonsterpmod 100$
$31$ and $100$ are relatively prime and $phi(100)= 40$ so
$31^littlemonster equiv 31^littlemonster % 40 pmod 100$.
$littlemonster = 2030^smallmonster$ but $5|2030$ and as $smallmonster > 2$ we know $8|2^smallmonster$ and $2^smallmonster|2030^smallmonster$.
So $littlemonster equiv 0 pmod 40$.
$2031^littlemonster equiv 31^0 equiv 1 pmod 100$
So $2032^monster equiv 31 pmod 125$
So $2032^monster equiv 0 pmod 8$ and $2032^monster equiv 31 pmod 125$.
So $2032^monster equiv 31 + 125k pmod 1000$ where $8|31 + 125k$.
I.e. $31+125k equiv -1 - 3k equiv 0 pmod 8$ so $3k equiv -1equiv 15 pmod 8$ so $k=5$ and
$2032^monster equiv 656pmod1000$
answered 1 hour ago
fleabloodfleablood
73.1k22789
73.1k22789
add a comment |
add a comment |
$begingroup$
$bmod 1000!: 32^large 2031^LARGE 2k!!equiv, 8left[dfraccolor#0a032^large 2031^LARGE 2k8 bmod color#0a0125right]! equiv 8left[dfraccolor#c00328bmod 125right]! equiv 32, $ by
$ ,beginalign !bmod color#0a0125!: color#0a032^large 2031^LARGE 2k!!
&equiv, 2^large 5cdot 2031^LARGE 2k! bmod 100 rm by 100 = phi(125) rm [Euler totient]\
&equiv,2^large 5(color#b6f2031^LARGE color#d4f2k! bmod 20) rm by mod Distributive Law\
&equiv,2^large 5(color#b6f1^LARGE k)equiv, color#c0032 rm by color#b6f2031^large 2!equiv 11^large 2equivcolor#b6f 1!!!pmod!20\
endalign $
$endgroup$
$begingroup$
We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
$endgroup$
– Bill Dubuque
1 hour ago
add a comment |
$begingroup$
$bmod 1000!: 32^large 2031^LARGE 2k!!equiv, 8left[dfraccolor#0a032^large 2031^LARGE 2k8 bmod color#0a0125right]! equiv 8left[dfraccolor#c00328bmod 125right]! equiv 32, $ by
$ ,beginalign !bmod color#0a0125!: color#0a032^large 2031^LARGE 2k!!
&equiv, 2^large 5cdot 2031^LARGE 2k! bmod 100 rm by 100 = phi(125) rm [Euler totient]\
&equiv,2^large 5(color#b6f2031^LARGE color#d4f2k! bmod 20) rm by mod Distributive Law\
&equiv,2^large 5(color#b6f1^LARGE k)equiv, color#c0032 rm by color#b6f2031^large 2!equiv 11^large 2equivcolor#b6f 1!!!pmod!20\
endalign $
$endgroup$
$begingroup$
We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
$endgroup$
– Bill Dubuque
1 hour ago
add a comment |
$begingroup$
$bmod 1000!: 32^large 2031^LARGE 2k!!equiv, 8left[dfraccolor#0a032^large 2031^LARGE 2k8 bmod color#0a0125right]! equiv 8left[dfraccolor#c00328bmod 125right]! equiv 32, $ by
$ ,beginalign !bmod color#0a0125!: color#0a032^large 2031^LARGE 2k!!
&equiv, 2^large 5cdot 2031^LARGE 2k! bmod 100 rm by 100 = phi(125) rm [Euler totient]\
&equiv,2^large 5(color#b6f2031^LARGE color#d4f2k! bmod 20) rm by mod Distributive Law\
&equiv,2^large 5(color#b6f1^LARGE k)equiv, color#c0032 rm by color#b6f2031^large 2!equiv 11^large 2equivcolor#b6f 1!!!pmod!20\
endalign $
$endgroup$
$bmod 1000!: 32^large 2031^LARGE 2k!!equiv, 8left[dfraccolor#0a032^large 2031^LARGE 2k8 bmod color#0a0125right]! equiv 8left[dfraccolor#c00328bmod 125right]! equiv 32, $ by
$ ,beginalign !bmod color#0a0125!: color#0a032^large 2031^LARGE 2k!!
&equiv, 2^large 5cdot 2031^LARGE 2k! bmod 100 rm by 100 = phi(125) rm [Euler totient]\
&equiv,2^large 5(color#b6f2031^LARGE color#d4f2k! bmod 20) rm by mod Distributive Law\
&equiv,2^large 5(color#b6f1^LARGE k)equiv, color#c0032 rm by color#b6f2031^large 2!equiv 11^large 2equivcolor#b6f 1!!!pmod!20\
endalign $
edited 1 hour ago
answered 1 hour ago
Bill DubuqueBill Dubuque
213k29195654
213k29195654
$begingroup$
We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
$endgroup$
– Bill Dubuque
1 hour ago
add a comment |
$begingroup$
We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
$endgroup$
– Bill Dubuque
1 hour ago
$begingroup$
We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
$endgroup$
– Bill Dubuque
1 hour ago
$begingroup$
We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
$endgroup$
– Bill Dubuque
1 hour ago
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%2f3161051%2ffind-last-3-digits-of-this-monster-number%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$
The common factor here is $8$ and you should be able show that he power is divisible by $8$, so the residue modulo $1000$ can be determined by looking at the residue modulo $1000/8=125$
$endgroup$
– Mark Bennet
3 hours ago
$begingroup$
@Mark is correct, and in fact we can factor it out in a slick operational way that avoids using CRT by using the mod Distributive Law, as I show in my answer. This usually ends up being simpler than rotely applying CRT = Chinese Remainder when the base shares a common factor with the modulus.
$endgroup$
– Bill Dubuque
41 mins ago