Solve for $m$: $m^5 + 7m + 8 equiv 0 pmod 3$
$begingroup$
I got about this far:
$$m^5 + 7m equiv -8 equiv 1 pmod 3$$
I'd have a much easier time solving a linear equation, but I have no clue about this one.
$$m(m^4 + 7) equiv 1 pmod 3$$
m itself is not divisible by three, but we already knew that... Any thoughts?
modular-arithmetic
$endgroup$
add a comment |
$begingroup$
I got about this far:
$$m^5 + 7m equiv -8 equiv 1 pmod 3$$
I'd have a much easier time solving a linear equation, but I have no clue about this one.
$$m(m^4 + 7) equiv 1 pmod 3$$
m itself is not divisible by three, but we already knew that... Any thoughts?
modular-arithmetic
$endgroup$
$begingroup$
$large bmod 3!: , mnotequiv 0,Rightarrow, mequiv pm1,Rightarrow,color{#C00}{m^4equiv 1}, $ so $large 1equiv (color{#c00}{m^4}!+!7)mequiv -m $
$endgroup$
– Bill Dubuque
Dec 17 '18 at 18:54
$begingroup$
The fastest method here would be to plug in $m=0$, $m=1$ and $m=2$, and see which (if any) of those work. Every integer is congruent to one of those three, so you are done at this point. More power to you, if you are asking for techniques handling more difficult cases. Those are not really for paper & pencil work though.
$endgroup$
– Jyrki Lahtonen
Dec 19 '18 at 10:30
add a comment |
$begingroup$
I got about this far:
$$m^5 + 7m equiv -8 equiv 1 pmod 3$$
I'd have a much easier time solving a linear equation, but I have no clue about this one.
$$m(m^4 + 7) equiv 1 pmod 3$$
m itself is not divisible by three, but we already knew that... Any thoughts?
modular-arithmetic
$endgroup$
I got about this far:
$$m^5 + 7m equiv -8 equiv 1 pmod 3$$
I'd have a much easier time solving a linear equation, but I have no clue about this one.
$$m(m^4 + 7) equiv 1 pmod 3$$
m itself is not divisible by three, but we already knew that... Any thoughts?
modular-arithmetic
modular-arithmetic
edited Dec 17 '18 at 18:02
Tianlalu
3,09421138
3,09421138
asked Dec 17 '18 at 17:58
MinahMinah
183
183
$begingroup$
$large bmod 3!: , mnotequiv 0,Rightarrow, mequiv pm1,Rightarrow,color{#C00}{m^4equiv 1}, $ so $large 1equiv (color{#c00}{m^4}!+!7)mequiv -m $
$endgroup$
– Bill Dubuque
Dec 17 '18 at 18:54
$begingroup$
The fastest method here would be to plug in $m=0$, $m=1$ and $m=2$, and see which (if any) of those work. Every integer is congruent to one of those three, so you are done at this point. More power to you, if you are asking for techniques handling more difficult cases. Those are not really for paper & pencil work though.
$endgroup$
– Jyrki Lahtonen
Dec 19 '18 at 10:30
add a comment |
$begingroup$
$large bmod 3!: , mnotequiv 0,Rightarrow, mequiv pm1,Rightarrow,color{#C00}{m^4equiv 1}, $ so $large 1equiv (color{#c00}{m^4}!+!7)mequiv -m $
$endgroup$
– Bill Dubuque
Dec 17 '18 at 18:54
$begingroup$
The fastest method here would be to plug in $m=0$, $m=1$ and $m=2$, and see which (if any) of those work. Every integer is congruent to one of those three, so you are done at this point. More power to you, if you are asking for techniques handling more difficult cases. Those are not really for paper & pencil work though.
$endgroup$
– Jyrki Lahtonen
Dec 19 '18 at 10:30
$begingroup$
$large bmod 3!: , mnotequiv 0,Rightarrow, mequiv pm1,Rightarrow,color{#C00}{m^4equiv 1}, $ so $large 1equiv (color{#c00}{m^4}!+!7)mequiv -m $
$endgroup$
– Bill Dubuque
Dec 17 '18 at 18:54
$begingroup$
$large bmod 3!: , mnotequiv 0,Rightarrow, mequiv pm1,Rightarrow,color{#C00}{m^4equiv 1}, $ so $large 1equiv (color{#c00}{m^4}!+!7)mequiv -m $
$endgroup$
– Bill Dubuque
Dec 17 '18 at 18:54
$begingroup$
The fastest method here would be to plug in $m=0$, $m=1$ and $m=2$, and see which (if any) of those work. Every integer is congruent to one of those three, so you are done at this point. More power to you, if you are asking for techniques handling more difficult cases. Those are not really for paper & pencil work though.
$endgroup$
– Jyrki Lahtonen
Dec 19 '18 at 10:30
$begingroup$
The fastest method here would be to plug in $m=0$, $m=1$ and $m=2$, and see which (if any) of those work. Every integer is congruent to one of those three, so you are done at this point. More power to you, if you are asking for techniques handling more difficult cases. Those are not really for paper & pencil work though.
$endgroup$
– Jyrki Lahtonen
Dec 19 '18 at 10:30
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
You are working in the space $mathbb{Z}/3mathbb{Z}={0,1,2}$ so there are only three elements to check.
For $mequiv 0$, $m^{5}+7m+8=8equiv 2mod 3$, so $0$ is not a solution.
For $mequiv 1$, $m^{5}+7m+8=16equiv 1mod 3$, so $1$ is not a solution.
For $mequiv 2$, $m^{5}+7m+8=54equiv 0mod 3$, so $2$ is a solution.
So $2$ is the only solution.
$endgroup$
$begingroup$
Delightful! May I ask, how would we proceed with a larger modulo where checking possible solutions would consume too much time?
$endgroup$
– Minah
Dec 17 '18 at 18:18
$begingroup$
For larger moduli, it would depend on the problem. It's impossible to give a general method for solving any congruence, but some useful tools are factoring (like you did), Fermat's little theorem (for prime moduli), or using quadratic residues.
$endgroup$
– pwerth
Dec 17 '18 at 18:23
add a comment |
$begingroup$
$$m^3equiv mpmod3$$
$$m^5equiv m^3equiv mpmod3$$
So, we need $3|8(m+1)iff mequiv-1equiv2pmod3$ as $(8,3)=1$
$endgroup$
add a comment |
$begingroup$
Take the coefficients mod $3$:
$$m^5+7m+8equiv m^5 + m+2equiv 0pmod 3$$
Apply the Little Theoreom of Fermat, which is $m^pequiv m pmod{p}$ for a prime $p$ and any $m$:
$$mcdot m^2 + m+2equiv m + m+2 equiv 2m+2 equiv 0pmod 3$$
Therefore:
$$m equiv -1 equiv 2pmod 3$$
$endgroup$
$begingroup$
This is essentially a dupe of lab's answer.
$endgroup$
– Bill Dubuque
Dec 17 '18 at 18:40
add a comment |
$begingroup$
Alternatively:
$$m^5+7m+8equiv m^5-m+8m+8equiv m(m-1)(m+1)(m^2+1)+8(m+1)equiv \8(m+1)equiv 0pmod{3}.$$
Here is the linear congruence equation for you.
$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%2f3044246%2fsolve-for-m-m5-7m-8-equiv-0-pmod-3%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$
You are working in the space $mathbb{Z}/3mathbb{Z}={0,1,2}$ so there are only three elements to check.
For $mequiv 0$, $m^{5}+7m+8=8equiv 2mod 3$, so $0$ is not a solution.
For $mequiv 1$, $m^{5}+7m+8=16equiv 1mod 3$, so $1$ is not a solution.
For $mequiv 2$, $m^{5}+7m+8=54equiv 0mod 3$, so $2$ is a solution.
So $2$ is the only solution.
$endgroup$
$begingroup$
Delightful! May I ask, how would we proceed with a larger modulo where checking possible solutions would consume too much time?
$endgroup$
– Minah
Dec 17 '18 at 18:18
$begingroup$
For larger moduli, it would depend on the problem. It's impossible to give a general method for solving any congruence, but some useful tools are factoring (like you did), Fermat's little theorem (for prime moduli), or using quadratic residues.
$endgroup$
– pwerth
Dec 17 '18 at 18:23
add a comment |
$begingroup$
You are working in the space $mathbb{Z}/3mathbb{Z}={0,1,2}$ so there are only three elements to check.
For $mequiv 0$, $m^{5}+7m+8=8equiv 2mod 3$, so $0$ is not a solution.
For $mequiv 1$, $m^{5}+7m+8=16equiv 1mod 3$, so $1$ is not a solution.
For $mequiv 2$, $m^{5}+7m+8=54equiv 0mod 3$, so $2$ is a solution.
So $2$ is the only solution.
$endgroup$
$begingroup$
Delightful! May I ask, how would we proceed with a larger modulo where checking possible solutions would consume too much time?
$endgroup$
– Minah
Dec 17 '18 at 18:18
$begingroup$
For larger moduli, it would depend on the problem. It's impossible to give a general method for solving any congruence, but some useful tools are factoring (like you did), Fermat's little theorem (for prime moduli), or using quadratic residues.
$endgroup$
– pwerth
Dec 17 '18 at 18:23
add a comment |
$begingroup$
You are working in the space $mathbb{Z}/3mathbb{Z}={0,1,2}$ so there are only three elements to check.
For $mequiv 0$, $m^{5}+7m+8=8equiv 2mod 3$, so $0$ is not a solution.
For $mequiv 1$, $m^{5}+7m+8=16equiv 1mod 3$, so $1$ is not a solution.
For $mequiv 2$, $m^{5}+7m+8=54equiv 0mod 3$, so $2$ is a solution.
So $2$ is the only solution.
$endgroup$
You are working in the space $mathbb{Z}/3mathbb{Z}={0,1,2}$ so there are only three elements to check.
For $mequiv 0$, $m^{5}+7m+8=8equiv 2mod 3$, so $0$ is not a solution.
For $mequiv 1$, $m^{5}+7m+8=16equiv 1mod 3$, so $1$ is not a solution.
For $mequiv 2$, $m^{5}+7m+8=54equiv 0mod 3$, so $2$ is a solution.
So $2$ is the only solution.
answered Dec 17 '18 at 18:00
pwerthpwerth
3,300417
3,300417
$begingroup$
Delightful! May I ask, how would we proceed with a larger modulo where checking possible solutions would consume too much time?
$endgroup$
– Minah
Dec 17 '18 at 18:18
$begingroup$
For larger moduli, it would depend on the problem. It's impossible to give a general method for solving any congruence, but some useful tools are factoring (like you did), Fermat's little theorem (for prime moduli), or using quadratic residues.
$endgroup$
– pwerth
Dec 17 '18 at 18:23
add a comment |
$begingroup$
Delightful! May I ask, how would we proceed with a larger modulo where checking possible solutions would consume too much time?
$endgroup$
– Minah
Dec 17 '18 at 18:18
$begingroup$
For larger moduli, it would depend on the problem. It's impossible to give a general method for solving any congruence, but some useful tools are factoring (like you did), Fermat's little theorem (for prime moduli), or using quadratic residues.
$endgroup$
– pwerth
Dec 17 '18 at 18:23
$begingroup$
Delightful! May I ask, how would we proceed with a larger modulo where checking possible solutions would consume too much time?
$endgroup$
– Minah
Dec 17 '18 at 18:18
$begingroup$
Delightful! May I ask, how would we proceed with a larger modulo where checking possible solutions would consume too much time?
$endgroup$
– Minah
Dec 17 '18 at 18:18
$begingroup$
For larger moduli, it would depend on the problem. It's impossible to give a general method for solving any congruence, but some useful tools are factoring (like you did), Fermat's little theorem (for prime moduli), or using quadratic residues.
$endgroup$
– pwerth
Dec 17 '18 at 18:23
$begingroup$
For larger moduli, it would depend on the problem. It's impossible to give a general method for solving any congruence, but some useful tools are factoring (like you did), Fermat's little theorem (for prime moduli), or using quadratic residues.
$endgroup$
– pwerth
Dec 17 '18 at 18:23
add a comment |
$begingroup$
$$m^3equiv mpmod3$$
$$m^5equiv m^3equiv mpmod3$$
So, we need $3|8(m+1)iff mequiv-1equiv2pmod3$ as $(8,3)=1$
$endgroup$
add a comment |
$begingroup$
$$m^3equiv mpmod3$$
$$m^5equiv m^3equiv mpmod3$$
So, we need $3|8(m+1)iff mequiv-1equiv2pmod3$ as $(8,3)=1$
$endgroup$
add a comment |
$begingroup$
$$m^3equiv mpmod3$$
$$m^5equiv m^3equiv mpmod3$$
So, we need $3|8(m+1)iff mequiv-1equiv2pmod3$ as $(8,3)=1$
$endgroup$
$$m^3equiv mpmod3$$
$$m^5equiv m^3equiv mpmod3$$
So, we need $3|8(m+1)iff mequiv-1equiv2pmod3$ as $(8,3)=1$
answered Dec 17 '18 at 18:02
lab bhattacharjeelab bhattacharjee
227k15158276
227k15158276
add a comment |
add a comment |
$begingroup$
Take the coefficients mod $3$:
$$m^5+7m+8equiv m^5 + m+2equiv 0pmod 3$$
Apply the Little Theoreom of Fermat, which is $m^pequiv m pmod{p}$ for a prime $p$ and any $m$:
$$mcdot m^2 + m+2equiv m + m+2 equiv 2m+2 equiv 0pmod 3$$
Therefore:
$$m equiv -1 equiv 2pmod 3$$
$endgroup$
$begingroup$
This is essentially a dupe of lab's answer.
$endgroup$
– Bill Dubuque
Dec 17 '18 at 18:40
add a comment |
$begingroup$
Take the coefficients mod $3$:
$$m^5+7m+8equiv m^5 + m+2equiv 0pmod 3$$
Apply the Little Theoreom of Fermat, which is $m^pequiv m pmod{p}$ for a prime $p$ and any $m$:
$$mcdot m^2 + m+2equiv m + m+2 equiv 2m+2 equiv 0pmod 3$$
Therefore:
$$m equiv -1 equiv 2pmod 3$$
$endgroup$
$begingroup$
This is essentially a dupe of lab's answer.
$endgroup$
– Bill Dubuque
Dec 17 '18 at 18:40
add a comment |
$begingroup$
Take the coefficients mod $3$:
$$m^5+7m+8equiv m^5 + m+2equiv 0pmod 3$$
Apply the Little Theoreom of Fermat, which is $m^pequiv m pmod{p}$ for a prime $p$ and any $m$:
$$mcdot m^2 + m+2equiv m + m+2 equiv 2m+2 equiv 0pmod 3$$
Therefore:
$$m equiv -1 equiv 2pmod 3$$
$endgroup$
Take the coefficients mod $3$:
$$m^5+7m+8equiv m^5 + m+2equiv 0pmod 3$$
Apply the Little Theoreom of Fermat, which is $m^pequiv m pmod{p}$ for a prime $p$ and any $m$:
$$mcdot m^2 + m+2equiv m + m+2 equiv 2m+2 equiv 0pmod 3$$
Therefore:
$$m equiv -1 equiv 2pmod 3$$
answered Dec 17 '18 at 18:26
I like SerenaI like Serena
4,3321822
4,3321822
$begingroup$
This is essentially a dupe of lab's answer.
$endgroup$
– Bill Dubuque
Dec 17 '18 at 18:40
add a comment |
$begingroup$
This is essentially a dupe of lab's answer.
$endgroup$
– Bill Dubuque
Dec 17 '18 at 18:40
$begingroup$
This is essentially a dupe of lab's answer.
$endgroup$
– Bill Dubuque
Dec 17 '18 at 18:40
$begingroup$
This is essentially a dupe of lab's answer.
$endgroup$
– Bill Dubuque
Dec 17 '18 at 18:40
add a comment |
$begingroup$
Alternatively:
$$m^5+7m+8equiv m^5-m+8m+8equiv m(m-1)(m+1)(m^2+1)+8(m+1)equiv \8(m+1)equiv 0pmod{3}.$$
Here is the linear congruence equation for you.
$endgroup$
add a comment |
$begingroup$
Alternatively:
$$m^5+7m+8equiv m^5-m+8m+8equiv m(m-1)(m+1)(m^2+1)+8(m+1)equiv \8(m+1)equiv 0pmod{3}.$$
Here is the linear congruence equation for you.
$endgroup$
add a comment |
$begingroup$
Alternatively:
$$m^5+7m+8equiv m^5-m+8m+8equiv m(m-1)(m+1)(m^2+1)+8(m+1)equiv \8(m+1)equiv 0pmod{3}.$$
Here is the linear congruence equation for you.
$endgroup$
Alternatively:
$$m^5+7m+8equiv m^5-m+8m+8equiv m(m-1)(m+1)(m^2+1)+8(m+1)equiv \8(m+1)equiv 0pmod{3}.$$
Here is the linear congruence equation for you.
answered Dec 17 '18 at 18:29
farruhotafarruhota
21.3k2841
21.3k2841
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%2f3044246%2fsolve-for-m-m5-7m-8-equiv-0-pmod-3%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
$begingroup$
$large bmod 3!: , mnotequiv 0,Rightarrow, mequiv pm1,Rightarrow,color{#C00}{m^4equiv 1}, $ so $large 1equiv (color{#c00}{m^4}!+!7)mequiv -m $
$endgroup$
– Bill Dubuque
Dec 17 '18 at 18:54
$begingroup$
The fastest method here would be to plug in $m=0$, $m=1$ and $m=2$, and see which (if any) of those work. Every integer is congruent to one of those three, so you are done at this point. More power to you, if you are asking for techniques handling more difficult cases. Those are not really for paper & pencil work though.
$endgroup$
– Jyrki Lahtonen
Dec 19 '18 at 10:30