$x^2equiv 5 pmod{1331p^3}$
Let $p$ be given by $p=2^{89}-1$ and note that it is a Mersenne Prime. The problem is to find the number of incongruent solutions to
$$
x^2equiv 5 pmod{1331p^3}
$$
I began the problem by splitting it up into the congruences
$$
x^2equiv 5 pmod{1331} $$and$$
x^2equiv 5 pmod{p^3}
$$
I found that $xequiv 4,7pmod{11}$ are solutions to $x^2equiv 5pmod{11}$ and then use Hansel's Lemma all the way up to get that $xequiv 1258, 73pmod{1331}$ are solutions to the equation $pmod{1331}$.
I think all I have to do is solve the second equation and use the Chinese Remainder Theorem at the end but I am stuck because I have no idea where to begin in solving $x^2equiv 5pmod{p}$ as p is such a large number.
Any help is appreciated!
number-theory chinese-remainder-theorem quadratic-residues hensels-lemma
asked Dec 10 '18 at 3:31
mjoseph
859
add a comment |
Let $p$ be given by $p=2^{89}-1$ and note that it is a Mersenne Prime. The problem is to find the number of incongruent solutions to
$$
x^2equiv 5 pmod{1331p^3}
$$
I began the problem by splitting it up into the congruences
$$
x^2equiv 5 pmod{1331} $$and$$
x^2equiv 5 pmod{p^3}
$$
I found that $xequiv 4,7pmod{11}$ are solutions to $x^2equiv 5pmod{11}$ and then use Hansel's Lemma all the way up to get that $xequiv 1258, 73pmod{1331}$ are solutions to the equation $pmod{1331}$.
I think all I have to do is solve the second equation and use the Chinese Remainder Theorem at the end but I am stuck because I have no idea where to begin in solving $x^2equiv 5pmod{p}$ as p is such a large number.
Any help is appreciated!
number-theory chinese-remainder-theorem quadratic-residues hensels-lemma
asked Dec 10 '18 at 3:31
mjoseph
859
Are you familiar with Legendere symbol and quadratic reciprocity?
– Anurag A
Dec 10 '18 at 3:34
Yes I am familiar with both but do not totally understand when and how to apply the concept
– mjoseph
Dec 10 '18 at 3:39
Oh I think I see what you mean. So can I say that $5equiv 1pmod{4}$ so the legendre symbol of 5 on p equals the legendre symbol of p on 5. Then just replace p with its least positive residue mod 5?
– mjoseph
Dec 10 '18 at 3:42
add a comment |
Let $p$ be given by $p=2^{89}-1$ and note that it is a Mersenne Prime. The problem is to find the number of incongruent solutions to
$$
x^2equiv 5 pmod{1331p^3}
$$
I began the problem by splitting it up into the congruences
$$
x^2equiv 5 pmod{1331} $$and$$
x^2equiv 5 pmod{p^3}
$$
I found that $xequiv 4,7pmod{11}$ are solutions to $x^2equiv 5pmod{11}$ and then use Hansel's Lemma all the way up to get that $xequiv 1258, 73pmod{1331}$ are solutions to the equation $pmod{1331}$.
I think all I have to do is solve the second equation and use the Chinese Remainder Theorem at the end but I am stuck because I have no idea where to begin in solving $x^2equiv 5pmod{p}$ as p is such a large number.
Any help is appreciated!
number-theory chinese-remainder-theorem quadratic-residues hensels-lemma
asked Dec 10 '18 at 3:31
mjoseph
859
Let $p$ be given by $p=2^{89}-1$ and note that it is a Mersenne Prime. The problem is to find the number of incongruent solutions to
$$
x^2equiv 5 pmod{1331p^3}
$$
I began the problem by splitting it up into the congruences
$$
x^2equiv 5 pmod{1331} $$and$$
x^2equiv 5 pmod{p^3}
$$
I found that $xequiv 4,7pmod{11}$ are solutions to $x^2equiv 5pmod{11}$ and then use Hansel's Lemma all the way up to get that $xequiv 1258, 73pmod{1331}$ are solutions to the equation $pmod{1331}$.
I think all I have to do is solve the second equation and use the Chinese Remainder Theorem at the end but I am stuck because I have no idea where to begin in solving $x^2equiv 5pmod{p}$ as p is such a large number.
Any help is appreciated!
number-theory chinese-remainder-theorem quadratic-residues hensels-lemma
number-theory chinese-remainder-theorem quadratic-residues hensels-lemma
asked Dec 10 '18 at 3:31
mjoseph
859
asked Dec 10 '18 at 3:31
mjoseph
859
asked Dec 10 '18 at 3:31
mjoseph
859
asked Dec 10 '18 at 3:31
mjoseph
859
asked Dec 10 '18 at 3:31
mjoseph
859
859
Are you familiar with Legendere symbol and quadratic reciprocity?
– Anurag A
Dec 10 '18 at 3:34
Yes I am familiar with both but do not totally understand when and how to apply the concept
– mjoseph
Dec 10 '18 at 3:39
Oh I think I see what you mean. So can I say that $5equiv 1pmod{4}$ so the legendre symbol of 5 on p equals the legendre symbol of p on 5. Then just replace p with its least positive residue mod 5?
– mjoseph
Dec 10 '18 at 3:42
add a comment |
Are you familiar with Legendere symbol and quadratic reciprocity?
– Anurag A
Dec 10 '18 at 3:34
Yes I am familiar with both but do not totally understand when and how to apply the concept
– mjoseph
Dec 10 '18 at 3:39
Oh I think I see what you mean. So can I say that $5equiv 1pmod{4}$ so the legendre symbol of 5 on p equals the legendre symbol of p on 5. Then just replace p with its least positive residue mod 5?
– mjoseph
Dec 10 '18 at 3:42
Are you familiar with Legendere symbol and quadratic reciprocity?
– Anurag A
Dec 10 '18 at 3:34
Are you familiar with Legendere symbol and quadratic reciprocity?
– Anurag A
Dec 10 '18 at 3:34
Yes I am familiar with both but do not totally understand when and how to apply the concept
– mjoseph
Dec 10 '18 at 3:39
Yes I am familiar with both but do not totally understand when and how to apply the concept
– mjoseph
Dec 10 '18 at 3:39
Oh I think I see what you mean. So can I say that $5equiv 1pmod{4}$ so the legendre symbol of 5 on p equals the legendre symbol of p on 5. Then just replace p with its least positive residue mod 5?
– mjoseph
Dec 10 '18 at 3:42
Oh I think I see what you mean. So can I say that $5equiv 1pmod{4}$ so the legendre symbol of 5 on p equals the legendre symbol of p on 5. Then just replace p with its least positive residue mod 5?
– mjoseph
Dec 10 '18 at 3:42
add a comment |
1 Answer
1
active
oldest
votes
Consider Legendere symbol $left(frac{5}{p}right)$. By quadratic reciprocity
$$left(frac{5}{p}right)Big(frac{p}{5}Big)=(-1)^{left(frac{5-1}{2}right)left(frac{p-1}{2}right)}=1 implies left(frac{5}{p}right)=left(frac{p}{5}right).$$
But $p=2^{89}-1 equiv 2(2^2)^{44}-1 equiv 1 pmod{5}$. Thus
$$left(frac{5}{p}right)=left(frac{p}{5}right)=left(frac{1}{5}right)=1.$$
Thus $5$ is indeed a QR modulo $p$. Since $p$ is a prime thus $x^2 equiv 5 pmod{5}$ will have two non-congruent solutions. Now you can apply Hensel to see if you will continue to have two solutions as you lift from $p$ to $p^3$.
If you have two solutions for $p^3$ as well, then in all you will have $4$ solutions (combining with two from the previous congruence with $11^3$).
answered Dec 10 '18 at 3:47
Anurag A
25.6k12249
The OP isn't having trouble with that part, as demonstrated by his mod 11^3 calcuatlions. He is asking for help with finding the square-root of 5 mod p, not about lifting that square-root from mod p to mod p^3.
– user10354138
Dec 10 '18 at 3:55
@user10354138 From the language of the question, OP wants to find the number of solutions (not the actual solutions). So if we can know the number of solutions for both congruences then you can have the number of solutions for the given congruence. My answer is in that regards.
– Anurag A
Dec 10 '18 at 3:57
I had this but I didn't think it was helpful as I can't use Hensel's Lemma unless I know explicit values of f(x) and f '(x).
– mjoseph
Dec 10 '18 at 4:03
1
@mjoseph you don't really need explicit $x$, only that $f'(x)=2x$ is nonzero (using $f(x)=x^2-5$). But that is obvious from $x^2equiv 5pmod{p}$)
– user10354138
Dec 10 '18 at 4:05
Oh yes that is obvious. Thank you so much!
– mjoseph
Dec 10 '18 at 4:07
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%2f3033409%2fx2-equiv-5-pmod1331p3%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
Consider Legendere symbol $left(frac{5}{p}right)$. By quadratic reciprocity
$$left(frac{5}{p}right)Big(frac{p}{5}Big)=(-1)^{left(frac{5-1}{2}right)left(frac{p-1}{2}right)}=1 implies left(frac{5}{p}right)=left(frac{p}{5}right).$$
But $p=2^{89}-1 equiv 2(2^2)^{44}-1 equiv 1 pmod{5}$. Thus
$$left(frac{5}{p}right)=left(frac{p}{5}right)=left(frac{1}{5}right)=1.$$
Thus $5$ is indeed a QR modulo $p$. Since $p$ is a prime thus $x^2 equiv 5 pmod{5}$ will have two non-congruent solutions. Now you can apply Hensel to see if you will continue to have two solutions as you lift from $p$ to $p^3$.
If you have two solutions for $p^3$ as well, then in all you will have $4$ solutions (combining with two from the previous congruence with $11^3$).
answered Dec 10 '18 at 3:47
Anurag A
25.6k12249
The OP isn't having trouble with that part, as demonstrated by his mod 11^3 calcuatlions. He is asking for help with finding the square-root of 5 mod p, not about lifting that square-root from mod p to mod p^3.
– user10354138
Dec 10 '18 at 3:55
@user10354138 From the language of the question, OP wants to find the number of solutions (not the actual solutions). So if we can know the number of solutions for both congruences then you can have the number of solutions for the given congruence. My answer is in that regards.
– Anurag A
Dec 10 '18 at 3:57
I had this but I didn't think it was helpful as I can't use Hensel's Lemma unless I know explicit values of f(x) and f '(x).
– mjoseph
Dec 10 '18 at 4:03
1
@mjoseph you don't really need explicit $x$, only that $f'(x)=2x$ is nonzero (using $f(x)=x^2-5$). But that is obvious from $x^2equiv 5pmod{p}$)
– user10354138
Dec 10 '18 at 4:05
Oh yes that is obvious. Thank you so much!
– mjoseph
Dec 10 '18 at 4:07
add a comment |
Consider Legendere symbol $left(frac{5}{p}right)$. By quadratic reciprocity
$$left(frac{5}{p}right)Big(frac{p}{5}Big)=(-1)^{left(frac{5-1}{2}right)left(frac{p-1}{2}right)}=1 implies left(frac{5}{p}right)=left(frac{p}{5}right).$$
But $p=2^{89}-1 equiv 2(2^2)^{44}-1 equiv 1 pmod{5}$. Thus
$$left(frac{5}{p}right)=left(frac{p}{5}right)=left(frac{1}{5}right)=1.$$
Thus $5$ is indeed a QR modulo $p$. Since $p$ is a prime thus $x^2 equiv 5 pmod{5}$ will have two non-congruent solutions. Now you can apply Hensel to see if you will continue to have two solutions as you lift from $p$ to $p^3$.
If you have two solutions for $p^3$ as well, then in all you will have $4$ solutions (combining with two from the previous congruence with $11^3$).
answered Dec 10 '18 at 3:47
Anurag A
25.6k12249
The OP isn't having trouble with that part, as demonstrated by his mod 11^3 calcuatlions. He is asking for help with finding the square-root of 5 mod p, not about lifting that square-root from mod p to mod p^3.
– user10354138
Dec 10 '18 at 3:55
@user10354138 From the language of the question, OP wants to find the number of solutions (not the actual solutions). So if we can know the number of solutions for both congruences then you can have the number of solutions for the given congruence. My answer is in that regards.
– Anurag A
Dec 10 '18 at 3:57
I had this but I didn't think it was helpful as I can't use Hensel's Lemma unless I know explicit values of f(x) and f '(x).
– mjoseph
Dec 10 '18 at 4:03
1
@mjoseph you don't really need explicit $x$, only that $f'(x)=2x$ is nonzero (using $f(x)=x^2-5$). But that is obvious from $x^2equiv 5pmod{p}$)
– user10354138
Dec 10 '18 at 4:05
Oh yes that is obvious. Thank you so much!
– mjoseph
Dec 10 '18 at 4:07
add a comment |
Consider Legendere symbol $left(frac{5}{p}right)$. By quadratic reciprocity
$$left(frac{5}{p}right)Big(frac{p}{5}Big)=(-1)^{left(frac{5-1}{2}right)left(frac{p-1}{2}right)}=1 implies left(frac{5}{p}right)=left(frac{p}{5}right).$$
But $p=2^{89}-1 equiv 2(2^2)^{44}-1 equiv 1 pmod{5}$. Thus
$$left(frac{5}{p}right)=left(frac{p}{5}right)=left(frac{1}{5}right)=1.$$
Thus $5$ is indeed a QR modulo $p$. Since $p$ is a prime thus $x^2 equiv 5 pmod{5}$ will have two non-congruent solutions. Now you can apply Hensel to see if you will continue to have two solutions as you lift from $p$ to $p^3$.
If you have two solutions for $p^3$ as well, then in all you will have $4$ solutions (combining with two from the previous congruence with $11^3$).
answered Dec 10 '18 at 3:47
Anurag A
25.6k12249
Consider Legendere symbol $left(frac{5}{p}right)$. By quadratic reciprocity
$$left(frac{5}{p}right)Big(frac{p}{5}Big)=(-1)^{left(frac{5-1}{2}right)left(frac{p-1}{2}right)}=1 implies left(frac{5}{p}right)=left(frac{p}{5}right).$$
But $p=2^{89}-1 equiv 2(2^2)^{44}-1 equiv 1 pmod{5}$. Thus
$$left(frac{5}{p}right)=left(frac{p}{5}right)=left(frac{1}{5}right)=1.$$
Thus $5$ is indeed a QR modulo $p$. Since $p$ is a prime thus $x^2 equiv 5 pmod{5}$ will have two non-congruent solutions. Now you can apply Hensel to see if you will continue to have two solutions as you lift from $p$ to $p^3$.
If you have two solutions for $p^3$ as well, then in all you will have $4$ solutions (combining with two from the previous congruence with $11^3$).
answered Dec 10 '18 at 3:47
Anurag A
25.6k12249
answered Dec 10 '18 at 3:47
Anurag A
25.6k12249
answered Dec 10 '18 at 3:47
Anurag A
25.6k12249
answered Dec 10 '18 at 3:47
Anurag A
25.6k12249
25.6k12249
The OP isn't having trouble with that part, as demonstrated by his mod 11^3 calcuatlions. He is asking for help with finding the square-root of 5 mod p, not about lifting that square-root from mod p to mod p^3.
– user10354138
Dec 10 '18 at 3:55
@user10354138 From the language of the question, OP wants to find the number of solutions (not the actual solutions). So if we can know the number of solutions for both congruences then you can have the number of solutions for the given congruence. My answer is in that regards.
– Anurag A
Dec 10 '18 at 3:57
I had this but I didn't think it was helpful as I can't use Hensel's Lemma unless I know explicit values of f(x) and f '(x).
– mjoseph
Dec 10 '18 at 4:03
1
@mjoseph you don't really need explicit $x$, only that $f'(x)=2x$ is nonzero (using $f(x)=x^2-5$). But that is obvious from $x^2equiv 5pmod{p}$)
– user10354138
Dec 10 '18 at 4:05
Oh yes that is obvious. Thank you so much!
– mjoseph
Dec 10 '18 at 4:07
add a comment |
The OP isn't having trouble with that part, as demonstrated by his mod 11^3 calcuatlions. He is asking for help with finding the square-root of 5 mod p, not about lifting that square-root from mod p to mod p^3.
– user10354138
Dec 10 '18 at 3:55
@user10354138 From the language of the question, OP wants to find the number of solutions (not the actual solutions). So if we can know the number of solutions for both congruences then you can have the number of solutions for the given congruence. My answer is in that regards.
– Anurag A
Dec 10 '18 at 3:57
I had this but I didn't think it was helpful as I can't use Hensel's Lemma unless I know explicit values of f(x) and f '(x).
– mjoseph
Dec 10 '18 at 4:03
1
@mjoseph you don't really need explicit $x$, only that $f'(x)=2x$ is nonzero (using $f(x)=x^2-5$). But that is obvious from $x^2equiv 5pmod{p}$)
– user10354138
Dec 10 '18 at 4:05
Oh yes that is obvious. Thank you so much!
– mjoseph
Dec 10 '18 at 4:07
The OP isn't having trouble with that part, as demonstrated by his mod 11^3 calcuatlions. He is asking for help with finding the square-root of 5 mod p, not about lifting that square-root from mod p to mod p^3.
– user10354138
Dec 10 '18 at 3:55
The OP isn't having trouble with that part, as demonstrated by his mod 11^3 calcuatlions. He is asking for help with finding the square-root of 5 mod p, not about lifting that square-root from mod p to mod p^3.
– user10354138
Dec 10 '18 at 3:55
@user10354138 From the language of the question, OP wants to find the number of solutions (not the actual solutions). So if we can know the number of solutions for both congruences then you can have the number of solutions for the given congruence. My answer is in that regards.
– Anurag A
Dec 10 '18 at 3:57
@user10354138 From the language of the question, OP wants to find the number of solutions (not the actual solutions). So if we can know the number of solutions for both congruences then you can have the number of solutions for the given congruence. My answer is in that regards.
– Anurag A
Dec 10 '18 at 3:57
I had this but I didn't think it was helpful as I can't use Hensel's Lemma unless I know explicit values of f(x) and f '(x).
– mjoseph
Dec 10 '18 at 4:03
I had this but I didn't think it was helpful as I can't use Hensel's Lemma unless I know explicit values of f(x) and f '(x).
– mjoseph
Dec 10 '18 at 4:03
1
1
@mjoseph you don't really need explicit $x$, only that $f'(x)=2x$ is nonzero (using $f(x)=x^2-5$). But that is obvious from $x^2equiv 5pmod{p}$)
– user10354138
Dec 10 '18 at 4:05
@mjoseph you don't really need explicit $x$, only that $f'(x)=2x$ is nonzero (using $f(x)=x^2-5$). But that is obvious from $x^2equiv 5pmod{p}$)
– user10354138
Dec 10 '18 at 4:05
Oh yes that is obvious. Thank you so much!
– mjoseph
Dec 10 '18 at 4:07
Oh yes that is obvious. Thank you so much!
– mjoseph
Dec 10 '18 at 4:07
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%2f3033409%2fx2-equiv-5-pmod1331p3%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
Are you familiar with Legendere symbol and quadratic reciprocity?
– Anurag A
Dec 10 '18 at 3:34
Yes I am familiar with both but do not totally understand when and how to apply the concept
– mjoseph
Dec 10 '18 at 3:39
Oh I think I see what you mean. So can I say that $5equiv 1pmod{4}$ so the legendre symbol of 5 on p equals the legendre symbol of p on 5. Then just replace p with its least positive residue mod 5?
– mjoseph
Dec 10 '18 at 3:42