2
$\begingroup$

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 Answers 1

2

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$

  • 0
    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 now2012-04-30