mersenneforum.org > Math Number of Solutions to d(p)
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2009-08-29, 05:48 #1 flouran     Dec 2008 15018 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     "Jacob" Sep 2006 Brussels, Belgium 1,901 Posts I suppose that another condition is N
 2009-08-29, 14:12 #3 flouran     Dec 2008 34116 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 5,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

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

5,987 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

83310 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

433 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

15018 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 16:20.

Sat Jan 28 16:20:09 UTC 2023 up 163 days, 13:48, 0 users, load averages: 1.22, 1.11, 1.09

Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