Mixing
What is the remainder of $3^{13} div 25$ by hand using Euler's theorem?
Well, I know how to solve this problem by using some basic stuff:
$3^3 equiv 2 rightarrow 3^{12} equiv 2^4 rightarrow 3^{13} equiv 48equiv 23pmod{25}$
But what I'm trying to do is to solve this ONLY using Euler's theorem.
What I tried was (all congruences are in mod 25):
$phi(25)=20, space rightarrow 3^{13}equiv3^{13mod{phi(25)}}equiv3^{13mod20}$
which still gives me $3^{13}$ and there's no way I could calculate that.
So I tried to raise both sides of the starting equation to the power of two so I get something easier to calculate:
$3^{26}equiv x^2 equiv 3^{26mod20}equiv3^6$ and then $3^6equiv(3^{3})^2equiv27^2equiv2^2equiv4$ therefore $x^2=4 rightarrow x=2,-2$, hence $3^{13} equiv 2$ or $3^{13}equiv23$ (And we know that the correct answer is 23)
We can verify which one of $2$ and $23$ is the correct answer using Euler's theorem $a^{phi(n)}equiv1pmod{n}$ but I'm trying to find a shorter, possibly smarter answer which DOES use Euler's theorem. Any thoughts?
modular-arithmetic totient-function
edited Nov 20 '18 at 16:03
amWhy
192k28224439
asked Nov 20 '18 at 15:51
Sean Goudarzi
1326
add a comment |
Well, I know how to solve this problem by using some basic stuff:
$3^3 equiv 2 rightarrow 3^{12} equiv 2^4 rightarrow 3^{13} equiv 48equiv 23pmod{25}$
But what I'm trying to do is to solve this ONLY using Euler's theorem.
What I tried was (all congruences are in mod 25):
$phi(25)=20, space rightarrow 3^{13}equiv3^{13mod{phi(25)}}equiv3^{13mod20}$
which still gives me $3^{13}$ and there's no way I could calculate that.
So I tried to raise both sides of the starting equation to the power of two so I get something easier to calculate:
$3^{26}equiv x^2 equiv 3^{26mod20}equiv3^6$ and then $3^6equiv(3^{3})^2equiv27^2equiv2^2equiv4$ therefore $x^2=4 rightarrow x=2,-2$, hence $3^{13} equiv 2$ or $3^{13}equiv23$ (And we know that the correct answer is 23)
We can verify which one of $2$ and $23$ is the correct answer using Euler's theorem $a^{phi(n)}equiv1pmod{n}$ but I'm trying to find a shorter, possibly smarter answer which DOES use Euler's theorem. Any thoughts?
modular-arithmetic totient-function
edited Nov 20 '18 at 16:03
amWhy
192k28224439
asked Nov 20 '18 at 15:51
Sean Goudarzi
1326
$!!bmod 25!: 3^{large 20}equiv 1,Rightarrow,3^{large 10}equiv pm1,,$ must be $-1$ to be correct $!bmod 5. $ Equivalently, check your $2$ cases $!bmod 5 $
– Bill Dubuque
Nov 20 '18 at 16:57
add a comment |
Well, I know how to solve this problem by using some basic stuff:
$3^3 equiv 2 rightarrow 3^{12} equiv 2^4 rightarrow 3^{13} equiv 48equiv 23pmod{25}$
But what I'm trying to do is to solve this ONLY using Euler's theorem.
What I tried was (all congruences are in mod 25):
$phi(25)=20, space rightarrow 3^{13}equiv3^{13mod{phi(25)}}equiv3^{13mod20}$
which still gives me $3^{13}$ and there's no way I could calculate that.
So I tried to raise both sides of the starting equation to the power of two so I get something easier to calculate:
$3^{26}equiv x^2 equiv 3^{26mod20}equiv3^6$ and then $3^6equiv(3^{3})^2equiv27^2equiv2^2equiv4$ therefore $x^2=4 rightarrow x=2,-2$, hence $3^{13} equiv 2$ or $3^{13}equiv23$ (And we know that the correct answer is 23)
We can verify which one of $2$ and $23$ is the correct answer using Euler's theorem $a^{phi(n)}equiv1pmod{n}$ but I'm trying to find a shorter, possibly smarter answer which DOES use Euler's theorem. Any thoughts?
modular-arithmetic totient-function
edited Nov 20 '18 at 16:03
amWhy
192k28224439
asked Nov 20 '18 at 15:51
Sean Goudarzi
1326
Well, I know how to solve this problem by using some basic stuff:
$3^3 equiv 2 rightarrow 3^{12} equiv 2^4 rightarrow 3^{13} equiv 48equiv 23pmod{25}$
But what I'm trying to do is to solve this ONLY using Euler's theorem.
What I tried was (all congruences are in mod 25):
$phi(25)=20, space rightarrow 3^{13}equiv3^{13mod{phi(25)}}equiv3^{13mod20}$
which still gives me $3^{13}$ and there's no way I could calculate that.
So I tried to raise both sides of the starting equation to the power of two so I get something easier to calculate:
$3^{26}equiv x^2 equiv 3^{26mod20}equiv3^6$ and then $3^6equiv(3^{3})^2equiv27^2equiv2^2equiv4$ therefore $x^2=4 rightarrow x=2,-2$, hence $3^{13} equiv 2$ or $3^{13}equiv23$ (And we know that the correct answer is 23)
We can verify which one of $2$ and $23$ is the correct answer using Euler's theorem $a^{phi(n)}equiv1pmod{n}$ but I'm trying to find a shorter, possibly smarter answer which DOES use Euler's theorem. Any thoughts?
modular-arithmetic totient-function
modular-arithmetic totient-function
edited Nov 20 '18 at 16:03
amWhy
192k28224439
asked Nov 20 '18 at 15:51
Sean Goudarzi
1326
edited Nov 20 '18 at 16:03
amWhy
192k28224439
asked Nov 20 '18 at 15:51
Sean Goudarzi
1326
edited Nov 20 '18 at 16:03
amWhy
192k28224439
edited Nov 20 '18 at 16:03
amWhy
192k28224439
edited Nov 20 '18 at 16:03
amWhy
192k28224439
192k28224439
asked Nov 20 '18 at 15:51
Sean Goudarzi
1326
asked Nov 20 '18 at 15:51
Sean Goudarzi
1326
asked Nov 20 '18 at 15:51
Sean Goudarzi
1326
1326
$!!bmod 25!: 3^{large 20}equiv 1,Rightarrow,3^{large 10}equiv pm1,,$ must be $-1$ to be correct $!bmod 5. $ Equivalently, check your $2$ cases $!bmod 5 $
– Bill Dubuque
Nov 20 '18 at 16:57
add a comment |
$!!bmod 25!: 3^{large 20}equiv 1,Rightarrow,3^{large 10}equiv pm1,,$ must be $-1$ to be correct $!bmod 5. $ Equivalently, check your $2$ cases $!bmod 5 $
– Bill Dubuque
Nov 20 '18 at 16:57
$!!bmod 25!: 3^{large 20}equiv 1,Rightarrow,3^{large 10}equiv pm1,,$ must be $-1$ to be correct $!bmod 5. $ Equivalently, check your $2$ cases $!bmod 5 $
– Bill Dubuque
Nov 20 '18 at 16:57
$!!bmod 25!: 3^{large 20}equiv 1,Rightarrow,3^{large 10}equiv pm1,,$ must be $-1$ to be correct $!bmod 5. $ Equivalently, check your $2$ cases $!bmod 5 $
– Bill Dubuque
Nov 20 '18 at 16:57
add a comment |
1 Answer
1
active
oldest
votes
You've already used Euler's theorem to show that $3^{13}equiv2pmod{25}$ or $3^{13}equiv23pmod{25}$, as
$$(3^{13})^2equiv3^{26}equiv3^{26mod{phi(25)}}equiv3^{26mod{20}}equiv3^6equiv4pmod{25}.$$
You can use Euler's theorem mod $5$ to finish the proof; you know that
$$3^{13}equiv3^{13mod{phi(5)}}equiv3^{13mod{4}}equiv3^1pmod{5},$$
and hence $3^{13}equiv23pmod{25}$.
answered Nov 20 '18 at 15:54
Servaes
22.4k33793
1
I don't understand the second part, $3^{13}equiv23pmod{25}$, is there any property that I'm missing in modular arithmetics? What I conclude from the first expression is that $3^{13}$ divided by 25 could be any number from {3, 8, 13, 18, 23}
– Sean Goudarzi
Nov 20 '18 at 16:07
I was assuming the work you showed in your question already; let me expand my answer to clarify this.
– Servaes
Nov 20 '18 at 16:26
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%2f3006485%2fwhat-is-the-remainder-of-313-div-25-by-hand-using-eulers-theorem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
You've already used Euler's theorem to show that $3^{13}equiv2pmod{25}$ or $3^{13}equiv23pmod{25}$, as
$$(3^{13})^2equiv3^{26}equiv3^{26mod{phi(25)}}equiv3^{26mod{20}}equiv3^6equiv4pmod{25}.$$
You can use Euler's theorem mod $5$ to finish the proof; you know that
$$3^{13}equiv3^{13mod{phi(5)}}equiv3^{13mod{4}}equiv3^1pmod{5},$$
and hence $3^{13}equiv23pmod{25}$.
answered Nov 20 '18 at 15:54
Servaes
22.4k33793
1
I don't understand the second part, $3^{13}equiv23pmod{25}$, is there any property that I'm missing in modular arithmetics? What I conclude from the first expression is that $3^{13}$ divided by 25 could be any number from {3, 8, 13, 18, 23}
– Sean Goudarzi
Nov 20 '18 at 16:07
I was assuming the work you showed in your question already; let me expand my answer to clarify this.
– Servaes
Nov 20 '18 at 16:26
add a comment |
You've already used Euler's theorem to show that $3^{13}equiv2pmod{25}$ or $3^{13}equiv23pmod{25}$, as
$$(3^{13})^2equiv3^{26}equiv3^{26mod{phi(25)}}equiv3^{26mod{20}}equiv3^6equiv4pmod{25}.$$
You can use Euler's theorem mod $5$ to finish the proof; you know that
$$3^{13}equiv3^{13mod{phi(5)}}equiv3^{13mod{4}}equiv3^1pmod{5},$$
and hence $3^{13}equiv23pmod{25}$.
answered Nov 20 '18 at 15:54
Servaes
22.4k33793
1
I don't understand the second part, $3^{13}equiv23pmod{25}$, is there any property that I'm missing in modular arithmetics? What I conclude from the first expression is that $3^{13}$ divided by 25 could be any number from {3, 8, 13, 18, 23}
– Sean Goudarzi
Nov 20 '18 at 16:07
I was assuming the work you showed in your question already; let me expand my answer to clarify this.
– Servaes
Nov 20 '18 at 16:26
add a comment |
You've already used Euler's theorem to show that $3^{13}equiv2pmod{25}$ or $3^{13}equiv23pmod{25}$, as
$$(3^{13})^2equiv3^{26}equiv3^{26mod{phi(25)}}equiv3^{26mod{20}}equiv3^6equiv4pmod{25}.$$
You can use Euler's theorem mod $5$ to finish the proof; you know that
$$3^{13}equiv3^{13mod{phi(5)}}equiv3^{13mod{4}}equiv3^1pmod{5},$$
and hence $3^{13}equiv23pmod{25}$.
answered Nov 20 '18 at 15:54
Servaes
22.4k33793
You've already used Euler's theorem to show that $3^{13}equiv2pmod{25}$ or $3^{13}equiv23pmod{25}$, as
$$(3^{13})^2equiv3^{26}equiv3^{26mod{phi(25)}}equiv3^{26mod{20}}equiv3^6equiv4pmod{25}.$$
You can use Euler's theorem mod $5$ to finish the proof; you know that
$$3^{13}equiv3^{13mod{phi(5)}}equiv3^{13mod{4}}equiv3^1pmod{5},$$
and hence $3^{13}equiv23pmod{25}$.
answered Nov 20 '18 at 15:54
Servaes
22.4k33793
edited Nov 20 '18 at 16:28
answered Nov 20 '18 at 15:54
Servaes
22.4k33793
answered Nov 20 '18 at 15:54
Servaes
22.4k33793
answered Nov 20 '18 at 15:54
Servaes
22.4k33793
22.4k33793
1
I don't understand the second part, $3^{13}equiv23pmod{25}$, is there any property that I'm missing in modular arithmetics? What I conclude from the first expression is that $3^{13}$ divided by 25 could be any number from {3, 8, 13, 18, 23}
– Sean Goudarzi
Nov 20 '18 at 16:07
I was assuming the work you showed in your question already; let me expand my answer to clarify this.
– Servaes
Nov 20 '18 at 16:26
add a comment |
1
I don't understand the second part, $3^{13}equiv23pmod{25}$, is there any property that I'm missing in modular arithmetics? What I conclude from the first expression is that $3^{13}$ divided by 25 could be any number from {3, 8, 13, 18, 23}
– Sean Goudarzi
Nov 20 '18 at 16:07
I was assuming the work you showed in your question already; let me expand my answer to clarify this.
– Servaes
Nov 20 '18 at 16:26
1
1
I don't understand the second part, $3^{13}equiv23pmod{25}$, is there any property that I'm missing in modular arithmetics? What I conclude from the first expression is that $3^{13}$ divided by 25 could be any number from {3, 8, 13, 18, 23}
– Sean Goudarzi
Nov 20 '18 at 16:07
I don't understand the second part, $3^{13}equiv23pmod{25}$, is there any property that I'm missing in modular arithmetics? What I conclude from the first expression is that $3^{13}$ divided by 25 could be any number from {3, 8, 13, 18, 23}
– Sean Goudarzi
Nov 20 '18 at 16:07
I was assuming the work you showed in your question already; let me expand my answer to clarify this.
– Servaes
Nov 20 '18 at 16:26
I was assuming the work you showed in your question already; let me expand my answer to clarify this.
– Servaes
Nov 20 '18 at 16:26
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%2f3006485%2fwhat-is-the-remainder-of-313-div-25-by-hand-using-eulers-theorem%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
$!!bmod 25!: 3^{large 20}equiv 1,Rightarrow,3^{large 10}equiv pm1,,$ must be $-1$ to be correct $!bmod 5. $ Equivalently, check your $2$ cases $!bmod 5 $
– Bill Dubuque
Nov 20 '18 at 16:57