mersenneforum.org > Math Number of Solutions to d(p)
 Register FAQ Search Today's Posts Mark Forums Read

 2009-08-29, 05:48 #1 flouran     Dec 2008 83310 Posts Number of Solutions to d(p) What is the number of solutions d(p) of $N-n^2 \equiv 0 \pmod p$ where p is a prime and n and N are positive and N => n? Last fiddled with by flouran on 2009-08-29 at 05:56
 2009-08-29, 10:19 #2 S485122     Sep 2006 Brussels, Belgium 164710 Posts I suppose that another condition is N
 2009-08-29, 14:12 #3 flouran     Dec 2008 72·17 Posts I only have a trivial estimate for d(p). That is, d(p) < p-1 if $p \not\mid F(0)$. But that's not at all interesting.... Last fiddled with by flouran on 2009-08-29 at 14:12
 2009-08-29, 20:40 #4 CRGreathouse     Aug 2006 3·1,987 Posts This is covered in any elementary number theory textbook. Look up "quadratic residue" on Google (or, better, Ireland & Rosen).
2009-08-29, 21:12   #5
flouran

Dec 2008

72×17 Posts

Quote:
 Originally Posted by CRGreathouse This is covered in any elementary number theory textbook. Look up "quadratic residue" on Google (or, better, Ireland & Rosen).
So basically, if we let p be a prime, then since the congruence $n^2 \equiv 0 \pmod p$ has only the solution n=0, then $N-n^2 \equiv 0 \pmod p$ has only 1 solution as well?

Last fiddled with by flouran on 2009-08-29 at 21:16

2009-08-29, 21:17   #6
Kevin

Aug 2002
Ann Arbor, MI

433 Posts

Quote:
 Originally Posted by CRGreathouse This is covered in any elementary number theory textbook. Look up "quadratic residue" on Google (or, better, Ireland & Rosen).
Not when you include the condition that n<N.

2009-08-29, 22:38   #7
CRGreathouse

Aug 2006

3×1,987 Posts

Quote:
 Originally Posted by Kevin Not when you include the condition that n
So you think 0 < n <= N <= p was intended?

Last fiddled with by CRGreathouse on 2009-08-29 at 22:53

2009-08-29, 22:54   #8
CRGreathouse

Aug 2006

174916 Posts

Quote:
 Originally Posted by flouran So basically, if we let p be a prime, then since the congruence $n^2 \equiv 0 \pmod p$ has only the solution n=0, then $N-n^2 \equiv 0 \pmod p$ has only 1 solution as well?
I can't come up with any interpretation under which that would be true. Can you explain in more detail what you mean? The best guess I have gives 2, 2, 4, 3, 6, 8, 11, 10, 9, 18, 13, 20, ... solutions for p = 2, 3, 5, 7, 11, ....

2009-08-30, 00:26   #9
flouran

Dec 2008

72·17 Posts

Quote:
 Originally Posted by CRGreathouse I can't come up with any interpretation under which that would be true. Can you explain in more detail what you mean? The best guess I have gives 2, 2, 4, 3, 6, 8, 11, 10, 9, 18, 13, 20, ... solutions for p = 2, 3, 5, 7, 11, ....
Let F(n) be a polynomial of degree g => 1 with integer coefficients. Let d(p) denote the number of solutions to the congruency $F(n) \equiv 0 \pmod p$ for all primes p (and suppose that d(p) < p for all p). We may take F(n) = N-n^2, where N is an integer greater than (or equal to) n. What is d(p) then in this case?

Last fiddled with by flouran on 2009-08-30 at 00:32

2009-08-30, 01:03   #10
Kevin

Aug 2002
Ann Arbor, MI

6618 Posts

Quote:
 Originally Posted by CRGreathouse So you think 0 < n <= N <= p was intended?
I think S485122's post has the "right" interpretation.

2009-08-30, 01:23   #11
flouran

Dec 2008

34116 Posts

Quote:
 Originally Posted by Kevin I think S485122's post has the "right" interpretation.
I think d(2) = 1, and d(p) = 2 for all odd primes p.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool carpetpool 2 2017-02-09 06:41 Don Miscellaneous Math 1 2016-09-23 16:55 Vijay Math 6 2005-04-14 05:19 jtavares Factoring 3 2005-04-11 19:25 Orgasmic Troll Puzzles 12 2003-07-16 09:36

All times are UTC. The time now is 20:27.

Tue Jan 19 20:27:38 UTC 2021 up 47 days, 16:38, 0 users, load averages: 2.92, 2.55, 2.29