# Is always $\small {rq-1 \over 2^B} \le q-1$ with natural r,q,B and $\small r,q \in \{1, \ldots, (2^B-1)\} , odd$?

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?

-
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

## 1 Answer

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!

-
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