Prime number and divisibility












0












$begingroup$


Let $p$ be prime, prove that for any integer $r$, there at most $2$ solutions to the equation $x^2-r equiv 0pmod p$.



I don't understand the question as if $p=2$, and $r$ odd, then $x^2$ will need to be odd, and we have an infinite number of solutions.



Maybe this is true for $p>2$, but I don't really know how to prove it.










share|cite|improve this question











$endgroup$








  • 4




    $begingroup$
    They mean solutions $pmod p$. Thus, if $p=7$ and $r=2$ the only solutions would be $3,4$. For $p=2, r=1$ the only solution is $x=1$.
    $endgroup$
    – lulu
    Jan 6 at 17:06












  • $begingroup$
    makes more sense! thank you - do you have any idea how to prove it though?
    $endgroup$
    – Student number x
    Jan 6 at 17:17










  • $begingroup$
    The mean solutions modulo $p$. There are only $p$ classes. If $p=2$ then are two possible $x$, $0$ and $1$. Any other odd number is $equiv 2 pmod 2$.
    $endgroup$
    – fleablood
    Jan 6 at 17:53










  • $begingroup$
    ..... if $p = 2$ and $r=7$ then there is one solution mod $2$. $1^2 - 7equiv 0 pmod 2$ but $0^2 - 7 not equiv 0 pmod 2$. Any other odd number,say $253$ so that $253^2 - 7 equiv 0 pmod 2$ is the same solution as $253 equiv 1 pmod 2$. In the $mod 2$ system $253$ and $1$ are the same class $253 equiv 1$. So $1$ is the only solution.
    $endgroup$
    – fleablood
    Jan 6 at 17:58










  • $begingroup$
    For the record, If $x^2 equiv r pmod p$ then $(kp+x)equiv r pmod p$ so if there are any integer solutions there are an infinite number of INTEGER solutions, but we are not asking for integers solution but EQUIVALENCE solutions. $kp + x equiv x$ so they are the SAME solution. It's only one, even though ther are an infinite number of integers that are all EQUIVALENT to the one solution.
    $endgroup$
    – fleablood
    Jan 6 at 18:16
















0












$begingroup$


Let $p$ be prime, prove that for any integer $r$, there at most $2$ solutions to the equation $x^2-r equiv 0pmod p$.



I don't understand the question as if $p=2$, and $r$ odd, then $x^2$ will need to be odd, and we have an infinite number of solutions.



Maybe this is true for $p>2$, but I don't really know how to prove it.










share|cite|improve this question











$endgroup$








  • 4




    $begingroup$
    They mean solutions $pmod p$. Thus, if $p=7$ and $r=2$ the only solutions would be $3,4$. For $p=2, r=1$ the only solution is $x=1$.
    $endgroup$
    – lulu
    Jan 6 at 17:06












  • $begingroup$
    makes more sense! thank you - do you have any idea how to prove it though?
    $endgroup$
    – Student number x
    Jan 6 at 17:17










  • $begingroup$
    The mean solutions modulo $p$. There are only $p$ classes. If $p=2$ then are two possible $x$, $0$ and $1$. Any other odd number is $equiv 2 pmod 2$.
    $endgroup$
    – fleablood
    Jan 6 at 17:53










  • $begingroup$
    ..... if $p = 2$ and $r=7$ then there is one solution mod $2$. $1^2 - 7equiv 0 pmod 2$ but $0^2 - 7 not equiv 0 pmod 2$. Any other odd number,say $253$ so that $253^2 - 7 equiv 0 pmod 2$ is the same solution as $253 equiv 1 pmod 2$. In the $mod 2$ system $253$ and $1$ are the same class $253 equiv 1$. So $1$ is the only solution.
    $endgroup$
    – fleablood
    Jan 6 at 17:58










  • $begingroup$
    For the record, If $x^2 equiv r pmod p$ then $(kp+x)equiv r pmod p$ so if there are any integer solutions there are an infinite number of INTEGER solutions, but we are not asking for integers solution but EQUIVALENCE solutions. $kp + x equiv x$ so they are the SAME solution. It's only one, even though ther are an infinite number of integers that are all EQUIVALENT to the one solution.
    $endgroup$
    – fleablood
    Jan 6 at 18:16














