% operator (was Re: count of bits set in a long)

[Paul Nulsen]

wittig at gmdzi.gmd.de (Georg Wittig) writes:
>tac at cs.brown.edu (Theodore A. Camus) writes:
>>However, 077 in octal is 63 in decimal, and I believe the following
>>					     ^^^^^^^^^
>>relationship is true : x % 63 = [(x % 64) + (x / 64)] % 63
>
>	Does there exist a proof for that equation? Can it be found in
>	literature? Is the following true?
>	
>		x % n = (x%(n+1) + floor(x/(n+1))) % n	      (n != 0;n != -1)
>	
>	Do there exist similar "surprising" equations?

The answers are: yes; yes; yes and I suppose yes (all qualified a little).

The proof follows from modular arithmetic. It is not difficult to show that
the normal arithmetic operations (addition, subtraction and multiplication)
are "preserved" under modular arithmetic, so that, for example, for integers
a, b and non-zero n:
    ((a modulo n) * (b modulo n) modulo n) = (a * b) modulo n

Now for any integer a
    a = (n + 1) * (a / (n + 1)) + a % (n + 1)
so, provided that,
    (n + 1) modulo n = 1,
we can just apply the modulo to both sides to get
    a modulo n = ((n + 1) * (a / (n + 1)) + a % (n + 1)) modulo n
      = (((n + 1) * (a / (n + 1))) modulo n + (a % (n + 1)) modulo n) modulo n
      = ((1 * (a / (n + 1))) modulo n + (a % (n + 1)) modulo n) modulo n
      = (a / (n + 1) + a % (n + 1)) modulo n
(note that the division is not done in modular arithmetic).
Usually,
    a modulo n = a % n,
so that this is the result.

I haven't tried to be too rigorous, but you can see where this result can
fail in practice.  Basically, you are safe if all the numbers are positive,
and all bets are off if n is negative (usually (n + 1) modulo n != 1 if n is
negative). Other cases will be machine dependent.

As to related surprising results, number theory is full of them. A direct
application of this result (n = 9) is the well known rule that the sum of
the digits of a number divisible by 9 is divisible nine.

Paul Nulsen
pejn at wolfen.cc.uow.edu.au