What's the remainder if $99{,}999^{99}$ is divided by $999{,}999$?
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 '18 at 0:01
Barry Cipra
59.1k653124
asked Nov 21 '18 at 20:56
Girish venkata
212
|
show 2 more comments
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 '18 at 0:01
Barry Cipra
59.1k653124
asked Nov 21 '18 at 20:56
Girish venkata
212
Hint: relabel $999999$ as $x$. What's the remainder after division?
– John Douma
Nov 21 '18 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 '18 at 21:07
@JohnDouma: I don't get it.
– TonyK
Nov 21 '18 at 23:21
@Hagen Your hardware is consistent with my wetware - see my answer.
– Bill Dubuque
Nov 21 '18 at 23:34
@TonyK I misread the question. I thought both numbers consisted of six $9$s.
– John Douma
Nov 21 '18 at 23:39
|
show 2 more comments
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 '18 at 0:01
Barry Cipra
59.1k653124
asked Nov 21 '18 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 '18 at 0:01
Barry Cipra
59.1k653124
asked Nov 21 '18 at 20:56
Girish venkata
212
edited Nov 22 '18 at 0:01
Barry Cipra
59.1k653124
asked Nov 21 '18 at 20:56
Girish venkata
212
edited Nov 22 '18 at 0:01
Barry Cipra
59.1k653124
edited Nov 22 '18 at 0:01
Barry Cipra
59.1k653124
edited Nov 22 '18 at 0:01
Barry Cipra
59.1k653124
59.1k653124
asked Nov 21 '18 at 20:56
Girish venkata
212
asked Nov 21 '18 at 20:56
Girish venkata
212
asked Nov 21 '18 at 20:56
Girish venkata
212
212
Hint: relabel $999999$ as $x$. What's the remainder after division?
– John Douma
Nov 21 '18 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 '18 at 21:07
@JohnDouma: I don't get it.
– TonyK
Nov 21 '18 at 23:21
@Hagen Your hardware is consistent with my wetware - see my answer.
– Bill Dubuque
Nov 21 '18 at 23:34
@TonyK I misread the question. I thought both numbers consisted of six $9$s.
– John Douma
Nov 21 '18 at 23:39
|
show 2 more comments
Hint: relabel $999999$ as $x$. What's the remainder after division?
– John Douma
Nov 21 '18 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 '18 at 21:07
@JohnDouma: I don't get it.
– TonyK
Nov 21 '18 at 23:21
@Hagen Your hardware is consistent with my wetware - see my answer.
– Bill Dubuque
Nov 21 '18 at 23:34
@TonyK I misread the question. I thought both numbers consisted of six $9$s.
– John Douma
Nov 21 '18 at 23:39
Hint: relabel $999999$ as $x$. What's the remainder after division?
– John Douma
Nov 21 '18 at 20:58
Hint: relabel $999999$ as $x$. What's the remainder after division?
– John Douma
Nov 21 '18 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 '18 at 21:07
Computer says 123579, but I don't see elegant trick besides laboriously doing square-and-multiply
– Hagen von Eitzen
Nov 21 '18 at 21:07
@JohnDouma: I don't get it.
– TonyK
Nov 21 '18 at 23:21
@JohnDouma: I don't get it.
– TonyK
Nov 21 '18 at 23:21
@Hagen Your hardware is consistent with my wetware - see my answer.
– Bill Dubuque
Nov 21 '18 at 23:34
@Hagen Your hardware is consistent with my wetware - see my answer.
– Bill Dubuque
Nov 21 '18 at 23:34
@TonyK I misread the question. I thought both numbers consisted of six $9$s.
– John Douma
Nov 21 '18 at 23:39
@TonyK I misread the question. I thought both numbers consisted of six $9$s.
– John Douma
Nov 21 '18 at 23:39
|
show 2 more comments
2 Answers
2
active
oldest
votes
$!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 '18 at 22:35
Bill Dubuque
209k29190629
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 '18 at 22:51
Then you can't arbitrarly pass from mod $999999$ to mod $n$.
– P De Donato
Nov 21 '18 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 '18 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 '18 at 22:54
I know it, but the answer isn't so clear.
– P De Donato
Nov 21 '18 at 22:56
|
show 3 more comments
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 '18 at 0:42
dan_fulea
6,2301312
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 '18 at 0:45
I committed it now after typing in the train... Yes, same computation.
– dan_fulea
Nov 22 '18 at 0:50
Thank you very much, it took some time but i eventually understood
– Girish venkata
Nov 26 '18 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',
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%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
$!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 '18 at 22:35
Bill Dubuque
209k29190629
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 '18 at 22:51
Then you can't arbitrarly pass from mod $999999$ to mod $n$.
– P De Donato
Nov 21 '18 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 '18 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 '18 at 22:54
I know it, but the answer isn't so clear.
– P De Donato
Nov 21 '18 at 22:56
|
show 3 more comments
$!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 '18 at 22:35
Bill Dubuque
209k29190629
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 '18 at 22:51
Then you can't arbitrarly pass from mod $999999$ to mod $n$.
– P De Donato
Nov 21 '18 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 '18 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 '18 at 22:54
I know it, but the answer isn't so clear.
– P De Donato
Nov 21 '18 at 22:56
|
show 3 more comments
$!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 '18 at 22:35
Bill Dubuque
209k29190629
$!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 '18 at 22:35
Bill Dubuque
209k29190629
edited Nov 22 '18 at 0:39
answered Nov 21 '18 at 22:35
Bill Dubuque
209k29190629
answered Nov 21 '18 at 22:35
Bill Dubuque
209k29190629
answered Nov 21 '18 at 22:35
Bill Dubuque
209k29190629
209k29190629
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 '18 at 22:51
Then you can't arbitrarly pass from mod $999999$ to mod $n$.
– P De Donato
Nov 21 '18 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 '18 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 '18 at 22:54
I know it, but the answer isn't so clear.
– P De Donato
Nov 21 '18 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 '18 at 22:51
Then you can't arbitrarly pass from mod $999999$ to mod $n$.
– P De Donato
Nov 21 '18 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 '18 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 '18 at 22:54
I know it, but the answer isn't so clear.
– P De Donato
Nov 21 '18 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 '18 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 '18 at 22:51
Then you can't arbitrarly pass from mod $999999$ to mod $n$.
– P De Donato
Nov 21 '18 at 22:52
Then you can't arbitrarly pass from mod $999999$ to mod $n$.
– P De Donato
Nov 21 '18 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 '18 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 '18 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 '18 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 '18 at 22:54
I know it, but the answer isn't so clear.
– P De Donato
Nov 21 '18 at 22:56
I know it, but the answer isn't so clear.
– P De Donato
Nov 21 '18 at 22:56
|
show 3 more comments
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 '18 at 0:42
dan_fulea
6,2301312
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 '18 at 0:45
I committed it now after typing in the train... Yes, same computation.
– dan_fulea
Nov 22 '18 at 0:50
Thank you very much, it took some time but i eventually understood
– Girish venkata
Nov 26 '18 at 18:12
add a comment |
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 '18 at 0:42
dan_fulea
6,2301312
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 '18 at 0:45
I committed it now after typing in the train... Yes, same computation.
– dan_fulea
Nov 22 '18 at 0:50
Thank you very much, it took some time but i eventually understood
– Girish venkata
Nov 26 '18 at 18:12
add a comment |
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 '18 at 0:42
dan_fulea
6,2301312
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 '18 at 0:42
dan_fulea
6,2301312
answered Nov 22 '18 at 0:42
dan_fulea
6,2301312
answered Nov 22 '18 at 0:42
dan_fulea
6,2301312
answered Nov 22 '18 at 0:42
dan_fulea
6,2301312
6,2301312
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 '18 at 0:45
I committed it now after typing in the train... Yes, same computation.
– dan_fulea
Nov 22 '18 at 0:50
Thank you very much, it took some time but i eventually understood
– Girish venkata
Nov 26 '18 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 '18 at 0:45
I committed it now after typing in the train... Yes, same computation.
– dan_fulea
Nov 22 '18 at 0:50
Thank you very much, it took some time but i eventually understood
– Girish venkata
Nov 26 '18 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 '18 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 '18 at 0:45
I committed it now after typing in the train... Yes, same computation.
– dan_fulea
Nov 22 '18 at 0:50
I committed it now after typing in the train... Yes, same computation.
– dan_fulea
Nov 22 '18 at 0:50
Thank you very much, it took some time but i eventually understood
– Girish venkata
Nov 26 '18 at 18:12
Thank you very much, it took some time but i eventually understood
– Girish venkata
Nov 26 '18 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 '18 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 '18 at 21:07
@JohnDouma: I don't get it.
– TonyK
Nov 21 '18 at 23:21
@Hagen Your hardware is consistent with my wetware - see my answer.
– Bill Dubuque
Nov 21 '18 at 23:34
@TonyK I misread the question. I thought both numbers consisted of six $9$s.
– John Douma
Nov 21 '18 at 23:39