Number of Solutions to d(p) vs F(n) Modulo Prime?

  • Thread starter flouran
  • Start date
In summary: Consider d(p,N) : take remainder of N divided by p . Let it be r.Now if r is a perfect square , then d(p.N) will have infinite solutions of the form r + kpelse there is no solutionWould d(p) be different if it was instead the number of solutions to:F(n) \equiv 0 \pmod p? Here F(n) = n - q where q = m^2 is a perfect square where m is a natural number.Is m fixed or can it take any integer value? Are there any limits on the value of n or m?
  • #1
flouran
64
0
What is the number of solutions d(p) of
[tex]N-n^2 \equiv 0 \pmod p[/tex]

where p is a prime and n and N are positive and N => n?
 
Physics news on Phys.org
  • #2
I'm not sure what you are really asking, but for each prime p, there are an infinite number of solutions (N,n) satisfying your criteria. Take n = 1, and N= k*p + 1, for k = 1, 2, 3, ...
 
  • #3
JustSam said:
I'm not sure what you are really asking, but for each prime p, there are an infinite number of solutions (N,n) satisfying your criteria. Take n = 1, and N= k*p + 1, for k = 1, 2, 3, ...
I have a trivial upper bound for d(p). That is, d(p) < p-1 for [tex]p\nmid N[/tex]. I think that suffices for my usages of d(p) for now.
 
Last edited:
  • #4
I am an idiot.
Hint: quadratic residue
 
  • #5
I still don't understand what you are asking.
flouran said:
What is the number of solutions d(p) of
[tex]N-n^2 \equiv 0 \pmod p[/tex]

where p is a prime and n and N are positive and N => n?
Let p be a prime number. Define d(p) as the cardinality of

[tex]$
\{ (N,n) : N \ge 1, n \ge 1, N \ge n, N \equiv n^2 \pmod p \}
[/tex]

Clearly you intend something different.
 
  • #6
JustSam said:
I still don't understand what you are asking.

Let p be a prime number. Define d(p) as the cardinality of

[tex]$
\{ (N,n) : N \ge 1, n \ge 1, N \ge n, N \equiv n^2 \pmod p \}
[/tex]

Clearly you intend something different.

I can be clearer:
Let F(n) be a polynomial of degree g => 1 with integer coefficients. Let d(p) denote the number of solutions to the congruency [tex]F(n) \equiv 0 \pmod p[/tex] 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 edited:
  • #7
flouran said:
I can be clearer:
Let F(n) be a polynomial of degree g => 1 with integer coefficients. Let d(p) denote the number of solutions to the congruency [tex]F(n) \equiv 0 \pmod p[/tex] 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?
Let p be a prime number. Define d(p) as:

[tex]$
\max_{N \ge 1} \left| \{ n \pmod p : N \equiv n^2 \pmod p \} \right|
[/tex]

Then d(2) = 1, d(p) = 2 for odd primes p.
 
  • #8
JustSam said:
Let p be a prime number. Define d(p) as:

[tex]$
\max_{N \ge 1} \left| \{ n \pmod p : N \equiv n^2 \pmod p \} \right|
[/tex]

Then d(2) = 1, d(p) = 2 for odd primes p.

I don't think this is the right solution . Consider p = 3 and N = 2. We know that no square number is congruent to 2 modulo 3. So in this case d(3) = 0
 
  • #9
srijithju said:
I don't think this is the right solution . Consider p = 3 and N = 2. We know that no square number is congruent to 2 modulo 3. So in this case d(3) = 0
Which is why it is important to have a precise definition of d(p). According to my second version, d(p) is the maximum number of solutions over all possible choices for N, so it makes sense that you can find particular values of N that have fewer than d(p) solutions.

Perhaps "d(p,N) = exact number of solutions" would be a more useful function.
 
  • #10
I think you mean that N is fixed , but

If the question is :
Find all N < p such that n^2 = N ( mod p) for some n ( By some n , I mean that corresponding to each N there will be one n) , then :

d(p) = greatest integer less than square root of p
 
  • #11
JustSam said:
Which is why it is important to have a precise definition of d(p). According to my second version, d(p) is the maximum number of solutions over all possible choices for N, so it makes sense that you can find particular values of N that have fewer than d(p) solutions.

Perhaps "d(p,N) = exact number of solutions" would be a more useful function.

Considering d(p,N) :

take remainder of N divided by p . Let it be r.
Now if r is a perfect square , then d(p.N) will have infinite solutions of the form r + kp
else there is no solution
 
  • #12
Would d(p) be different if it was instead the number of solutions to:
[tex]F(n) \equiv 0 \pmod p[/tex]? Here F(n) = n - q where q = m^2 is a perfect square where m is a natural number.
 
  • #13
Is m fixed or can it take any integer value? Are there any limits on the value of n or m?
 
  • #14
CRGreathouse said:
Is m fixed or can it take any integer value? Are there any limits on the value of n or m?

There are no limits on the value of n or m. Nice to see you on the forums, by the way Charles!
 
  • #15
flouran said:
Would d(p) be different if it was instead the number of solutions to:
[tex]F(n) \equiv 0 \pmod p[/tex]? Here F(n) = n - q where q = m^2 is a perfect square where m is a natural number.

flouran said:
There are no limits on the value of n or m.

So there are, trivially, infinitely many solutions.

flouran said:
Nice to see you on the forums, by the way Charles!

You too.
 

What is the meaning of "Number of Solutions to d(p)"?

"Number of Solutions to d(p)" refers to the number of positive integer solutions to the equation d(p) = n, where d(p) represents the number of positive divisors of a given positive integer p and n is a positive integer.

Is there a formula for calculating the number of solutions to d(p)?

Yes, there is a formula known as the divisor function that can be used to calculate the number of solutions to d(p). The formula is d(p) = (a+1)(b+1)(c+1)... where p = a^x * b^y * c^z * ..., where a, b, c, etc. are prime numbers and x, y, z, etc. are their respective powers.

Can the number of solutions to d(p) be greater than p?

No, the number of solutions to d(p) can never be greater than p. This is because the maximum number of divisors a positive integer p can have is p itself, and therefore, the maximum number of solutions to d(p) is also p.

What is the relationship between the number of solutions to d(p) and prime numbers?

The number of solutions to d(p) is directly related to prime numbers. For any prime number p, the only positive integer solution to d(p) = n is when n = 2, as a prime number only has two divisors (1 and itself). Therefore, the number of solutions to d(p) for any prime number p is always 1.

Are there any real-world applications for understanding the number of solutions to d(p)?

Yes, the number of solutions to d(p) has applications in number theory and cryptography. It is also used in understanding the distribution of prime numbers and in factoring large numbers, which is important for many encryption algorithms.

Similar threads

  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
705
  • Linear and Abstract Algebra
Replies
9
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
730
  • Precalculus Mathematics Homework Help
Replies
12
Views
1K
  • Precalculus Mathematics Homework Help
Replies
7
Views
764
  • Linear and Abstract Algebra
Replies
8
Views
858
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
1K
Back
Top