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
    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?2012-04-30
  • 1
    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$.2012-04-30
  • 0
    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)2012-04-30
  • 0
    (...) 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...2012-04-30
  • 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