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

[Karl Heuer]

In article <985 at sunc.osc.edu> djh at xipe.osc.edu (David Heisterberg) writes:
>In article <3417 at gmdzi.gmd.de> wittig at gmdzi.gmd.de (Georg Wittig) writes:
>>Is the following true?
>>	x % n = (x%(n+1) + floor(x/(n+1))) % n	      (n != 0;n != -1)
>
>It should hold for any n,m relatively prime.  [Using m for n+1]

Counterexample: (n=10, m=13, x=15): x % 10 = 5 != 3 = (x%13 + x/13) % 10
The correct generalization is
	x % n = (x%m + (x/m)*(m%n)) % n
which reduces to the original identity when m%n = 1.

Proof of generalization: this is just the identity x = (x/m * m + x%m) reduced
modulo n, with m replaced by the equivalent m%n.  (There's no need for m and n
to be relatively prime, either.)

Karl W. Z. Heuer (karl at kelp.ima.isc.com or ima!kelp!karl), The Walking Lint