0












0








0





$begingroup$


Let $p$ be prime, prove that for any integer $r$, there at most $2$ solutions to the equation $x^2-r equiv 0pmod p$.



I don't understand the question as if $p=2$, and $r$ odd, then $x^2$ will need to be odd, and we have an infinite number of solutions.



Maybe this is true for $p>2$, but I don't really know how to prove it.










share|cite|improve this question











$endgroup$




Let $p$ be prime, prove that for any integer $r$, there at most $2$ solutions to the equation $x^2-r equiv 0pmod p$.



I don't understand the question as if $p=2$, and $r$ odd, then $x^2$ will need to be odd, and we have an infinite number of solutions.



Maybe this is true for $p>2$, but I don't really know how to prove it.







modular-arithmetic






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 6 at 17:49









amWhy

1




1










asked Jan 6 at 17:04









Student number xStudent number x

1107




1107








  • 4




    $begingroup$
    They mean solutions $pmod p$. Thus, if $p=7$ and $r=2$ the only solutions would be $3,4$. For $p=2, r=1$ the only solution is $x=1$.
    $endgroup$
    – lulu
    Jan 6 at 17:06












  • $begingroup$
    makes more sense! thank you - do you have any idea how to prove it though?
    $endgroup$
    – Student number x
    Jan 6 at 17:17










  • $begingroup$
    The mean solutions modulo $p$. There are only $p$ classes. If $p=2$ then are two possible $x$, $0$ and $1$. Any other odd number is $equiv 2 pmod 2$.
    $endgroup$
    – fleablood
    Jan 6 at 17:53










  • $begingroup$
    ..... if $p = 2$ and $r=7$ then there is one solution mod $2$. $1^2 - 7equiv 0 pmod 2$ but $0^2 - 7 not equiv 0 pmod 2$. Any other odd number,say $253$ so that $253^2 - 7 equiv 0 pmod 2$ is the same solution as $253 equiv 1 pmod 2$. In the $mod 2$ system $253$ and $1$ are the same class $253 equiv 1$. So $1$ is the only solution.
    $endgroup$
    – fleablood
    Jan 6 at 17:58










  • $begingroup$
    For the record, If $x^2 equiv r pmod p$ then $(kp+x)equiv r pmod p$ so if there are any integer solutions there are an infinite number of INTEGER solutions, but we are not asking for integers solution but EQUIVALENCE solutions. $kp + x equiv x$ so they are the SAME solution. It's only one, even though ther are an infinite number of integers that are all EQUIVALENT to the one solution.
    $endgroup$
    – fleablood
    Jan 6 at 18:16














  • 4




    $begingroup$
    They mean solutions $pmod p$. Thus, if $p=7$ and $r=2$ the only solutions would be $3,4$. For $p=2, r=1$ the only solution is $x=1$.
    $endgroup$
    – lulu
    Jan 6 at 17:06












  • $begingroup$
    makes more sense! thank you - do you have any idea how to prove it though?
    $endgroup$
    – Student number x
    Jan 6 at 17:17










  • $begingroup$
    The mean solutions modulo $p$. There are only $p$ classes. If $p=2$ then are two possible $x$, $0$ and $1$. Any other odd number is $equiv 2 pmod 2$.
    $endgroup$
    – fleablood
    Jan 6 at 17:53










  • $begingroup$
    ..... if $p = 2$ and $r=7$ then there is one solution mod $2$. $1^2 - 7equiv 0 pmod 2$ but $0^2 - 7 not equiv 0 pmod 2$. Any other odd number,say $253$ so that $253^2 - 7 equiv 0 pmod 2$ is the same solution as $253 equiv 1 pmod 2$. In the $mod 2$ system $253$ and $1$ are the same class $253 equiv 1$. So $1$ is the only solution.
    $endgroup$
    – fleablood
    Jan 6 at 17:58










  • $begingroup$
    For the record, If $x^2 equiv r pmod p$ then $(kp+x)equiv r pmod p$ so if there are any integer solutions there are an infinite number of INTEGER solutions, but we are not asking for integers solution but EQUIVALENCE solutions. $kp + x equiv x$ so they are the SAME solution. It's only one, even though ther are an infinite number of integers that are all EQUIVALENT to the one solution.
    $endgroup$
    – fleablood
    Jan 6 at 18:16








