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

[David Heisterberg]

In article <3417 at gmdzi.gmd.de> 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?

It should hold for any n,m relatively prime.

x % n = (x % m + x / m) % n  <=>  x = k * n + (x % m + x / m)  <=>

x % m = k * n % m + x % m % m + x / m % m  [x % m % m = x % m]  <=>

k * n % m  + x / m % m = 0  <=>  k * n + l * m = -(x / m)

k' * n + l' * m = 1 has solutions in integers if (n,m) = 1, let

k = -(x / m) * k', l = -(x / m) * l'.

Corrections and improvements welcome.
--
David J. Heisterberg		djh at osc.edu		And you all know
The Ohio Supercomputer Center	djh at ohstpy.bitnet	security Is mortals'
Columbus, Ohio  43212		ohstpy::djh		chiefest enemy.