Calculate $100^{1207} mod 63$
$begingroup$
I try to solve this question: Calculate $100^{1207} mod 63$. There is the hint that i should calculate $100^{1207} mod 7$, $100^{1207} mod 9$, which is easy for me, but I don't see the relationship between this to questions. I guess it must have something to do with the fact, that $7*9 = 63$.
modular-arithmetic
edited Jan 20 at 10:38
Bernard
121k740116
asked Jan 20 at 9:09
eriaeeriae
112
$endgroup$
add a comment |
$begingroup$
I try to solve this question: Calculate $100^{1207} mod 63$. There is the hint that i should calculate $100^{1207} mod 7$, $100^{1207} mod 9$, which is easy for me, but I don't see the relationship between this to questions. I guess it must have something to do with the fact, that $7*9 = 63$.
modular-arithmetic
edited Jan 20 at 10:38
Bernard
121k740116
asked Jan 20 at 9:09
eriaeeriae
112
$endgroup$
1
$begingroup$
Perhaps you should learn the Chinese Remainder Theorem
$endgroup$
– crskhr
Jan 20 at 9:12
add a comment |
$begingroup$
I try to solve this question: Calculate $100^{1207} mod 63$. There is the hint that i should calculate $100^{1207} mod 7$, $100^{1207} mod 9$, which is easy for me, but I don't see the relationship between this to questions. I guess it must have something to do with the fact, that $7*9 = 63$.
modular-arithmetic
edited Jan 20 at 10:38
Bernard
121k740116
asked Jan 20 at 9:09
eriaeeriae
112
$endgroup$
I try to solve this question: Calculate $100^{1207} mod 63$. There is the hint that i should calculate $100^{1207} mod 7$, $100^{1207} mod 9$, which is easy for me, but I don't see the relationship between this to questions. I guess it must have something to do with the fact, that $7*9 = 63$.
modular-arithmetic
modular-arithmetic
edited Jan 20 at 10:38
Bernard
121k740116
asked Jan 20 at 9:09
eriaeeriae
112
edited Jan 20 at 10:38
Bernard
121k740116
asked Jan 20 at 9:09
eriaeeriae
112
edited Jan 20 at 10:38
Bernard
121k740116
edited Jan 20 at 10:38
Bernard
121k740116
edited Jan 20 at 10:38
Bernard
121k740116
121k740116
asked Jan 20 at 9:09
eriaeeriae
112
asked Jan 20 at 9:09
eriaeeriae
112
asked Jan 20 at 9:09
eriaeeriae
112
112
1
$begingroup$
Perhaps you should learn the Chinese Remainder Theorem
$endgroup$
– crskhr
Jan 20 at 9:12
add a comment |
1
$begingroup$
Perhaps you should learn the Chinese Remainder Theorem
$endgroup$
– crskhr
Jan 20 at 9:12
1
1
$begingroup$
Perhaps you should learn the Chinese Remainder Theorem
$endgroup$
– crskhr
Jan 20 at 9:12
$begingroup$
Perhaps you should learn the Chinese Remainder Theorem
$endgroup$
– crskhr
Jan 20 at 9:12
add a comment |
6 Answers
6
active
oldest
votes
$begingroup$
Note that $$100^3equiv 1 mod 63$$
answered Jan 20 at 9:13
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
75.7k42866
$endgroup$
add a comment |
$begingroup$
Well, its the Chinese remainder theorem:
$$xequiv a mod 7quad text{and}quad xequiv b mod 9,quad a,bin{Bbb Z}.$$
The solution is unique in the range of $0leq xleq 63-1$.
answered Jan 20 at 9:12
WuestenfuxWuestenfux
4,7331413
$endgroup$
add a comment |
$begingroup$
First note that $100$ and $63$ are coprime, and that $phi(63)=phi(3^2)phi(7)=6^2$.
So
$$100^{1207}=4^{1207},25^{1207}equiv 4^{1207bmod 36},25^{1207bmod36}=4^{19},25^{19}mod 63.$$
On the other hand, $4$ has order 3$bmod 63$, so
$$4^{19},25^{19}equiv 4cdot5^{38}equiv4cdot5^{38bmod 36}=4cdot5^2mod 63.$$
answered Jan 20 at 10:55
BernardBernard
121k740116
$endgroup$
add a comment |
$begingroup$
The Chinese remainder theorem tells us that if we know a number $x$ modulo $7$ and
modulo $9$ we also know $x$ modulo $7times 9 = 63$ because $7$ and $9$ are coprime. It even gives a formula to compute this $x$ modulo $63$, given these other two.
answered Jan 20 at 10:10
Henno BrandsmaHenno Brandsma
110k347117
$endgroup$
add a comment |
$begingroup$
It certainly has to do with the fact that $7*9=64$ and also with the fact that the greatest common divisor of 7 and 9 is 1 (they are coprime). As explained by others, the Chinese Remainder Theorem can help solving this problem. It states the following:
Chinese Remainder Theorem
Let $m_1, ..., m_n$ be pairwise coprime ($gcd(m_i, m_j) = 1$ when $i
> neq j$). Then the system of $n$ equations
$$x equiv a_1 mod{m_1}\ ... \ x equiv a_n mod{m_n}$$
has a unique solution for $x$ modulo $M$ where $M = m_1dotsm m_n$.
So for this particular problem you can find $a_1$ and $a_2$ for $m_1 = 7$ and $m_2 = 9$ and then look for an $0 < x < 63$ that satisfies the equations for $m_1$ and $m_2$. Here are several methods you can use for this (Search by sieving might be the best for this case).
A completely different solution might use the fact that $100^3 equiv 1mod{63}$.
answered Jan 20 at 12:43
salvaricosalvarico
665
$endgroup$
add a comment |
$begingroup$
Using http://mathworld.wolfram.com/CarmichaelFunction.html, $$lambda(63)=6$$
and $(100,63)=1$ and $1207equiv1pmod6$
$implies100^{1207}equiv100^1pmod{63}equiv?$
More generally,
$a^nequiv a^{npmod6}pmod{63}$ for $(a,63)=1$
answered Jan 21 at 3:31
lab bhattacharjeelab bhattacharjee
226k15157275
$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');
});
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%2f3080343%2fcalculate-1001207-mod-63%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
6 Answers
6
active
oldest
votes
6 Answers
6
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Note that $$100^3equiv 1 mod 63$$
answered Jan 20 at 9:13
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
75.7k42866
$endgroup$
add a comment |
$begingroup$
Note that $$100^3equiv 1 mod 63$$
answered Jan 20 at 9:13
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
75.7k42866
$endgroup$
add a comment |
$begingroup$
Note that $$100^3equiv 1 mod 63$$
answered Jan 20 at 9:13
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
75.7k42866
$endgroup$
Note that $$100^3equiv 1 mod 63$$
answered Jan 20 at 9:13
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
75.7k42866
answered Jan 20 at 9:13
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
75.7k42866
answered Jan 20 at 9:13
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
75.7k42866
answered Jan 20 at 9:13
Dr. Sonnhard GraubnerDr. Sonnhard Graubner
75.7k42866
75.7k42866
add a comment |
add a comment |
$begingroup$
Well, its the Chinese remainder theorem:
$$xequiv a mod 7quad text{and}quad xequiv b mod 9,quad a,bin{Bbb Z}.$$
The solution is unique in the range of $0leq xleq 63-1$.
answered Jan 20 at 9:12
WuestenfuxWuestenfux
4,7331413
$endgroup$
add a comment |
$begingroup$
Well, its the Chinese remainder theorem:
$$xequiv a mod 7quad text{and}quad xequiv b mod 9,quad a,bin{Bbb Z}.$$
The solution is unique in the range of $0leq xleq 63-1$.
answered Jan 20 at 9:12
WuestenfuxWuestenfux
4,7331413
$endgroup$
add a comment |
$begingroup$
Well, its the Chinese remainder theorem:
$$xequiv a mod 7quad text{and}quad xequiv b mod 9,quad a,bin{Bbb Z}.$$
The solution is unique in the range of $0leq xleq 63-1$.
answered Jan 20 at 9:12
WuestenfuxWuestenfux
4,7331413
$endgroup$
Well, its the Chinese remainder theorem:
$$xequiv a mod 7quad text{and}quad xequiv b mod 9,quad a,bin{Bbb Z}.$$
The solution is unique in the range of $0leq xleq 63-1$.
answered Jan 20 at 9:12
WuestenfuxWuestenfux
4,7331413
answered Jan 20 at 9:12
WuestenfuxWuestenfux
4,7331413
answered Jan 20 at 9:12
WuestenfuxWuestenfux
4,7331413
answered Jan 20 at 9:12
WuestenfuxWuestenfux
4,7331413
4,7331413
add a comment |
add a comment |
$begingroup$
First note that $100$ and $63$ are coprime, and that $phi(63)=phi(3^2)phi(7)=6^2$.
So
$$100^{1207}=4^{1207},25^{1207}equiv 4^{1207bmod 36},25^{1207bmod36}=4^{19},25^{19}mod 63.$$
On the other hand, $4$ has order 3$bmod 63$, so
$$4^{19},25^{19}equiv 4cdot5^{38}equiv4cdot5^{38bmod 36}=4cdot5^2mod 63.$$
answered Jan 20 at 10:55
BernardBernard
121k740116
$endgroup$
add a comment |
$begingroup$
First note that $100$ and $63$ are coprime, and that $phi(63)=phi(3^2)phi(7)=6^2$.
So
$$100^{1207}=4^{1207},25^{1207}equiv 4^{1207bmod 36},25^{1207bmod36}=4^{19},25^{19}mod 63.$$
On the other hand, $4$ has order 3$bmod 63$, so
$$4^{19},25^{19}equiv 4cdot5^{38}equiv4cdot5^{38bmod 36}=4cdot5^2mod 63.$$
answered Jan 20 at 10:55
BernardBernard
121k740116
$endgroup$
add a comment |
$begingroup$
First note that $100$ and $63$ are coprime, and that $phi(63)=phi(3^2)phi(7)=6^2$.
So
$$100^{1207}=4^{1207},25^{1207}equiv 4^{1207bmod 36},25^{1207bmod36}=4^{19},25^{19}mod 63.$$
On the other hand, $4$ has order 3$bmod 63$, so
$$4^{19},25^{19}equiv 4cdot5^{38}equiv4cdot5^{38bmod 36}=4cdot5^2mod 63.$$
answered Jan 20 at 10:55
BernardBernard
121k740116
$endgroup$
First note that $100$ and $63$ are coprime, and that $phi(63)=phi(3^2)phi(7)=6^2$.
So
$$100^{1207}=4^{1207},25^{1207}equiv 4^{1207bmod 36},25^{1207bmod36}=4^{19},25^{19}mod 63.$$
On the other hand, $4$ has order 3$bmod 63$, so
$$4^{19},25^{19}equiv 4cdot5^{38}equiv4cdot5^{38bmod 36}=4cdot5^2mod 63.$$
answered Jan 20 at 10:55
BernardBernard
121k740116
answered Jan 20 at 10:55
BernardBernard
121k740116
answered Jan 20 at 10:55
BernardBernard
121k740116
answered Jan 20 at 10:55
BernardBernard
121k740116
121k740116
add a comment |
add a comment |
$begingroup$
The Chinese remainder theorem tells us that if we know a number $x$ modulo $7$ and
modulo $9$ we also know $x$ modulo $7times 9 = 63$ because $7$ and $9$ are coprime. It even gives a formula to compute this $x$ modulo $63$, given these other two.
answered Jan 20 at 10:10
Henno BrandsmaHenno Brandsma
110k347117
$endgroup$
add a comment |
$begingroup$
The Chinese remainder theorem tells us that if we know a number $x$ modulo $7$ and
modulo $9$ we also know $x$ modulo $7times 9 = 63$ because $7$ and $9$ are coprime. It even gives a formula to compute this $x$ modulo $63$, given these other two.
answered Jan 20 at 10:10
Henno BrandsmaHenno Brandsma
110k347117
$endgroup$
add a comment |
$begingroup$
The Chinese remainder theorem tells us that if we know a number $x$ modulo $7$ and
modulo $9$ we also know $x$ modulo $7times 9 = 63$ because $7$ and $9$ are coprime. It even gives a formula to compute this $x$ modulo $63$, given these other two.
answered Jan 20 at 10:10
Henno BrandsmaHenno Brandsma
110k347117
$endgroup$
The Chinese remainder theorem tells us that if we know a number $x$ modulo $7$ and
modulo $9$ we also know $x$ modulo $7times 9 = 63$ because $7$ and $9$ are coprime. It even gives a formula to compute this $x$ modulo $63$, given these other two.
answered Jan 20 at 10:10
Henno BrandsmaHenno Brandsma
110k347117
answered Jan 20 at 10:10
Henno BrandsmaHenno Brandsma
110k347117
answered Jan 20 at 10:10
Henno BrandsmaHenno Brandsma
110k347117
answered Jan 20 at 10:10
Henno BrandsmaHenno Brandsma
110k347117
110k347117
add a comment |
add a comment |
$begingroup$
It certainly has to do with the fact that $7*9=64$ and also with the fact that the greatest common divisor of 7 and 9 is 1 (they are coprime). As explained by others, the Chinese Remainder Theorem can help solving this problem. It states the following:
Chinese Remainder Theorem
Let $m_1, ..., m_n$ be pairwise coprime ($gcd(m_i, m_j) = 1$ when $i
> neq j$). Then the system of $n$ equations
$$x equiv a_1 mod{m_1}\ ... \ x equiv a_n mod{m_n}$$
has a unique solution for $x$ modulo $M$ where $M = m_1dotsm m_n$.
So for this particular problem you can find $a_1$ and $a_2$ for $m_1 = 7$ and $m_2 = 9$ and then look for an $0 < x < 63$ that satisfies the equations for $m_1$ and $m_2$. Here are several methods you can use for this (Search by sieving might be the best for this case).
A completely different solution might use the fact that $100^3 equiv 1mod{63}$.
answered Jan 20 at 12:43
salvaricosalvarico
665
$endgroup$
add a comment |
$begingroup$
It certainly has to do with the fact that $7*9=64$ and also with the fact that the greatest common divisor of 7 and 9 is 1 (they are coprime). As explained by others, the Chinese Remainder Theorem can help solving this problem. It states the following:
Chinese Remainder Theorem
Let $m_1, ..., m_n$ be pairwise coprime ($gcd(m_i, m_j) = 1$ when $i
> neq j$). Then the system of $n$ equations
$$x equiv a_1 mod{m_1}\ ... \ x equiv a_n mod{m_n}$$
has a unique solution for $x$ modulo $M$ where $M = m_1dotsm m_n$.
So for this particular problem you can find $a_1$ and $a_2$ for $m_1 = 7$ and $m_2 = 9$ and then look for an $0 < x < 63$ that satisfies the equations for $m_1$ and $m_2$. Here are several methods you can use for this (Search by sieving might be the best for this case).
A completely different solution might use the fact that $100^3 equiv 1mod{63}$.
answered Jan 20 at 12:43
salvaricosalvarico
665
$endgroup$
add a comment |
$begingroup$
It certainly has to do with the fact that $7*9=64$ and also with the fact that the greatest common divisor of 7 and 9 is 1 (they are coprime). As explained by others, the Chinese Remainder Theorem can help solving this problem. It states the following:
Chinese Remainder Theorem
Let $m_1, ..., m_n$ be pairwise coprime ($gcd(m_i, m_j) = 1$ when $i
> neq j$). Then the system of $n$ equations
$$x equiv a_1 mod{m_1}\ ... \ x equiv a_n mod{m_n}$$
has a unique solution for $x$ modulo $M$ where $M = m_1dotsm m_n$.
So for this particular problem you can find $a_1$ and $a_2$ for $m_1 = 7$ and $m_2 = 9$ and then look for an $0 < x < 63$ that satisfies the equations for $m_1$ and $m_2$. Here are several methods you can use for this (Search by sieving might be the best for this case).
A completely different solution might use the fact that $100^3 equiv 1mod{63}$.
answered Jan 20 at 12:43
salvaricosalvarico
665
$endgroup$
It certainly has to do with the fact that $7*9=64$ and also with the fact that the greatest common divisor of 7 and 9 is 1 (they are coprime). As explained by others, the Chinese Remainder Theorem can help solving this problem. It states the following:
Chinese Remainder Theorem
Let $m_1, ..., m_n$ be pairwise coprime ($gcd(m_i, m_j) = 1$ when $i
> neq j$). Then the system of $n$ equations
$$x equiv a_1 mod{m_1}\ ... \ x equiv a_n mod{m_n}$$
has a unique solution for $x$ modulo $M$ where $M = m_1dotsm m_n$.
So for this particular problem you can find $a_1$ and $a_2$ for $m_1 = 7$ and $m_2 = 9$ and then look for an $0 < x < 63$ that satisfies the equations for $m_1$ and $m_2$. Here are several methods you can use for this (Search by sieving might be the best for this case).
A completely different solution might use the fact that $100^3 equiv 1mod{63}$.
answered Jan 20 at 12:43
salvaricosalvarico
665
answered Jan 20 at 12:43
salvaricosalvarico
665
answered Jan 20 at 12:43
salvaricosalvarico
665
answered Jan 20 at 12:43
salvaricosalvarico
665
665
add a comment |
add a comment |
$begingroup$
Using http://mathworld.wolfram.com/CarmichaelFunction.html, $$lambda(63)=6$$
and $(100,63)=1$ and $1207equiv1pmod6$
$implies100^{1207}equiv100^1pmod{63}equiv?$
More generally,
$a^nequiv a^{npmod6}pmod{63}$ for $(a,63)=1$
answered Jan 21 at 3:31
lab bhattacharjeelab bhattacharjee
226k15157275
$endgroup$
add a comment |
$begingroup$
Using http://mathworld.wolfram.com/CarmichaelFunction.html, $$lambda(63)=6$$
and $(100,63)=1$ and $1207equiv1pmod6$
$implies100^{1207}equiv100^1pmod{63}equiv?$
More generally,
$a^nequiv a^{npmod6}pmod{63}$ for $(a,63)=1$
answered Jan 21 at 3:31
lab bhattacharjeelab bhattacharjee
226k15157275
$endgroup$
add a comment |
$begingroup$
Using http://mathworld.wolfram.com/CarmichaelFunction.html, $$lambda(63)=6$$
and $(100,63)=1$ and $1207equiv1pmod6$
$implies100^{1207}equiv100^1pmod{63}equiv?$
More generally,
$a^nequiv a^{npmod6}pmod{63}$ for $(a,63)=1$
answered Jan 21 at 3:31
lab bhattacharjeelab bhattacharjee
226k15157275
$endgroup$
Using http://mathworld.wolfram.com/CarmichaelFunction.html, $$lambda(63)=6$$
and $(100,63)=1$ and $1207equiv1pmod6$
$implies100^{1207}equiv100^1pmod{63}equiv?$
More generally,
$a^nequiv a^{npmod6}pmod{63}$ for $(a,63)=1$
answered Jan 21 at 3:31
lab bhattacharjeelab bhattacharjee
226k15157275
answered Jan 21 at 3:31
lab bhattacharjeelab bhattacharjee
226k15157275
answered Jan 21 at 3:31
lab bhattacharjeelab bhattacharjee
226k15157275
answered Jan 21 at 3:31
lab bhattacharjeelab bhattacharjee
226k15157275
226k15157275
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');
});
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%2f3080343%2fcalculate-1001207-mod-63%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
1
$begingroup$
Perhaps you should learn the Chinese Remainder Theorem
$endgroup$
– crskhr
Jan 20 at 9:12