4




4




$begingroup$
They mean solutions $pmod p$. Thus, if $p=7$ and $r=2$ the only solutions would be $3,4$. For $p=2, r=1$ the only solution is $x=1$.
$endgroup$
– lulu
Jan 6 at 17:06






$begingroup$
They mean solutions $pmod p$. Thus, if $p=7$ and $r=2$ the only solutions would be $3,4$. For $p=2, r=1$ the only solution is $x=1$.
$endgroup$
– lulu
Jan 6 at 17:06














$begingroup$
makes more sense! thank you - do you have any idea how to prove it though?
$endgroup$
– Student number x
Jan 6 at 17:17




$begingroup$
makes more sense! thank you - do you have any idea how to prove it though?
$endgroup$
– Student number x
Jan 6 at 17:17












$begingroup$
The mean solutions modulo $p$. There are only $p$ classes. If $p=2$ then are two possible $x$, $0$ and $1$. Any other odd number is $equiv 2 pmod 2$.
$endgroup$
– fleablood
Jan 6 at 17:53




$begingroup$
The mean solutions modulo $p$. There are only $p$ classes. If $p=2$ then are two possible $x$, $0$ and $1$. Any other odd number is $equiv 2 pmod 2$.
$endgroup$
– fleablood
Jan 6 at 17:53












$begingroup$
..... if $p = 2$ and $r=7$ then there is one solution mod $2$. $1^2 - 7equiv 0 pmod 2$ but $0^2 - 7 not equiv 0 pmod 2$. Any other odd number,say $253$ so that $253^2 - 7 equiv 0 pmod 2$ is the same solution as $253 equiv 1 pmod 2$. In the $mod 2$ system $253$ and $1$ are the same class $253 equiv 1$. So $1$ is the only solution.
$endgroup$
– fleablood
Jan 6 at 17:58




$begingroup$
..... if $p = 2$ and $r=7$ then there is one solution mod $2$. $1^2 - 7equiv 0 pmod 2$ but $0^2 - 7 not equiv 0 pmod 2$. Any other odd number,say $253$ so that $253^2 - 7 equiv 0 pmod 2$ is the same solution as $253 equiv 1 pmod 2$. In the $mod 2$ system $253$ and $1$ are the same class $253 equiv 1$. So $1$ is the only solution.
$endgroup$
– fleablood
Jan 6 at 17:58












$begingroup$
For the record, If $x^2 equiv r pmod p$ then $(kp+x)equiv r pmod p$ so if there are any integer solutions there are an infinite number of INTEGER solutions, but we are not asking for integers solution but EQUIVALENCE solutions. $kp + x equiv x$ so they are the SAME solution. It's only one, even though ther are an infinite number of integers that are all EQUIVALENT to the one solution.
$endgroup$
– fleablood
Jan 6 at 18:16




$begingroup$
For the record, If $x^2 equiv r pmod p$ then $(kp+x)equiv r pmod p$ so if there are any integer solutions there are an infinite number of INTEGER solutions, but we are not asking for integers solution but EQUIVALENCE solutions. $kp + x equiv x$ so they are the SAME solution. It's only one, even though ther are an infinite number of integers that are all EQUIVALENT to the one solution.
$endgroup$
– fleablood
Jan 6 at 18:16










3 Answers
3






active

oldest

votes


















1












$begingroup$

If $a$ and $x$ are solutions of $x^2 equiv r pmod p$ then $x^2 - r equiv x^2 - a^2 = (x-a)(x+a) equiv 0 pmod p$.

Since $p$ is prime, $p | (x-a)(x+a)$ means $p | (x-a)$ or $p | (x+a)$, i.e., $x equiv a$ or $-a pmod p$.

