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
Journal losing indexing services
Why is Arduino resetting while driving motors?
When quoting, must I also copy hyphens used to divide words that continue on the next line?
Divine apple island
Is it possible to use .desktop files to open local pdf files on specific pages with a browser?
Bob has never been a M before
Can I use my Chinese passport to enter China after I acquired another citizenship?
THT: What is a squared annular “ring”?
What major Native American tribes were around Santa Fe during the late 1850s?
Drawing a topological "handle" with Tikz
Fuse symbol on toroidal transformer
How can Trident be so inexpensive? Will it orbit Triton or just do a (slow) flyby?
Difference between -| and |- in TikZ
What is this type of notehead called?
Why has "pence" been used in this sentence, not "pences"?
Indicating multiple different modes of speech (fantasy language or telepathy)
Do the concepts of IP address and network interface not belong to the same layer?
How should I respond when I lied about my education and the company finds out through background check?
Visiting the UK as unmarried couple
Can we have a perfect cadence in a minor key?
How will losing mobility of one hand affect my career as a programmer?
Did US corporations pay demonstrators in the German demonstrations against article 13?
What does this horizontal bar at the first measure mean?
Can I sign legal documents with a smiley face?
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
58 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
58 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
58 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
58 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
58 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$
$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$
1
$begingroup$
We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
$endgroup$
– Bill Dubuque
2 hours 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 |
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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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.3k12136
13.3k12136
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$
$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$
1
$begingroup$
We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
$endgroup$
– Bill Dubuque
2 hours 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$
1
$begingroup$
We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
$endgroup$
– Bill Dubuque
2 hours 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 2 hours ago
Bill DubuqueBill Dubuque
213k29195654
213k29195654
1
$begingroup$
We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
$endgroup$
– Bill Dubuque
2 hours ago
add a comment |
1
$begingroup$
We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
$endgroup$
– Bill Dubuque
2 hours ago
1
1
$begingroup$
We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
$endgroup$
– Bill Dubuque
2 hours ago
$begingroup$
We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
$endgroup$
– Bill Dubuque
2 hours 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 2 hours ago
fleabloodfleablood
73.1k22789
73.1k22789
add a comment |
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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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
58 mins ago