What's the remainder if $99{,}999^{99}$ is divided by $999{,}999$?
up vote
4
down vote
favorite
What's the remainder if $99{,}999^{99}$ is divided by $999{,}999$?
Is there any formula or trick method to achieve this?
Also kindly ignore the improper use of tag as i don't know which tag to choose
elementary-number-theory modular-arithmetic
edited Nov 22 at 0:01
Barry Cipra
58.6k653122
asked Nov 21 at 20:56
Girish venkata
212
|
show 2 more comments
up vote
4
down vote
favorite
What's the remainder if $99{,}999^{99}$ is divided by $999{,}999$?
Is there any formula or trick method to achieve this?
Also kindly ignore the improper use of tag as i don't know which tag to choose
elementary-number-theory modular-arithmetic
edited Nov 22 at 0:01
Barry Cipra
58.6k653122
asked Nov 21 at 20:56
Girish venkata
212
Hint: relabel $999999$ as $x$. What's the remainder after division?
– John Douma
Nov 21 at 20:58
1
Computer says 123579, but I don't see elegant trick besides laboriously doing square-and-multiply
– Hagen von Eitzen
Nov 21 at 21:07
@JohnDouma: I don't get it.
– TonyK
Nov 21 at 23:21
@Hagen Your hardware is consistent with my wetware - see my answer.
– Bill Dubuque
Nov 21 at 23:34
@TonyK I misread the question. I thought both numbers consisted of six $9$s.
– John Douma
Nov 21 at 23:39
|
show 2 more comments
up vote
4
down vote
favorite
up vote
4
down vote
favorite
What's the remainder if $99{,}999^{99}$ is divided by $999{,}999$?
Is there any formula or trick method to achieve this?
Also kindly ignore the improper use of tag as i don't know which tag to choose
elementary-number-theory modular-arithmetic
edited Nov 22 at 0:01
Barry Cipra
58.6k653122
asked Nov 21 at 20:56
Girish venkata
212
What's the remainder if $99{,}999^{99}$ is divided by $999{,}999$?
Is there any formula or trick method to achieve this?
Also kindly ignore the improper use of tag as i don't know which tag to choose
elementary-number-theory modular-arithmetic
elementary-number-theory modular-arithmetic
edited Nov 22 at 0:01
Barry Cipra
58.6k653122
asked Nov 21 at 20:56
Girish venkata
212
edited Nov 22 at 0:01
Barry Cipra
58.6k653122
asked Nov 21 at 20:56
Girish venkata
212
edited Nov 22 at 0:01
Barry Cipra
58.6k653122
edited Nov 22 at 0:01
Barry Cipra
58.6k653122
edited Nov 22 at 0:01
Barry Cipra
58.6k653122
58.6k653122
asked Nov 21 at 20:56
Girish venkata
212
asked Nov 21 at 20:56
Girish venkata
212
asked Nov 21 at 20:56
Girish venkata
212
212
Hint: relabel $999999$ as $x$. What's the remainder after division?
– John Douma
Nov 21 at 20:58
1
Computer says 123579, but I don't see elegant trick besides laboriously doing square-and-multiply
– Hagen von Eitzen
Nov 21 at 21:07
@JohnDouma: I don't get it.
– TonyK
Nov 21 at 23:21
@Hagen Your hardware is consistent with my wetware - see my answer.
– Bill Dubuque
Nov 21 at 23:34
@TonyK I misread the question. I thought both numbers consisted of six $9$s.
– John Douma
Nov 21 at 23:39
|
show 2 more comments
Hint: relabel $999999$ as $x$. What's the remainder after division?
– John Douma
Nov 21 at 20:58
1
Computer says 123579, but I don't see elegant trick besides laboriously doing square-and-multiply
– Hagen von Eitzen
Nov 21 at 21:07
@JohnDouma: I don't get it.
– TonyK
Nov 21 at 23:21
@Hagen Your hardware is consistent with my wetware - see my answer.
– Bill Dubuque
Nov 21 at 23:34
@TonyK I misread the question. I thought both numbers consisted of six $9$s.
– John Douma
Nov 21 at 23:39
Hint: relabel $999999$ as $x$. What's the remainder after division?
– John Douma
Nov 21 at 20:58
Hint: relabel $999999$ as $x$. What's the remainder after division?
– John Douma
Nov 21 at 20:58
1
1
Computer says 123579, but I don't see elegant trick besides laboriously doing square-and-multiply
– Hagen von Eitzen
Nov 21 at 21:07
Computer says 123579, but I don't see elegant trick besides laboriously doing square-and-multiply
– Hagen von Eitzen
Nov 21 at 21:07
@JohnDouma: I don't get it.
– TonyK
Nov 21 at 23:21
@JohnDouma: I don't get it.
– TonyK
Nov 21 at 23:21
@Hagen Your hardware is consistent with my wetware - see my answer.
– Bill Dubuque
Nov 21 at 23:34
@Hagen Your hardware is consistent with my wetware - see my answer.
– Bill Dubuque
Nov 21 at 23:34
@TonyK I misread the question. I thought both numbers consisted of six $9$s.
– John Douma
Nov 21 at 23:39
@TonyK I misread the question. I thought both numbers consisted of six $9$s.
– John Douma
Nov 21 at 23:39
|
show 2 more comments
2 Answers
2
active
oldest
votes
up vote
2
down vote
$!bmod 999999!:, 10cdot99999equiv -9 $ so $ 99999 equiv -9/10$
Thus $,99999^{large99}equiv -9^{large 99}/10^{large 99}equiv -9^{large 99}/10^{large 3}equiv -10^{large 3}cdot 9^{large 99} $ via $ 10^{large
6}equiv 1$
$n := 999999/27 = 7cdot 11cdot 13cdot 37.,$ mod each $p,,$ $9,$ has order $,3,5,3,9,$ so $,9^{large color{#c00}{45}}equiv 1pmod{!n}$
so $ 9^{large 99}!bmod 999999 = 27(3cdot 9^{large color{#c00}{97}}!bmod n) = 27(3cdot 9^{large 7}!bmod n) equiv 9^{large 9}!pmod{!999999}$
Hence we conclude $ 99999^{large 99}equiv -10^{large 3}cdot 9^{large 99}equiv {-}10^{large 3}cdot 9^{large 9}equiv 123579,pmod{!999999}$
answered Nov 21 at 22:35
Bill Dubuque
207k29189624
Due to $999999$ isn't a prime number you should say that $10$ has an inverse because it's coprime with $999999$.
– P De Donato
Nov 21 at 22:51
Then you can't arbitrarly pass from mod $999999$ to mod $n$.
– P De Donato
Nov 21 at 22:52
He's using the Chinese remainder theorem there. It's clear that $99999^{99} equiv 0 bmod 27$.
– Qiaochu Yuan
Nov 21 at 22:53
@PDeDonato That's obvious: $bmod 10^6-1!:, 10cdot 10^5equiv 1 $ so $10^{-1}equiv 10^5 $
– Bill Dubuque
Nov 21 at 22:54
I know it, but the answer isn't so clear.
– P De Donato
Nov 21 at 22:56
|
show 3 more comments
up vote
2
down vote
We work in the ring $R=Bbb Z/N$, with operation modulo $N=999999=10^6-1$.
(Equalities below address computations in $R$.)
Then
$$
begin{aligned}
99999^{99}
&=(99999-999999)^{99} =(-900000)^{99}=-9^{99}cdot (10^5)^{99}\
&=-3^{198}cdot 10^{495}=-3^{198}cdot {underbrace{(10^6)}_{=1}}^{82}cdot 10^3=-3^{198}cdot 1000 .
end{aligned}
$$
Now the order of (the unit) $3$ in the ring
$Bbb Z/37037
=Bbb Z/(7cdot 11cdot 13cdot 37)
cong
(Bbb Z/7)times
(Bbb Z/11)times
(Bbb Z/13)times
(Bbb Z/37)
$
is $90$, but we need only the simpler information that $3^{180}$ is one modulo $37037$. This is so because $180$ is a multiple of $(7-1)$, $(11-1)$, $(13-1)$, and $(37-1)$. So instead of $3^{198}$ we write the smaller power $3^{18}=387420489$.
We finally search for a number which is $0$ modulo $27$, and also $-387420489000$ modulo $37037$, which is $12468$. After rearrangements modulo $3,9,27$ we get the result
$$123579 .$$
Note: A computer algebra system like sage delivers immediately
sage: Zmod(999999)(99999)^99
123579
answered Nov 22 at 0:42
dan_fulea
6,2101312
This is essentially the same as my answer, except I used the mod distributive law form of CRT (which makes it simpler).
– Bill Dubuque
Nov 22 at 0:45
I committed it now after typing in the train... Yes, same computation.
– dan_fulea
Nov 22 at 0:50
Thank you very much, it took some time but i eventually understood
– Girish venkata
Nov 26 at 18:12
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',
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%2f3008349%2fwhats-the-remainder-if-99-99999-is-divided-by-999-999%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
$!bmod 999999!:, 10cdot99999equiv -9 $ so $ 99999 equiv -9/10$
Thus $,99999^{large99}equiv -9^{large 99}/10^{large 99}equiv -9^{large 99}/10^{large 3}equiv -10^{large 3}cdot 9^{large 99} $ via $ 10^{large
6}equiv 1$
$n := 999999/27 = 7cdot 11cdot 13cdot 37.,$ mod each $p,,$ $9,$ has order $,3,5,3,9,$ so $,9^{large color{#c00}{45}}equiv 1pmod{!n}$
so $ 9^{large 99}!bmod 999999 = 27(3cdot 9^{large color{#c00}{97}}!bmod n) = 27(3cdot 9^{large 7}!bmod n) equiv 9^{large 9}!pmod{!999999}$
Hence we conclude $ 99999^{large 99}equiv -10^{large 3}cdot 9^{large 99}equiv {-}10^{large 3}cdot 9^{large 9}equiv 123579,pmod{!999999}$
answered Nov 21 at 22:35
Bill Dubuque
207k29189624
Due to $999999$ isn't a prime number you should say that $10$ has an inverse because it's coprime with $999999$.
– P De Donato
Nov 21 at 22:51
Then you can't arbitrarly pass from mod $999999$ to mod $n$.
– P De Donato
Nov 21 at 22:52
He's using the Chinese remainder theorem there. It's clear that $99999^{99} equiv 0 bmod 27$.
– Qiaochu Yuan
Nov 21 at 22:53
@PDeDonato That's obvious: $bmod 10^6-1!:, 10cdot 10^5equiv 1 $ so $10^{-1}equiv 10^5 $
– Bill Dubuque
Nov 21 at 22:54
I know it, but the answer isn't so clear.
– P De Donato
Nov 21 at 22:56
|
show 3 more comments
up vote
2
down vote
$!bmod 999999!:, 10cdot99999equiv -9 $ so $ 99999 equiv -9/10$
Thus $,99999^{large99}equiv -9^{large 99}/10^{large 99}equiv -9^{large 99}/10^{large 3}equiv -10^{large 3}cdot 9^{large 99} $ via $ 10^{large
6}equiv 1$
$n := 999999/27 = 7cdot 11cdot 13cdot 37.,$ mod each $p,,$ $9,$ has order $,3,5,3,9,$ so $,9^{large color{#c00}{45}}equiv 1pmod{!n}$
so $ 9^{large 99}!bmod 999999 = 27(3cdot 9^{large color{#c00}{97}}!bmod n) = 27(3cdot 9^{large 7}!bmod n) equiv 9^{large 9}!pmod{!999999}$
Hence we conclude $ 99999^{large 99}equiv -10^{large 3}cdot 9^{large 99}equiv {-}10^{large 3}cdot 9^{large 9}equiv 123579,pmod{!999999}$
answered Nov 21 at 22:35
Bill Dubuque
207k29189624
Due to $999999$ isn't a prime number you should say that $10$ has an inverse because it's coprime with $999999$.
– P De Donato
Nov 21 at 22:51
Then you can't arbitrarly pass from mod $999999$ to mod $n$.
– P De Donato
Nov 21 at 22:52
He's using the Chinese remainder theorem there. It's clear that $99999^{99} equiv 0 bmod 27$.
– Qiaochu Yuan
Nov 21 at 22:53
@PDeDonato That's obvious: $bmod 10^6-1!:, 10cdot 10^5equiv 1 $ so $10^{-1}equiv 10^5 $
– Bill Dubuque
Nov 21 at 22:54
I know it, but the answer isn't so clear.
– P De Donato
Nov 21 at 22:56
|
show 3 more comments
up vote
2
down vote
up vote
2
down vote
$!bmod 999999!:, 10cdot99999equiv -9 $ so $ 99999 equiv -9/10$
Thus $,99999^{large99}equiv -9^{large 99}/10^{large 99}equiv -9^{large 99}/10^{large 3}equiv -10^{large 3}cdot 9^{large 99} $ via $ 10^{large
6}equiv 1$
$n := 999999/27 = 7cdot 11cdot 13cdot 37.,$ mod each $p,,$ $9,$ has order $,3,5,3,9,$ so $,9^{large color{#c00}{45}}equiv 1pmod{!n}$
so $ 9^{large 99}!bmod 999999 = 27(3cdot 9^{large color{#c00}{97}}!bmod n) = 27(3cdot 9^{large 7}!bmod n) equiv 9^{large 9}!pmod{!999999}$
Hence we conclude $ 99999^{large 99}equiv -10^{large 3}cdot 9^{large 99}equiv {-}10^{large 3}cdot 9^{large 9}equiv 123579,pmod{!999999}$
answered Nov 21 at 22:35
Bill Dubuque
207k29189624
$!bmod 999999!:, 10cdot99999equiv -9 $ so $ 99999 equiv -9/10$
Thus $,99999^{large99}equiv -9^{large 99}/10^{large 99}equiv -9^{large 99}/10^{large 3}equiv -10^{large 3}cdot 9^{large 99} $ via $ 10^{large
6}equiv 1$
$n := 999999/27 = 7cdot 11cdot 13cdot 37.,$ mod each $p,,$ $9,$ has order $,3,5,3,9,$ so $,9^{large color{#c00}{45}}equiv 1pmod{!n}$
so $ 9^{large 99}!bmod 999999 = 27(3cdot 9^{large color{#c00}{97}}!bmod n) = 27(3cdot 9^{large 7}!bmod n) equiv 9^{large 9}!pmod{!999999}$
Hence we conclude $ 99999^{large 99}equiv -10^{large 3}cdot 9^{large 99}equiv {-}10^{large 3}cdot 9^{large 9}equiv 123579,pmod{!999999}$
answered Nov 21 at 22:35
Bill Dubuque
207k29189624
edited Nov 22 at 0:39
answered Nov 21 at 22:35
Bill Dubuque
207k29189624
answered Nov 21 at 22:35
Bill Dubuque
207k29189624
answered Nov 21 at 22:35
Bill Dubuque
207k29189624
207k29189624
Due to $999999$ isn't a prime number you should say that $10$ has an inverse because it's coprime with $999999$.
– P De Donato
Nov 21 at 22:51
Then you can't arbitrarly pass from mod $999999$ to mod $n$.
– P De Donato
Nov 21 at 22:52
He's using the Chinese remainder theorem there. It's clear that $99999^{99} equiv 0 bmod 27$.
– Qiaochu Yuan
Nov 21 at 22:53
@PDeDonato That's obvious: $bmod 10^6-1!:, 10cdot 10^5equiv 1 $ so $10^{-1}equiv 10^5 $
– Bill Dubuque
Nov 21 at 22:54
I know it, but the answer isn't so clear.
– P De Donato
Nov 21 at 22:56
|
show 3 more comments
Due to $999999$ isn't a prime number you should say that $10$ has an inverse because it's coprime with $999999$.
– P De Donato
Nov 21 at 22:51
Then you can't arbitrarly pass from mod $999999$ to mod $n$.
– P De Donato
Nov 21 at 22:52
He's using the Chinese remainder theorem there. It's clear that $99999^{99} equiv 0 bmod 27$.
– Qiaochu Yuan
Nov 21 at 22:53
@PDeDonato That's obvious: $bmod 10^6-1!:, 10cdot 10^5equiv 1 $ so $10^{-1}equiv 10^5 $
– Bill Dubuque
Nov 21 at 22:54
I know it, but the answer isn't so clear.
– P De Donato
Nov 21 at 22:56
Due to $999999$ isn't a prime number you should say that $10$ has an inverse because it's coprime with $999999$.
– P De Donato
Nov 21 at 22:51
Due to $999999$ isn't a prime number you should say that $10$ has an inverse because it's coprime with $999999$.
– P De Donato
Nov 21 at 22:51
Then you can't arbitrarly pass from mod $999999$ to mod $n$.
– P De Donato
Nov 21 at 22:52
Then you can't arbitrarly pass from mod $999999$ to mod $n$.
– P De Donato
Nov 21 at 22:52
He's using the Chinese remainder theorem there. It's clear that $99999^{99} equiv 0 bmod 27$.
– Qiaochu Yuan
Nov 21 at 22:53
He's using the Chinese remainder theorem there. It's clear that $99999^{99} equiv 0 bmod 27$.
– Qiaochu Yuan
Nov 21 at 22:53
@PDeDonato That's obvious: $bmod 10^6-1!:, 10cdot 10^5equiv 1 $ so $10^{-1}equiv 10^5 $
– Bill Dubuque
Nov 21 at 22:54
@PDeDonato That's obvious: $bmod 10^6-1!:, 10cdot 10^5equiv 1 $ so $10^{-1}equiv 10^5 $
– Bill Dubuque
Nov 21 at 22:54
I know it, but the answer isn't so clear.
– P De Donato
Nov 21 at 22:56
I know it, but the answer isn't so clear.
– P De Donato
Nov 21 at 22:56
|
show 3 more comments
up vote
2
down vote
We work in the ring $R=Bbb Z/N$, with operation modulo $N=999999=10^6-1$.
(Equalities below address computations in $R$.)
Then
$$
begin{aligned}
99999^{99}
&=(99999-999999)^{99} =(-900000)^{99}=-9^{99}cdot (10^5)^{99}\
&=-3^{198}cdot 10^{495}=-3^{198}cdot {underbrace{(10^6)}_{=1}}^{82}cdot 10^3=-3^{198}cdot 1000 .
end{aligned}
$$
Now the order of (the unit) $3$ in the ring
$Bbb Z/37037
=Bbb Z/(7cdot 11cdot 13cdot 37)
cong
(Bbb Z/7)times
(Bbb Z/11)times
(Bbb Z/13)times
(Bbb Z/37)
$
is $90$, but we need only the simpler information that $3^{180}$ is one modulo $37037$. This is so because $180$ is a multiple of $(7-1)$, $(11-1)$, $(13-1)$, and $(37-1)$. So instead of $3^{198}$ we write the smaller power $3^{18}=387420489$.
We finally search for a number which is $0$ modulo $27$, and also $-387420489000$ modulo $37037$, which is $12468$. After rearrangements modulo $3,9,27$ we get the result
$$123579 .$$
Note: A computer algebra system like sage delivers immediately
sage: Zmod(999999)(99999)^99
123579
answered Nov 22 at 0:42
dan_fulea
6,2101312
This is essentially the same as my answer, except I used the mod distributive law form of CRT (which makes it simpler).
– Bill Dubuque
Nov 22 at 0:45
I committed it now after typing in the train... Yes, same computation.
– dan_fulea
Nov 22 at 0:50
Thank you very much, it took some time but i eventually understood
– Girish venkata
Nov 26 at 18:12
add a comment |
up vote
2
down vote
We work in the ring $R=Bbb Z/N$, with operation modulo $N=999999=10^6-1$.
(Equalities below address computations in $R$.)
Then
$$
begin{aligned}
99999^{99}
&=(99999-999999)^{99} =(-900000)^{99}=-9^{99}cdot (10^5)^{99}\
&=-3^{198}cdot 10^{495}=-3^{198}cdot {underbrace{(10^6)}_{=1}}^{82}cdot 10^3=-3^{198}cdot 1000 .
end{aligned}
$$
Now the order of (the unit) $3$ in the ring
$Bbb Z/37037
=Bbb Z/(7cdot 11cdot 13cdot 37)
cong
(Bbb Z/7)times
(Bbb Z/11)times
(Bbb Z/13)times
(Bbb Z/37)
$
is $90$, but we need only the simpler information that $3^{180}$ is one modulo $37037$. This is so because $180$ is a multiple of $(7-1)$, $(11-1)$, $(13-1)$, and $(37-1)$. So instead of $3^{198}$ we write the smaller power $3^{18}=387420489$.
We finally search for a number which is $0$ modulo $27$, and also $-387420489000$ modulo $37037$, which is $12468$. After rearrangements modulo $3,9,27$ we get the result
$$123579 .$$
Note: A computer algebra system like sage delivers immediately
sage: Zmod(999999)(99999)^99
123579
answered Nov 22 at 0:42
dan_fulea
6,2101312
This is essentially the same as my answer, except I used the mod distributive law form of CRT (which makes it simpler).
– Bill Dubuque
Nov 22 at 0:45
I committed it now after typing in the train... Yes, same computation.
– dan_fulea
Nov 22 at 0:50
Thank you very much, it took some time but i eventually understood
– Girish venkata
Nov 26 at 18:12
add a comment |
up vote
2
down vote
up vote
2
down vote
We work in the ring $R=Bbb Z/N$, with operation modulo $N=999999=10^6-1$.
(Equalities below address computations in $R$.)
Then
$$
begin{aligned}
99999^{99}
&=(99999-999999)^{99} =(-900000)^{99}=-9^{99}cdot (10^5)^{99}\
&=-3^{198}cdot 10^{495}=-3^{198}cdot {underbrace{(10^6)}_{=1}}^{82}cdot 10^3=-3^{198}cdot 1000 .
end{aligned}
$$
Now the order of (the unit) $3$ in the ring
$Bbb Z/37037
=Bbb Z/(7cdot 11cdot 13cdot 37)
cong
(Bbb Z/7)times
(Bbb Z/11)times
(Bbb Z/13)times
(Bbb Z/37)
$
is $90$, but we need only the simpler information that $3^{180}$ is one modulo $37037$. This is so because $180$ is a multiple of $(7-1)$, $(11-1)$, $(13-1)$, and $(37-1)$. So instead of $3^{198}$ we write the smaller power $3^{18}=387420489$.
We finally search for a number which is $0$ modulo $27$, and also $-387420489000$ modulo $37037$, which is $12468$. After rearrangements modulo $3,9,27$ we get the result
$$123579 .$$
Note: A computer algebra system like sage delivers immediately
sage: Zmod(999999)(99999)^99
123579
answered Nov 22 at 0:42
dan_fulea
6,2101312
We work in the ring $R=Bbb Z/N$, with operation modulo $N=999999=10^6-1$.
(Equalities below address computations in $R$.)
Then
$$
begin{aligned}
99999^{99}
&=(99999-999999)^{99} =(-900000)^{99}=-9^{99}cdot (10^5)^{99}\
&=-3^{198}cdot 10^{495}=-3^{198}cdot {underbrace{(10^6)}_{=1}}^{82}cdot 10^3=-3^{198}cdot 1000 .
end{aligned}
$$
Now the order of (the unit) $3$ in the ring
$Bbb Z/37037
=Bbb Z/(7cdot 11cdot 13cdot 37)
cong
(Bbb Z/7)times
(Bbb Z/11)times
(Bbb Z/13)times
(Bbb Z/37)
$
is $90$, but we need only the simpler information that $3^{180}$ is one modulo $37037$. This is so because $180$ is a multiple of $(7-1)$, $(11-1)$, $(13-1)$, and $(37-1)$. So instead of $3^{198}$ we write the smaller power $3^{18}=387420489$.
We finally search for a number which is $0$ modulo $27$, and also $-387420489000$ modulo $37037$, which is $12468$. After rearrangements modulo $3,9,27$ we get the result
$$123579 .$$
Note: A computer algebra system like sage delivers immediately
sage: Zmod(999999)(99999)^99
123579
answered Nov 22 at 0:42
dan_fulea
6,2101312
answered Nov 22 at 0:42
dan_fulea
6,2101312
answered Nov 22 at 0:42
dan_fulea
6,2101312
answered Nov 22 at 0:42
dan_fulea
6,2101312
6,2101312
This is essentially the same as my answer, except I used the mod distributive law form of CRT (which makes it simpler).
– Bill Dubuque
Nov 22 at 0:45
I committed it now after typing in the train... Yes, same computation.
– dan_fulea
Nov 22 at 0:50
Thank you very much, it took some time but i eventually understood
– Girish venkata
Nov 26 at 18:12
add a comment |
This is essentially the same as my answer, except I used the mod distributive law form of CRT (which makes it simpler).
– Bill Dubuque
Nov 22 at 0:45
I committed it now after typing in the train... Yes, same computation.
– dan_fulea
Nov 22 at 0:50
Thank you very much, it took some time but i eventually understood
– Girish venkata
Nov 26 at 18:12
This is essentially the same as my answer, except I used the mod distributive law form of CRT (which makes it simpler).
– Bill Dubuque
Nov 22 at 0:45
This is essentially the same as my answer, except I used the mod distributive law form of CRT (which makes it simpler).
– Bill Dubuque
Nov 22 at 0:45
I committed it now after typing in the train... Yes, same computation.
– dan_fulea
Nov 22 at 0:50
I committed it now after typing in the train... Yes, same computation.
– dan_fulea
Nov 22 at 0:50
Thank you very much, it took some time but i eventually understood
– Girish venkata
Nov 26 at 18:12
Thank you very much, it took some time but i eventually understood
– Girish venkata
Nov 26 at 18:12
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3008349%2fwhats-the-remainder-if-99-99999-is-divided-by-999-999%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
Hint: relabel $999999$ as $x$. What's the remainder after division?
– John Douma
Nov 21 at 20:58
1
Computer says 123579, but I don't see elegant trick besides laboriously doing square-and-multiply
– Hagen von Eitzen
Nov 21 at 21:07
@JohnDouma: I don't get it.
– TonyK
Nov 21 at 23:21
@Hagen Your hardware is consistent with my wetware - see my answer.
– Bill Dubuque
Nov 21 at 23:34
@TonyK I misread the question. I thought both numbers consisted of six $9$s.
– John Douma
Nov 21 at 23:39