mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-08-29, 05:48   #1
flouran
 
flouran's Avatar
 
Dec 2008

2·5·83 Posts
Default 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
flouran is offline   Reply With Quote
Old 2009-08-29, 10:19   #2
S485122
 
S485122's Avatar
 
Sep 2006
Brussels, Belgium

2×797 Posts
Default

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

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

I have no answer though.

Jacob
S485122 is offline   Reply With Quote
Old 2009-08-29, 14:12   #3
flouran
 
flouran's Avatar
 
Dec 2008

2×5×83 Posts
Default

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
flouran is offline   Reply With Quote
Old 2009-08-29, 20:40   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,969 Posts
Default

This is covered in any elementary number theory textbook. Look up "quadratic residue" on Google (or, better, Ireland & Rosen).
CRGreathouse is offline   Reply With Quote
Old 2009-08-29, 21:12   #5
flouran
 
flouran's Avatar
 
Dec 2008

11001111102 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
flouran is offline   Reply With Quote
Old 2009-08-29, 21:17   #6
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

1101100012 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
Kevin is offline   Reply With Quote
Old 2009-08-29, 22:38   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

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

Last fiddled with by CRGreathouse on 2009-08-29 at 22:53
CRGreathouse is offline   Reply With Quote
Old 2009-08-29, 22:54   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

593810 Posts
Default

Quote:
Originally Posted by flouran View Post
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, ....
CRGreathouse is offline   Reply With Quote
Old 2009-08-30, 00:26   #9
flouran
 
flouran's Avatar
 
Dec 2008

2·5·83 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
flouran is offline   Reply With Quote
Old 2009-08-30, 01:03   #10
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

6618 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
So you think 0 < n <= N <= p was intended?
I think S485122's post has the "right" interpretation.
Kevin is offline   Reply With Quote
Old 2009-08-30, 01:23   #11
flouran
 
flouran's Avatar
 
Dec 2008

2·5·83 Posts
Default

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

Thread Tools


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

All times are UTC. The time now is 13:08.

Tue Nov 24 13:08:40 UTC 2020 up 75 days, 10:19, 4 users, load averages: 1.84, 1.89, 1.99

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.