Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!cmcl2!husc6!spdcc!ima!haddock!karl
From: karl@haddock.ima.isc.com (Karl Heuer)
Newsgroups: comp.lang.c
Subject: Re: % operator (was Re: count of bits set in a long)
Message-ID: <18357@haddock.ima.isc.com>
Date: 1 Oct 90 19:11:44 GMT
References: <2859@litchi.bbn.com> <51467@brunix.UUCP> <3417@gmdzi.gmd.de> <985@sunc.osc.edu>
Reply-To: karl@kelp.ima.isc.com (Karl Heuer)
Organization: Interactive Systems, Cambridge, MA 02138-5302
Lines: 17

In article <985@sunc.osc.edu> djh@xipe.osc.edu (David Heisterberg) writes:
>In article <3417@gmdzi.gmd.de> wittig@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@kelp.ima.isc.com or ima!kelp!karl), The Walking Lint