Prime number and divisibility The 2019 Stack Overflow Developer Survey Results Are In Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)How to prove that the number of solutions of $ x^2 equiv a pmodp$ is 0 or 2?Congruences and prime powersModularity and prime number sequenceDivisibility of Fibonacci Sequence mod primeHow do I prove that a number $p>2$ is prime if and only if $(p-1)! equiv -1 pmod p$?Proof Using Modular Arithmetic - Divisibility using co-prime numbersWhat is the distribution of $x^2pmod p$ where $p$ is a prime number, and $x in mathbbZ_p$?Show that an odd number of a, b, and c satisfy $abcequiv 1pmod3$Take p an odd prime and $a$ an integer with order $d$ mod p, is it true that if $d$ is even, then $a^fracd2 equiv -1pmod p$How many solutions do $x^p-1 equiv 1 pmod p$ and $x^p-1 equiv 2 pmod p$ have?If $p equiv 1 pmod 4$ where $p$ is an odd prime, then $x^2 equiv -1 pmod p^k$ where $k$ is any integer has $2$ solutions.
Mortgage adviser recommends a longer term than necessary combined with overpayments
Circular reasoning in L'Hopital's rule
Loose spokes after only a few rides
How to type a long/em dash `—`
One-dimensional Japanese puzzle
Word for: a synonym with a positive connotation?
What is the padding with red substance inside of steak packaging?
Does Parliament hold absolute power in the UK?
Windows 10: How to Lock (not sleep) laptop on lid close?
Make it rain characters
What information about me do stores get via my credit card?
Presidential Pardon
Can withdrawing asylum be illegal?
Single author papers against my advisor's will?
Student Loan from years ago pops up and is taking my salary
What aspect of planet Earth must be changed to prevent the industrial revolution?
What can I do if neighbor is blocking my solar panels intentionally?
Are spiders unable to hurt humans, especially very small spiders?
Did the new image of black hole confirm the general theory of relativity?
Did the UK government pay "millions and millions of dollars" to try to snag Julian Assange?
Why not take a picture of a closer black hole?
What to do when moving next to a bird sanctuary with a loosely-domesticated cat?
US Healthcare consultation for visitors
Does Parliament need to approve the new Brexit delay to 31 October 2019?
Prime number and divisibility
The 2019 Stack Overflow Developer Survey Results Are In
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)How to prove that the number of solutions of $ x^2 equiv a pmodp$ is 0 or 2?Congruences and prime powersModularity and prime number sequenceDivisibility of Fibonacci Sequence mod primeHow do I prove that a number $p>2$ is prime if and only if $(p-1)! equiv -1 pmod p$?Proof Using Modular Arithmetic - Divisibility using co-prime numbersWhat is the distribution of $x^2pmod p$ where $p$ is a prime number, and $x in mathbbZ_p$?Show that an odd number of a, b, and c satisfy $abcequiv 1pmod3$Take p an odd prime and $a$ an integer with order $d$ mod p, is it true that if $d$ is even, then $a^fracd2 equiv -1pmod p$How many solutions do $x^p-1 equiv 1 pmod p$ and $x^p-1 equiv 2 pmod p$ have?If $p equiv 1 pmod 4$ where $p$ is an odd prime, then $x^2 equiv -1 pmod p^k$ where $k$ is any integer has $2$ solutions.
$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.
modular-arithmetic
edited Jan 6 at 17:49
Namaste
1
asked Jan 6 at 17:04
Student number xStudent number x
1108
$endgroup$
|
show 1 more comment
$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.
modular-arithmetic
edited Jan 6 at 17:49
Namaste
1
asked Jan 6 at 17:04
Student number xStudent number x
1108
$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
|
show 1 more comment
$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.
modular-arithmetic
edited Jan 6 at 17:49
Namaste
1
asked Jan 6 at 17:04
Student number xStudent number x
1108
$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
modular-arithmetic
edited Jan 6 at 17:49
Namaste
1
asked Jan 6 at 17:04
Student number xStudent number x
1108
edited Jan 6 at 17:49
Namaste
1
asked Jan 6 at 17:04
Student number xStudent number x
1108
edited Jan 6 at 17:49
Namaste
1
edited Jan 6 at 17:49
Namaste
1
edited Jan 6 at 17:49
Namaste
1
1
asked Jan 6 at 17:04
Student number xStudent number x
1108
asked Jan 6 at 17:04
Student number xStudent number x
1108
asked Jan 6 at 17:04
Student number xStudent number x
1108
1108
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
|
show 1 more comment
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
|
show 1 more comment
3 Answers
3
active
oldest
votes
$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.
answered Jan 6 at 19:00
J. W. TannerJ. W. Tanner
4,7721420
$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
add a comment |
$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.
answered Jan 6 at 18:19
J. W. TannerJ. W. Tanner
4,7721420
$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
$begingroup$
@BillDubuque: Not clear why you commented here -- that edit was on a different question/answer -- but anyway at least "positive" is now spelled correctly there
$endgroup$
– J. W. Tanner
Mar 24 at 18:05
$begingroup$
@BillDubuque: actually I didn't know until now that you couldn't ping me there
$endgroup$
– J. W. Tanner
Mar 24 at 18:29
add a comment |
$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.)
answered Jan 6 at 18:13
fleabloodfleablood
1
$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
add a comment |
Your Answer
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%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
$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.
answered Jan 6 at 19:00
J. W. TannerJ. W. Tanner
4,7721420
$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
add a comment |
$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.
answered Jan 6 at 19:00
J. W. TannerJ. W. Tanner
4,7721420
$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
add a comment |
$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.
answered Jan 6 at 19:00
J. W. TannerJ. W. Tanner
4,7721420
$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.
answered Jan 6 at 19:00
J. W. TannerJ. W. Tanner
4,7721420
edited Mar 24 at 18:31
answered Jan 6 at 19:00
J. W. TannerJ. W. Tanner
4,7721420
answered Jan 6 at 19:00
J. W. TannerJ. W. Tanner
4,7721420
answered Jan 6 at 19:00
J. W. TannerJ. W. Tanner
4,7721420
4,7721420
$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
add a comment |
$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
add a comment |
$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.
answered Jan 6 at 18:19
J. W. TannerJ. W. Tanner
4,7721420
$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
$begingroup$
@BillDubuque: Not clear why you commented here -- that edit was on a different question/answer -- but anyway at least "positive" is now spelled correctly there
$endgroup$
– J. W. Tanner
Mar 24 at 18:05
$begingroup$
@BillDubuque: actually I didn't know until now that you couldn't ping me there
$endgroup$
– J. W. Tanner
Mar 24 at 18:29
add a comment |
$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.
answered Jan 6 at 18:19
J. W. TannerJ. W. Tanner
4,7721420
$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
$begingroup$
@BillDubuque: Not clear why you commented here -- that edit was on a different question/answer -- but anyway at least "positive" is now spelled correctly there
$endgroup$
– J. W. Tanner
Mar 24 at 18:05
$begingroup$
@BillDubuque: actually I didn't know until now that you couldn't ping me there
$endgroup$
– J. W. Tanner
Mar 24 at 18:29
add a comment |
$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.
answered Jan 6 at 18:19
J. W. TannerJ. W. Tanner
4,7721420
$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.
answered Jan 6 at 18:19
J. W. TannerJ. W. Tanner
4,7721420
answered Jan 6 at 18:19
J. W. TannerJ. W. Tanner
4,7721420
answered Jan 6 at 18:19
J. W. TannerJ. W. Tanner
4,7721420
answered Jan 6 at 18:19
J. W. TannerJ. W. Tanner
4,7721420
4,7721420
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
$begingroup$
@BillDubuque: Not clear why you commented here -- that edit was on a different question/answer -- but anyway at least "positive" is now spelled correctly there
$endgroup$
– J. W. Tanner
Mar 24 at 18:05
$begingroup$
@BillDubuque: actually I didn't know until now that you couldn't ping me there
$endgroup$
– J. W. Tanner
Mar 24 at 18:29
add a comment |
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
$begingroup$
@BillDubuque: Not clear why you commented here -- that edit was on a different question/answer -- but anyway at least "positive" is now spelled correctly there
$endgroup$
– J. W. Tanner
Mar 24 at 18:05
$begingroup$
@BillDubuque: actually I didn't know until now that you couldn't ping me there
$endgroup$
– J. W. Tanner
Mar 24 at 18:29
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
$begingroup$
@BillDubuque: Not clear why you commented here -- that edit was on a different question/answer -- but anyway at least "positive" is now spelled correctly there
$endgroup$
– J. W. Tanner
Mar 24 at 18:05
$begingroup$
@BillDubuque: Not clear why you commented here -- that edit was on a different question/answer -- but anyway at least "positive" is now spelled correctly there
$endgroup$
– J. W. Tanner
Mar 24 at 18:05
$begingroup$
@BillDubuque: actually I didn't know until now that you couldn't ping me there
$endgroup$
– J. W. Tanner
Mar 24 at 18:29
$begingroup$
@BillDubuque: actually I didn't know until now that you couldn't ping me there
$endgroup$
– J. W. Tanner
Mar 24 at 18:29
add a comment |
$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.)
answered Jan 6 at 18:13
fleabloodfleablood
1
$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
add a comment |
$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.)
answered Jan 6 at 18:13
fleabloodfleablood
1
$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
add a comment |
$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.)
answered Jan 6 at 18:13
fleabloodfleablood
1
$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.)
answered Jan 6 at 18:13
fleabloodfleablood
1
edited Jan 7 at 21:41
answered Jan 6 at 18:13
fleabloodfleablood
1
answered Jan 6 at 18:13
fleabloodfleablood
1
answered Jan 6 at 18:13
fleabloodfleablood
1
1
$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
add a comment |
$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
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%2f3064116%2fprime-number-and-divisibility%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
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