Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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]);
      )}
share|improve this question

1 Answer 1

up vote 2 down vote accepted

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$$

share|improve this answer
    
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
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$. –  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

Your Answer

 
discard

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.