Thus there can be at most two solutions.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    As noted by others, it is possible there are no solutions. For example $x^2 - 2 equiv 0 pmod 3$ has no solutions.
    $endgroup$
    – J. W. Tanner
    Jan 7 at 18:57





















1












$begingroup$

The integers mod p are a field. In general, a polynomial of degree n over a field has at most n roots in the field. Here n=2.






share|cite|improve this answer









$endgroup$









  • 1




    $begingroup$
    Do you think this question is being at a level where the student can be expected to prove that a polynomial of degree $n$ has at most $n$ solutions? Or to take it as a given?
    $endgroup$
    – fleablood
    Jan 6 at 18:57










  • $begingroup$
    But +1 for bringing in ideas about what the question is actually asking and considering consequences.
    $endgroup$
    – fleablood
    Jan 6 at 18:58










  • $begingroup$
    I provided another answer, which is less abstract
    $endgroup$
    – J. W. Tanner
    Jan 6 at 19:18



















0












$begingroup$

$x^2 equiv r pmod p$ and $0le x < p$



$y^2 equiv r pmod p$ so that $yne x$ and $0 le y < p$



$x^2 - y^2 equiv 0 pmod p$



$(x+y)(x-y) equiv 0 pmod p$.



Now $x ne y $ so $x-y ne 0$ and $|x-y| < p$ so $pnot mid x-y$ hence $p|(x+y)$ but $0 < x+y < 2p$ so $x + y= p$



Now if we had a third option so that



$z^2 equiv r pmod p$ and $0 le z <p$ but $z ne x; z ne y; xne y$ we could use the exact same argument to conclude:



$x+y = x+z = y+z = p$. But that would imply $z = y$ (and $y = x$ and $x = z$).



So $2$ distinct solutions is a possibility (but not a certainty!) but three distinct solutions is not.



