[math-fun] Difference of Squares Modulo p?
Hello, I've been trying to prove the following statement, which I believe to be true: Let $p$ be a prime number, and let $n$ and $m$ be two distinct positive integers such that $0\le n , m \le (p-1)$. Then, $m^2 - n^2 = a (mod p)$ has exactly (p-1) solutions for each $0\le b \le (p-1)$. I've been just writing out a table of $m$ and $n$, and I tried to use some kind of counting argument, but it has gotten me nowhere. Could someone give me a hint? Best, Ki -- If I'm not working, then I must be depressed.
Oops. I had changed the second "a" into a "b" without changing the first "a". I meant to say: Let $p$ be a prime number, and let $n$ and $m$ be two distinct positive integers such that $0\le n , m \le (p-1)$. Then, $m^2 - n^2 = b (mod p)$ has exactly (p-1) solutions for each $0\le b \le (p-1)$. On Mon, Aug 25, 2008 at 10:57 PM, Ki Song <kiwisquash@math.sunysb.edu>wrote:
Hello,
I've been trying to prove the following statement, which I believe to be true:
Let $p$ be a prime number, and let $n$ and $m$ be two distinct positive integers such that $0\le n , m \le (p-1)$. Then, $m^2 - n^2 = a (mod p)$ has exactly (p-1) solutions for each $0\le b \le (p-1)$.
I've been just writing out a table of $m$ and $n$, and I tried to use some kind of counting argument, but it has gotten me nowhere. Could someone give me a hint?
Best,
Ki
-- If I'm not working, then I must be depressed.
-- If I'm not working, then I must be depressed.
Try setting m = n + k. J.P. On 8/25/08, Ki Song <kiwisquash@math.sunysb.edu> wrote:
Oops. I had changed the second "a" into a "b" without changing the first "a".
I meant to say:
Let $p$ be a prime number, and let $n$ and $m$ be two distinct positive integers such that $0\le n , m \le (p-1)$. Then, $m^2 - n^2 = b (mod p)$ has exactly (p-1) solutions for each $0\le b \le (p-1)$.
On Mon, Aug 25, 2008 at 10:57 PM, Ki Song <kiwisquash@math.sunysb.edu
wrote:
Hello,
I've been trying to prove the following statement, which I believe to be true:
Let $p$ be a prime number, and let $n$ and $m$ be two distinct positive integers such that $0\le n , m \le (p-1)$. Then, $m^2 - n^2 = a (mod p)$ has exactly (p-1) solutions for each $0\le b \le (p-1)$.
I've been just writing out a table of $m$ and $n$, and I tried to use some kind of counting argument, but it has gotten me nowhere. Could someone give me a hint?
Best,
Ki
-- If I'm not working, then I must be depressed.
-- If I'm not working, then I must be depressed. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Oh, wow. I actually DID try something like that last night, but for some reason, I had no idea what to do with it. The original problem was the following: Find the modulus. Sum_{n=0}^{p-1} exp( 2pi *i n^2 / p ), where p is a prime number, After some examples, I guessed that the modulus would be \sqrt{p}, and trying to prove that reduced to the problem I posted about earlier. Is there a more clever way of solving this? On Tue, Aug 26, 2008 at 6:07 AM, J.P. Grossman <jpg@alum.mit.edu> wrote:
Try setting m = n + k.
J.P.
On 8/25/08, Ki Song <kiwisquash@math.sunysb.edu> wrote:
Oops. I had changed the second "a" into a "b" without changing the first "a".
I meant to say:
Let $p$ be a prime number, and let $n$ and $m$ be two distinct positive integers such that $0\le n , m \le (p-1)$. Then, $m^2 - n^2 = b (mod p)$ has exactly (p-1) solutions for each $0\le b \le (p-1)$.
On Mon, Aug 25, 2008 at 10:57 PM, Ki Song <kiwisquash@math.sunysb.edu
wrote:
Hello,
I've been trying to prove the following statement, which I believe to
be
true:
Let $p$ be a prime number, and let $n$ and $m$ be two distinct positive integers such that $0\le n , m \le (p-1)$. Then, $m^2 - n^2 = a (mod p)$ has exactly (p-1) solutions for each $0\le b \le (p-1)$.
I've been just writing out a table of $m$ and $n$, and I tried to use some kind of counting argument, but it has gotten me nowhere. Could someone give me a hint?
Best,
Ki
-- If I'm not working, then I must be depressed.
-- If I'm not working, then I must be depressed. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- If I'm not working, then I must be depressed.
It's a bit faster to make the substitution u = m+n, v = m-n (deal with p = 2 separately), and you end up with |x|^2 = Sum_{u=0}^{p-1} Sum_{v=0}^{p-1} exp(2pi *i uv/p) = p J.P. On 8/26/08, Ki Song <kiwisquash@math.sunysb.edu> wrote:
Oh, wow. I actually DID try something like that last night, but for some reason, I had no idea what to do with it.
The original problem was the following:
Find the modulus.
Sum_{n=0}^{p-1} exp( 2pi *i n^2 / p ), where p is a prime number,
After some examples, I guessed that the modulus would be \sqrt{p}, and trying to prove that reduced to the problem I posted about earlier.
Is there a more clever way of solving this?
On Tue, Aug 26, 2008 at 6:07 AM, J.P. Grossman <jpg@alum.mit.edu> wrote:
Try setting m = n + k.
J.P.
On 8/25/08, Ki Song <kiwisquash@math.sunysb.edu> wrote:
Oops. I had changed the second "a" into a "b" without changing the
first
"a".
I meant to say:
Let $p$ be a prime number, and let $n$ and $m$ be two distinct positive integers such that $0\le n , m \le (p-1)$. Then, $m^2 - n^2 = b (mod p)$ has exactly (p-1) solutions for each $0\le b \le (p-1)$.
On Mon, Aug 25, 2008 at 10:57 PM, Ki Song <kiwisquash@math.sunysb.edu
wrote:
Hello,
I've been trying to prove the following statement, which I believe to be true:
Let $p$ be a prime number, and let $n$ and $m$ be two distinct positive integers such that $0\le n , m \le (p-1)$. Then, $m^2 - n^2 = a (mod p)$ has exactly (p-1) solutions for each $0\le b \le (p-1)$.
I've been just writing out a table of $m$ and $n$, and I tried to use some kind of counting argument, but it has gotten me nowhere. Could someone give me a hint?
Best,
Ki
-- If I'm not working, then I must be depressed.
-- If I'm not working, then I must be depressed. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- If I'm not working, then I must be depressed. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
J.P. Grossman -
Ki Song