Sign up ×

Suppose we have $D$ prime and $d$ square free. Is there a way to express the smallest integer $n$ that makes $d \vert (Dn-2)$? If such an $n$ exists for a given $D$, $d$ it must exist less than $d$, but is there some function of $D$ and $d$ that gives it explicitly?

share|cite|improve this question
What sort of function are you looking for? – Igor Rivin Aug 6 '11 at 19:00
So you're looking at the congruence class $2D^{-1}\bmod{d}$ and want to find its representative in $\\{0,1,2,\ldots,d-1\\}$. I doubt there's a simple formula, since as $D$ varies, the quantity $D^{-1}\bmod}{d}$ will jump all over the place. I also doubt it's relevant that $D$ is prime, although $d$ being square free might help. I'm pretty sure people have at least studied the sequence $D^{-1}\bmod{p}$ as a function of $D$, where $p$ is prime. But those would be averaging results, or estimating the smallest $D$ such that $D^{-1}\bmod{p}$ is also "small". (I'm going to add an "nt" tag.) – Joe Silverman Aug 6 '11 at 19:24
You need to rule out that ((D>2)and (D divides d)). After that, use standard algorithms to compute the inverse of d mod D (so find smallest k > -D such that dk = Dm +1 for some negative integer m ) and then multiply m found above by -2. If necessary, subtract certain multiples of d from the result. Gerhard "Ask Me About System Design" Paseman, 2011.08.06 – Gerhard Paseman Aug 6 '11 at 19:28
Yes, I see what you mean, things get all messed up if D=2, or D divides d. Thank you both, I will continue to look into it. – Alex Botros Aug 6 '11 at 19:33
amazing that so many people consider this a research-level question... – Igor Rivin Aug 6 '11 at 20:19

1 Answer 1

Hi guys, sorry I caused a fuss. The fact of the matter is (from what my limited understanding tells me) is that is if you solved this question, you could then tackle the weirdly huge error term in Brun's sieve. You're all probably familiar with this sieve, but it frustrates me that we must assume all error terms (typically written) $R_d$ (of fluctuating sign) positive in order to bound its sum as an alternating series. I understand that we expect there to be about $$\frac{N/2}{d}2^{\omega(d)}$$ integers n between $N/2$ and $N$ that will allow $d\vert n(Dn-2)$, and I understand that this may sometimes be an overestimate (resulting in a negative $R_d$) or an underestimate (resulting in a positive $R_d$). Furthermore, because Brun's error is written as an alternating series over these $R_d$, the rectification of signs becomes tragic. I was thinking that if my above question was answerable, we would be able to rectify when Brun's main term is an underestimate, and when it is an underestimate, and thus we would not have to simply take the error as the strictly positive sum over $\vert R_d \vert$ which blows up way quicker than it has to. I have been using fairly standard sieve theory notation without explaining it, and for that I apologize. Furthermore I just graduated high school as Gerhard Paseman correctly pointed out, so I apologize further for the elementary nature of my comment. Thank you sirs for your patience, I will keep looking.

share|cite|improve this answer
The above isn't actually an answer, it was simply to long to write as an additional comment. – Alex Botros Aug 8 '11 at 3:50
Now that you have mentioned the motivation, you might consider related problems which might be solvable and applicable, such as what else you could say that would help with the error term. Perhaps, as Joe Silverman suggests, looking at how n is distributed would be of use. Gerhard "Ask Me About System Design" Paseman, 2011.08.07 – Gerhard Paseman Aug 8 '11 at 4:48

Your Answer