(Bear in mind it's possible that there are no solutions.)



(Also not if $x$ is one solution then so is $p-x$ and if $p$ is odd then $x$ and $p-x$ are two distinct solutions. But that does not mean there is a solution at all.)






share|cite|improve this answer











$endgroup$













  • $begingroup$
    In the second line, did you mean $y ne x$ and $0 le$ y $lt p$?
    $endgroup$
    – J. W. Tanner
    Jan 7 at 18:47












  • $begingroup$
    Yes, I did.......
    $endgroup$
    – fleablood
    Jan 7 at 21:40











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
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3064116%2fprime-number-and-divisibility%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























3 Answers
3






active

oldest

votes








3 Answers
3






active

oldest

votes









active

oldest

votes






active

oldest

votes









1












$begingroup$

If $a$ and $x$ are solutions of $x^2 equiv r pmod p$ then $x^2 - r equiv x^2 - a^2 = (x-a)(x+a) equiv 0 pmod p$.

Since $p$ is prime, $p | (x-a)(x+a)$ means $p | (x-a)$ or $p | (x+a)$, i.e., $x equiv a$ or $-a pmod p$.

Thus there can be at most two solutions.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    As noted by others, it is possible there are no solutions. For example $x^2 - 2 equiv 0 pmod 3$ has no solutions.
    $endgroup$
    – J. W. Tanner
    Jan 7 at 18:57


















1












$begingroup$

If $a$ and $x$ are solutions of $x^2 equiv r pmod p$ then $x^2 - r equiv x^2 - a^2 = (x-a)(x+a) equiv 0 pmod p$.

Since $p$ is prime, $p | (x-a)(x+a)$ means $p | (x-a)$ or $p | (x+a)$, i.e., $x equiv a$ or $-a pmod p$.

Thus there can be at most two solutions.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    As noted by others, it is possible there are no solutions. For example $x^2 - 2 equiv 0 pmod 3$ has no solutions.
    $endgroup$
    – J. W. Tanner
    Jan 7 at 18:57
















1












1








1





$begingroup$

If $a$ and $x$ are solutions of $x^2 equiv r pmod p$ then $x^2 - r equiv x^2 - a^2 = (x-a)(x+a) equiv 0 pmod p$.

Since $p$ is prime, $p | (x-a)(x+a)$ means $p | (x-a)$ or $p | (x+a)$, i.e., $x equiv a$ or $-a pmod p$.

Thus there can be at most two solutions.






share|cite|improve this answer











$endgroup$



If $a$ and $x$ are solutions of $x^2 equiv r pmod p$ then $x^2 - r equiv x^2 - a^2 = (x-a)(x+a) equiv 0 pmod p$.

Since $p$ is prime, $p | (x-a)(x+a)$ means $p | (x-a)$ or $p | (x+a)$, i.e., $x equiv a$ or $-a pmod p$.

Thus there can be at most two solutions.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Jan 7 at 0:34

























answered Jan 6 at 19:00









J. W. TannerJ. W. Tanner

2129




2129












  • $begingroup$
    As noted by others, it is possible there are no solutions. For example $x^2 - 2 equiv 0 pmod 3$ has no solutions.
    $endgroup$
    – J. W. Tanner
    Jan 7 at 18:57




















  • $begingroup$
    As noted by others, it is possible there are no solutions. For example $x^2 - 2 equiv 0 pmod 3$ has no solutions.
    $endgroup$
    – J. W. Tanner
    Jan 7 at 18:57


















$begingroup$
As noted by others, it is possible there are no solutions. For example $x^2 - 2 equiv 0 pmod 3$ has no solutions.
$endgroup$
– J. W. Tanner
Jan 7 at 18:57






$begingroup$
As noted by others, it is possible there are no solutions. For example $x^2 - 2 equiv 0 pmod 3$ has no solutions.
$endgroup$
– J. W. Tanner
Jan 7 at 18:57













1












$begingroup$

The integers mod p are a field. In general, a polynomial of degree n over a field has at most n roots in the field. Here n=2.






share|cite|improve this answer









$endgroup$









  • 1




    $begingroup$
    Do you think this question is being at a level where the student can be expected to prove that a polynomial of degree $n$ has at most $n$ solutions? Or to take it as a given?
    $endgroup$
    – fleablood
    Jan 6 at 18:57










  • $begingroup$
    But +1 for bringing in ideas about what the question is actually asking and considering consequences.
    $endgroup$
    – fleablood
    Jan 6 at 18:58










  • $begingroup$
    I provided another answer, which is less abstract
    $endgroup$
    – J. W. Tanner
    Jan 6 at 19:18
















1












$begingroup$

The integers mod p are a field. In general, a polynomial of degree n over a field has at most n roots in the field. Here n=2.






share|cite|improve this answer









$endgroup$









  • 1




    $begingroup$
    Do you think this question is being at a level where the student can be expected to prove that a polynomial of degree $n$ has at most $n$ solutions? Or to take it as a given?
    $endgroup$
    – fleablood
    Jan 6 at 18:57










  • $begingroup$
    But +1 for bringing in ideas about what the question is actually asking and considering consequences.
    $endgroup$
    – fleablood
    Jan 6 at 18:58










  • $begingroup$
    I provided another answer, which is less abstract
    $endgroup$
    – J. W. Tanner
    Jan 6 at 19:18














1












1








1





$begingroup$

The integers mod p are a field. In general, a polynomial of degree n over a field has at most n roots in the field. Here n=2.






share|cite|improve this answer









$endgroup$



The integers mod p are a field. In general, a polynomial of degree n over a field has at most n roots in the field. Here n=2.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Jan 6 at 18:19









J. W. TannerJ. W. Tanner

2129




2129








  • 1




    $begingroup$
    Do you think this question is being at a level where the student can be expected to prove that a polynomial of degree $n$ has at most $n$ solutions? Or to take it as a given?
    $endgroup$
    – fleablood
    Jan 6 at 18:57










  • $begingroup$
    But +1 for bringing in ideas about what the question is actually asking and considering consequences.
    $endgroup$
    – fleablood
    Jan 6 at 18:58










  • $begingroup$
    I provided another answer, which is less abstract
    $endgroup$
    – J. W. Tanner
    Jan 6 at 19:18














  • 1




    $begingroup$
    Do you think this question is being at a level where the student can be expected to prove that a polynomial of degree $n$ has at most $n$ solutions? Or to take it as a given?
    $endgroup$
    – fleablood
    Jan 6 at 18:57










  • $begingroup$
    But +1 for bringing in ideas about what the question is actually asking and considering consequences.
    $endgroup$
    – fleablood
    Jan 6 at 18:58










  • $begingroup$
    I provided another answer, which is less abstract
    $endgroup$
    – J. W. Tanner
    Jan 6 at 19:18








1




1




$begingroup$
Do you think this question is being at a level where the student can be expected to prove that a polynomial of degree $n$ has at most $n$ solutions? Or to take it as a given?
$endgroup$
– fleablood
Jan 6 at 18:57




$begingroup$
Do you think this question is being at a level where the student can be expected to prove that a polynomial of degree $n$ has at most $n$ solutions? Or to take it as a given?
$endgroup$
– fleablood
Jan 6 at 18:57












$begingroup$
But +1 for bringing in ideas about what the question is actually asking and considering consequences.
$endgroup$
– fleablood
Jan 6 at 18:58




$begingroup$
But +1 for bringing in ideas about what the question is actually asking and considering consequences.
$endgroup$
– fleablood
Jan 6 at 18:58












$begingroup$
I provided another answer, which is less abstract
$endgroup$
– J. W. Tanner
Jan 6 at 19:18




$begingroup$
I provided another answer, which is less abstract
$endgroup$
– J. W. Tanner
Jan 6 at 19:18











0












$begingroup$

$x^2 equiv r pmod p$ and $0le x < p$



$y^2 equiv r pmod p$ so that $yne x$ and $0 le y < p$



$x^2 - y^2 equiv 0 pmod p$



$(x+y)(x-y) equiv 0 pmod p$.



Now $x ne y $ so $x-y ne 0$ and $|x-y| < p$ so $pnot mid x-y$ hence $p|(x+y)$ but $0 < x+y < 2p$ so $x + y= p$



Now if we had a third option so that



$z^2 equiv r pmod p$ and $0 le z <p$ but $z ne x; z ne y; xne y$ we could use the exact same argument to conclude:



$x+y = x+z = y+z = p$. But that would imply $z = y$ (and $y = x$ and $x = z$).



So $2$ distinct solutions is a possibility (but not a certainty!) but three distinct solutions is not.



(Bear in mind it's possible that there are no solutions.)



(Also not if $x$ is one solution then so is $p-x$ and if $p$ is odd then $x$ and $p-x$ are two distinct solutions. But that does not mean there is a solution at all.)






share|cite|improve this answer











$endgroup$













  • $begingroup$
    In the second line, did you mean $y ne x$ and $0 le$ y $lt p$?
    $endgroup$
    – J. W. Tanner
    Jan 7 at 18:47












  • $begingroup$
    Yes, I did.......
    $endgroup$
    – fleablood
    Jan 7 at 21:40
















0












$begingroup$

$x^2 equiv r pmod p$ and $0le x < p$



$y^2 equiv r pmod p$ so that $yne x$ and $0 le y < p$



$x^2 - y^2 equiv 0 pmod p$



$(x+y)(x-y) equiv 0 pmod p$.



Now $x ne y $ so $x-y ne 0$ and $|x-y| < p$ so $pnot mid x-y$ hence $p|(x+y)$ but $0 < x+y < 2p$ so $x + y= p$



Now if we had a third option so that



$z^2 equiv r pmod p$ and $0 le z <p$ but $z ne x; z ne y; xne y$ we could use the exact same argument to conclude:



$x+y = x+z = y+z = p$. But that would imply $z = y$ (and $y = x$ and $x = z$).



So $2$ distinct solutions is a possibility (but not a certainty!) but three distinct solutions is not.



(Bear in mind it's possible that there are no solutions.)



(Also not if $x$ is one solution then so is $p-x$ and if $p$ is odd then $x$ and $p-x$ are two distinct solutions. But that does not mean there is a solution at all.)






share|cite|improve this answer











$endgroup$













  • $begingroup$
    In the second line, did you mean $y ne x$ and $0 le$ y $lt p$?
    $endgroup$
    – J. W. Tanner
    Jan 7 at 18:47












  • $begingroup$
    Yes, I did.......
    $endgroup$
    – fleablood
    Jan 7 at 21:40














0












0








0





$begingroup$

$x^2 equiv r pmod p$ and $0le x < p$



$y^2 equiv r pmod p$ so that $yne x$ and $0 le y < p$



$x^2 - y^2 equiv 0 pmod p$



$(x+y)(x-y) equiv 0 pmod p$.



Now $x ne y $ so $x-y ne 0$ and $|x-y| < p$ so $pnot mid x-y$ hence $p|(x+y)$ but $0 < x+y < 2p$ so $x + y= p$



Now if we had a third option so that



$z^2 equiv r pmod p$ and $0 le z <p$ but $z ne x; z ne y; xne y$ we could use the exact same argument to conclude:



$x+y = x+z = y+z = p$. But that would imply $z = y$ (and $y = x$ and $x = z$).



So $2$ distinct solutions is a possibility (but not a certainty!) but three distinct solutions is not.



(Bear in mind it's possible that there are no solutions.)



(Also not if $x$ is one solution then so is $p-x$ and if $p$ is odd then $x$ and $p-x$ are two distinct solutions. But that does not mean there is a solution at all.)






share|cite|improve this answer











$endgroup$



$x^2 equiv r pmod p$ and $0le x < p$



$y^2 equiv r pmod p$ so that $yne x$ and $0 le y < p$



$x^2 - y^2 equiv 0 pmod p$



$(x+y)(x-y) equiv 0 pmod p$.



Now $x ne y $ so $x-y ne 0$ and $|x-y| < p$ so $pnot mid x-y$ hence $p|(x+y)$ but $0 < x+y < 2p$ so $x + y= p$



Now if we had a third option so that



$z^2 equiv r pmod p$ and $0 le z <p$ but $z ne x; z ne y; xne y$ we could use the exact same argument to conclude:



$x+y = x+z = y+z = p$. But that would imply $z = y$ (and $y = x$ and $x = z$).



So $2$ distinct solutions is a possibility (but not a certainty!) but three distinct solutions is not.



(Bear in mind it's possible that there are no solutions.)



(Also not if $x$ is one solution then so is $p-x$ and if $p$ is odd then $x$ and $p-x$ are two distinct solutions. But that does not mean there is a solution at all.)







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Jan 7 at 21:41

























answered Jan 6 at 18:13









fleabloodfleablood

68.9k22685




68.9k22685












  • $begingroup$
    In the second line, did you mean $y ne x$ and $0 le$ y $lt p$?
    $endgroup$
    – J. W. Tanner
    Jan 7 at 18:47












  • $begingroup$
    Yes, I did.......
    $endgroup$
    – fleablood
    Jan 7 at 21:40


















  • $begingroup$
    In the second line, did you mean $y ne x$ and $0 le$ y $lt p$?
    $endgroup$
    – J. W. Tanner
    Jan 7 at 18:47












  • $begingroup$
    Yes, I did.......
    $endgroup$
    – fleablood
    Jan 7 at 21:40
















$begingroup$
In the second line, did you mean $y ne x$ and $0 le$ y $lt p$?
$endgroup$
– J. W. Tanner
Jan 7 at 18:47






$begingroup$
In the second line, did you mean $y ne x$ and $0 le$ y $lt p$?
$endgroup$
– J. W. Tanner
Jan 7 at 18:47














$begingroup$
Yes, I did.......
$endgroup$
– fleablood
Jan 7 at 21:40




$begingroup$
Yes, I did.......
$endgroup$
– fleablood
Jan 7 at 21:40


















draft saved

draft discarded




















































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.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3064116%2fprime-number-and-divisibility%23new-answer', 'question_page');
}
);

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







Popular posts from this blog

1300-talet

1300-talet

Display a custom attribute below product name in the front-end Magento 1.9.3.8