Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the comparision in positive integers $$\small {rq-1 \over 2^B} \le q-1 $$ where $\small B $ is the given parameter and r and q are residues modulo $\small 2^B$ (which also implies, that the lhs is assumed to be integer and which then puts restrictions on the relation of r and q) .
In my calculations I use $\small r=3^N (\mod 2^B) $and $\small q=3^{-N} (\mod 2^B) $ with $\small N \gt 0$ as free parameter to guarantee an integer lhs. (This implicitely restricts empirical results to less possible residue classes in r,q and thus possible solutions, but leave this for the moment).

My observation is, that the lhs is always at most equal to the rhs, which makes me curious. But I was not yet able to extract the key argument, why this is so. It is easy to see, that if $\small q=2^B-1 $ then also $\small r=q $ (from which then the equality in the equation follows) and also if $\small q=1 $ then $\small r=1$ and again the equality holds.

So my question is, how can I see that the given inequality holds always?

share|cite|improve this question
You talk about $p$, but I don't see it anywhere. – Gerry Myerson Apr 3 '12 at 10:14
@Gerry: It's meant r. I'll correct it – Gottfried Helms Apr 3 '12 at 10:17
$p$ is still there. – Gerry Myerson Apr 3 '12 at 12:39
Just found and removed that last easter-egg. – Gottfried Helms Apr 3 '12 at 13:32
up vote 0 down vote accepted

Hmm, I don't know why I didn't see this before ....

Assume $\small {rq-1\over 2^B}=q$ then $\small rq=q2^B+1$ and $\small r=2^B+\frac1q $ . Here the case q=1 gives the only integer solution $\small r=2^B+1 $, but which as well as the noninteger solutions due to $\small q \gt 1$ are excluded by the definitions.

[update] It is even nicer; empirically I find, that $$\small {rq-1\over 2^B}+1 \le \min({q,r})$$ and equality occurs if and only if q or r is a divisor of $\small 2^B-1 $ . (Recall $\small r\equiv 1/q \pmod {2^B} $) This is really a surprise!

share|cite|improve this answer
To remove the uestion from the automatic reminder I've to "accept" one answer formally. I'll do that although it's my own answer... – Gottfried Helms May 5 '12 at 18:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.