Solutions to $x^2+x-1equiv 0$ mod $p$
The problem is to find all prime number p such that the above congruence has solutions.
I started this problem by rearranging the equation such that:
$$
x(x+1)equiv 1 pmod{p}
$$
The hint given was to use quadratic reciprocity however I don't see how to apply that to this problem. I did do some brute force work and found that there are no solutions for $p=2,7,13,17,23$ one solutions for $p=5$ and two solutions for $p=11,19,29$.
Any help would be much appreciated.
elementary-number-theory quadratic-reciprocity
asked Dec 9 '18 at 23:53
mjoseph
859
add a comment |
The problem is to find all prime number p such that the above congruence has solutions.
I started this problem by rearranging the equation such that:
$$
x(x+1)equiv 1 pmod{p}
$$
The hint given was to use quadratic reciprocity however I don't see how to apply that to this problem. I did do some brute force work and found that there are no solutions for $p=2,7,13,17,23$ one solutions for $p=5$ and two solutions for $p=11,19,29$.
Any help would be much appreciated.
elementary-number-theory quadratic-reciprocity
asked Dec 9 '18 at 23:53
mjoseph
859
2
Have you tried completing the square?
– JavaMan
Dec 9 '18 at 23:57
1
Hint: The answer depends on whether $5$ is a quadratic residue modulo $p$. Do strongly take @JavaMan's suggestion into consideration.
– Batominovski
Dec 10 '18 at 0:03
add a comment |
The problem is to find all prime number p such that the above congruence has solutions.
I started this problem by rearranging the equation such that:
$$
x(x+1)equiv 1 pmod{p}
$$
The hint given was to use quadratic reciprocity however I don't see how to apply that to this problem. I did do some brute force work and found that there are no solutions for $p=2,7,13,17,23$ one solutions for $p=5$ and two solutions for $p=11,19,29$.
Any help would be much appreciated.
elementary-number-theory quadratic-reciprocity
asked Dec 9 '18 at 23:53
mjoseph
859
The problem is to find all prime number p such that the above congruence has solutions.
I started this problem by rearranging the equation such that:
$$
x(x+1)equiv 1 pmod{p}
$$
The hint given was to use quadratic reciprocity however I don't see how to apply that to this problem. I did do some brute force work and found that there are no solutions for $p=2,7,13,17,23$ one solutions for $p=5$ and two solutions for $p=11,19,29$.
Any help would be much appreciated.
elementary-number-theory quadratic-reciprocity
elementary-number-theory quadratic-reciprocity
asked Dec 9 '18 at 23:53
mjoseph
859
asked Dec 9 '18 at 23:53
mjoseph
859
asked Dec 9 '18 at 23:53
mjoseph
859
asked Dec 9 '18 at 23:53
mjoseph
859
asked Dec 9 '18 at 23:53
mjoseph
859
859
2
Have you tried completing the square?
– JavaMan
Dec 9 '18 at 23:57
1
Hint: The answer depends on whether $5$ is a quadratic residue modulo $p$. Do strongly take @JavaMan's suggestion into consideration.
– Batominovski
Dec 10 '18 at 0:03
add a comment |
2
Have you tried completing the square?
– JavaMan
Dec 9 '18 at 23:57
1
Hint: The answer depends on whether $5$ is a quadratic residue modulo $p$. Do strongly take @JavaMan's suggestion into consideration.
– Batominovski
Dec 10 '18 at 0:03
2
2
Have you tried completing the square?
– JavaMan
Dec 9 '18 at 23:57
Have you tried completing the square?
– JavaMan
Dec 9 '18 at 23:57
1
1
Hint: The answer depends on whether $5$ is a quadratic residue modulo $p$. Do strongly take @JavaMan's suggestion into consideration.
– Batominovski
Dec 10 '18 at 0:03
Hint: The answer depends on whether $5$ is a quadratic residue modulo $p$. Do strongly take @JavaMan's suggestion into consideration.
– Batominovski
Dec 10 '18 at 0:03
add a comment |
2 Answers
2
active
oldest
votes
Completing the square is the most obvious approach. Starting from
$$x^2+x-1equiv 0pmod p$$
we want to make the LHS into a square, so we can discuss quadratic residues. Multiply through by $4$:
$$ 4x^2+4x-4equiv 0pmod piff (2x+1)^2equiv 5pmod p.$$
Hence for this congruence to have a solution, $5$ needs to be a quadratic residue modulo $p$. Can you continue from here? (Hint: try using Euler's Criterion.)
answered Dec 10 '18 at 1:30
YiFan
2,5291421
Oh yeah that makes sense. Thank you for the help!
– mjoseph
Dec 10 '18 at 1:51
1
Is this correct: Basically, by the Law of Quadratic Reciprocity, the last equation you got can only be true iff p is a square (mod 5), i.e. $pequiv +/-1 pmod{5}$ or $p=5$.
– mjoseph
Dec 10 '18 at 2:57
add a comment |
For odd $p$, multiply through by $4$ to get
$$4x^2+4x+1 equiv 5 pmod{p}.$$
Enough?
answered Dec 10 '18 at 0:49
B. Goddard
18.4k21340
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%2f3033207%2fsolutions-to-x2x-1-equiv-0-mod-p%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
Completing the square is the most obvious approach. Starting from
$$x^2+x-1equiv 0pmod p$$
we want to make the LHS into a square, so we can discuss quadratic residues. Multiply through by $4$:
$$ 4x^2+4x-4equiv 0pmod piff (2x+1)^2equiv 5pmod p.$$
Hence for this congruence to have a solution, $5$ needs to be a quadratic residue modulo $p$. Can you continue from here? (Hint: try using Euler's Criterion.)
answered Dec 10 '18 at 1:30
YiFan
2,5291421
Oh yeah that makes sense. Thank you for the help!
– mjoseph
Dec 10 '18 at 1:51
1
Is this correct: Basically, by the Law of Quadratic Reciprocity, the last equation you got can only be true iff p is a square (mod 5), i.e. $pequiv +/-1 pmod{5}$ or $p=5$.
– mjoseph
Dec 10 '18 at 2:57
add a comment |
Completing the square is the most obvious approach. Starting from
$$x^2+x-1equiv 0pmod p$$
we want to make the LHS into a square, so we can discuss quadratic residues. Multiply through by $4$:
$$ 4x^2+4x-4equiv 0pmod piff (2x+1)^2equiv 5pmod p.$$
Hence for this congruence to have a solution, $5$ needs to be a quadratic residue modulo $p$. Can you continue from here? (Hint: try using Euler's Criterion.)
answered Dec 10 '18 at 1:30
YiFan
2,5291421
Oh yeah that makes sense. Thank you for the help!
– mjoseph
Dec 10 '18 at 1:51
1
Is this correct: Basically, by the Law of Quadratic Reciprocity, the last equation you got can only be true iff p is a square (mod 5), i.e. $pequiv +/-1 pmod{5}$ or $p=5$.
– mjoseph
Dec 10 '18 at 2:57
add a comment |
Completing the square is the most obvious approach. Starting from
$$x^2+x-1equiv 0pmod p$$
we want to make the LHS into a square, so we can discuss quadratic residues. Multiply through by $4$:
$$ 4x^2+4x-4equiv 0pmod piff (2x+1)^2equiv 5pmod p.$$
Hence for this congruence to have a solution, $5$ needs to be a quadratic residue modulo $p$. Can you continue from here? (Hint: try using Euler's Criterion.)
answered Dec 10 '18 at 1:30
YiFan
2,5291421
Completing the square is the most obvious approach. Starting from
$$x^2+x-1equiv 0pmod p$$
we want to make the LHS into a square, so we can discuss quadratic residues. Multiply through by $4$:
$$ 4x^2+4x-4equiv 0pmod piff (2x+1)^2equiv 5pmod p.$$
Hence for this congruence to have a solution, $5$ needs to be a quadratic residue modulo $p$. Can you continue from here? (Hint: try using Euler's Criterion.)
answered Dec 10 '18 at 1:30
YiFan
2,5291421
answered Dec 10 '18 at 1:30
YiFan
2,5291421
answered Dec 10 '18 at 1:30
YiFan
2,5291421
answered Dec 10 '18 at 1:30
YiFan
2,5291421
2,5291421
Oh yeah that makes sense. Thank you for the help!
– mjoseph
Dec 10 '18 at 1:51
1
Is this correct: Basically, by the Law of Quadratic Reciprocity, the last equation you got can only be true iff p is a square (mod 5), i.e. $pequiv +/-1 pmod{5}$ or $p=5$.
– mjoseph
Dec 10 '18 at 2:57
add a comment |
Oh yeah that makes sense. Thank you for the help!
– mjoseph
Dec 10 '18 at 1:51
1
Is this correct: Basically, by the Law of Quadratic Reciprocity, the last equation you got can only be true iff p is a square (mod 5), i.e. $pequiv +/-1 pmod{5}$ or $p=5$.
– mjoseph
Dec 10 '18 at 2:57
Oh yeah that makes sense. Thank you for the help!
– mjoseph
Dec 10 '18 at 1:51
Oh yeah that makes sense. Thank you for the help!
– mjoseph
Dec 10 '18 at 1:51
1
1
Is this correct: Basically, by the Law of Quadratic Reciprocity, the last equation you got can only be true iff p is a square (mod 5), i.e. $pequiv +/-1 pmod{5}$ or $p=5$.
– mjoseph
Dec 10 '18 at 2:57
Is this correct: Basically, by the Law of Quadratic Reciprocity, the last equation you got can only be true iff p is a square (mod 5), i.e. $pequiv +/-1 pmod{5}$ or $p=5$.
– mjoseph
Dec 10 '18 at 2:57
add a comment |
For odd $p$, multiply through by $4$ to get
$$4x^2+4x+1 equiv 5 pmod{p}.$$
Enough?
answered Dec 10 '18 at 0:49
B. Goddard
18.4k21340
add a comment |
For odd $p$, multiply through by $4$ to get
$$4x^2+4x+1 equiv 5 pmod{p}.$$
Enough?
answered Dec 10 '18 at 0:49
B. Goddard
18.4k21340
add a comment |
For odd $p$, multiply through by $4$ to get
$$4x^2+4x+1 equiv 5 pmod{p}.$$
Enough?
answered Dec 10 '18 at 0:49
B. Goddard
18.4k21340
For odd $p$, multiply through by $4$ to get
$$4x^2+4x+1 equiv 5 pmod{p}.$$
Enough?
answered Dec 10 '18 at 0:49
B. Goddard
18.4k21340
answered Dec 10 '18 at 0:49
B. Goddard
18.4k21340
answered Dec 10 '18 at 0:49
B. Goddard
18.4k21340
answered Dec 10 '18 at 0:49
B. Goddard
18.4k21340
18.4k21340
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.
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%2f3033207%2fsolutions-to-x2x-1-equiv-0-mod-p%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
2
Have you tried completing the square?
– JavaMan
Dec 9 '18 at 23:57
1
Hint: The answer depends on whether $5$ is a quadratic residue modulo $p$. Do strongly take @JavaMan's suggestion into consideration.
– Batominovski
Dec 10 '18 at 0:03