# Is always $\small {rq-1 \over 2^B} +1 \le \min(q,r)$ with equality iff $\small q$ or $\small r$ is a divisor…

I had a simpler question before such that I could even answer it myself. For the next step I seem again to be too dense today. (Remark several days later: it's not only being dense... I still don't find the first step for the solution)

Recall: I discuss q,r as residues to a modulus of $\small 2^B$ for natural parameters B. I assume an odd $\small r (\gt 0)$ as given and q as $\small q= \frac1r \pmod {2^B}$. I understand now well, that $$\small {qr-1\over 2^B} +1 \le \min(q,r)$$

But I observe more: I find in some experiments using Pari/GP, that the equality occurs exactly iff either r or q is a divisor (or both are divisors) of $\small 2^B-1$.

How can I show this with a proof?

Examples.

We use $\small B=8, 2^B=256$

1. First we try $\small r=15$. Then $\small 1/15 \equiv 239 \pmod{256} \to q=239$
Also r is a divisor of $\small 256-1$ . Then

$\qquad \small {15\cdot239-1\over256}+1 =15 = \min(15,239)$

2. Next we try $\small r=13$. Then $\small 1/13 \equiv 197 \pmod{256} \to q=197$
Now r is not a divisor of $\small 256-1$ Then

$\qquad \small {13\cdot197-1\over256}+1 =10 \lt \min(13,197)$

Here is some Pari/GP-code to see what I mean

B=9  \\ chose some exponent B
Test(B) \\ check display

{Test(B) = local(M,M1,r,q,t,rhs,isdiv);
M = 2^B ; M1 = 2^B-1 ;
for(k=1,M/2,
r=2*k-1;       \\ test all odd residues up to 2^B-1
q=1 / r  % M ;  \\ q is the multiplicative inverse (mod 2^B)
t = (r*q-1)/M +1 ;
rhs = min(r,q);
isdiv = ((M1 % r ) * (M1 % q)) == 0 ; \\ =1 if either q or r is divisor of 2^B-1
print([r,q,t, rhs, t == rhs, isdiv]);
)}

-

## 1 Answer

If $${qr-1\over2^B}+1=q$$ then a bit of algebra gets you to $2^B-1=(2^B-r)q$, so $q$ is a divisor of $2^B-1$.

If $q$ is a divisor of $2^B-1$, say, $2^B-1=qs$, then $(2^B-s)q=(q-1)2^B+1\equiv1\pmod{2^B}$, so $r=2^B-s$; then $${qr-1\over2^B}+1={(2^B-s)q-1\over2^B}+1={2^Bq-(qs+1)\over2^B}+1={2^Bq-2^B\over2^B}+1=q$$

-
yes, meanwhile I've arrived at this formulation, when q (or p) is a divisor, too. But I'm still without an idea, how to even formulate the case, if (q AND r) are not divisors, that the result is then smaller than q. Can I read this in your line of arguments in some way? –  Gottfried Helms Apr 30 '12 at 4:51
Sure. You say you know that $1+(1/2^B)(qr-1)\le\min(q,r)$. If neither $q$ nor $r$ is a divisor, then by my first sentence $1+(1/2^B)(qr-1)$ is neither $q$ nor $r$. It's immediate that it's less than $q$. –  Gerry Myerson Apr 30 '12 at 4:57
I don't know why, I feel insecure with it, but it might only be a mental problem of lack of exerise, because I'm beginning to formally understand the argument: it must be smaller or equal. We asumme it is equal and find, that if we assume it is a divisor, then this holds. If we assume it to be not equal, it must be smaller by the first sentence, so it cannot be a divisor... I'll have to chew this more times. (cont) –  Gottfried Helms Apr 30 '12 at 5:13
(...) I need to have it perfectly in mind, because I want to say something for the approximation of $3^N$to $2^{N+B}$ when $2^B-1$ is a mersenne-prime and has no proper divisors. And I've erred many times with hypotheses in that problem... –  Gottfried Helms Apr 30 '12 at 5:14
I think I'm getting now familiar with it. Another view, which was helpful for me is to formulate the non-divisorship by another parameter, say $a$ in ${2^Ba-1\over q}$ with $0 \lt a \lt q$ and where $a=1$ if $q$ is a divisor of $2^B-1$, and $a>1$ if not. This helped to improve the intuition. Thanks for the answer, I think I got it now –  Gottfried Helms Apr 30 '12 at 7:19