Number of Solutions to d(p)

flouran · 2009-08-29, 05:48

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?

S485122 · 2009-08-29, 10:19

I suppose that another condition is N<p, otherwise d(p) is infinite : any N=n² satisfies N-n²=0 and n <= N.

With those conditions : integers n, N and p where p is prime and 0 < n <= N < p, the solutions with n² < p are trivial and their number is int(p^0,5)+1. Only the solutions like 4-3² mod 5 are interesting.

I have no answer though.

Jacob

flouran · 2009-08-29, 14:12

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....

CRGreathouse · 2009-08-29, 20:40

This is covered in any elementary number theory textbook. Look up "quadratic residue" on Google (or, better, Ireland & Rosen).

flouran · 2009-08-29, 21:12

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?

Kevin · 2009-08-29, 21:17

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.

CRGreathouse · 2009-08-29, 22:38

Quote:

Originally Posted by Kevin

Not when you include the condition that n<N.

So you think 0 < n <= N <= p was intended?

CRGreathouse · 2009-08-29, 22:54

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, ....

flouran · 2009-08-30, 00:26

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?

Kevin · 2009-08-30, 01:03

Quote:

Originally Posted by CRGreathouse

So you think 0 < n <= N <= p was intended?

I think S485122's post has the "right" interpretation.

flouran · 2009-08-30, 01:23

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.

2009-08-29, 05:48	#1
flouran Dec 2008 7²·17 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, 14:12	#3
flouran Dec 2008 833₁₀ 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Solutions to a^2-ab+b^2 = 3^n	carpetpool	carpetpool	2	2017-02-09 06:41
New Solutions (Landau's Problems - Number Theory)	Don	Miscellaneous Math	1	2016-09-23 16:55
Possible solutions to an equation:	Vijay	Math	6	2005-04-14 05:19
Looking for solutions to w^2-n*x^2=z^2	jtavares	Factoring	3	2005-04-11 19:25
Puzzles without solutions	Orgasmic Troll	Puzzles	12	2003-07-16 09:36

2009-08-29, 10:19	#2
S485122 "Jacob" Sep 2006 Brussels, Belgium 11110101111₂ Posts	I suppose that another condition is N<p, otherwise d(p) is infinite : any N=n² satisfies N-n²=0 and n <= N. With those conditions : integers n, N and p where p is prime and 0 < n <= N < p, the solutions with n² < p are trivial and their number is int(p^0,5)+1. Only the solutions like 4-3² mod 5 are interesting. I have no answer though. Jacob

2009-08-29, 20:40	#4
CRGreathouse Aug 2006 2²×3×499 Posts	This is covered in any elementary number theory textbook. Look up "quadratic residue" on Google (or, better, Ireland & Rosen).