Path: utzoo!attcan!uunet!tut.cis.ohio-state.edu!oscsunb!xipe.osc.edu!djh
From: djh@xipe.osc.edu (David Heisterberg)
Newsgroups: comp.lang.c
Subject: Re: % operator (was Re: count of bits set in a long)
Message-ID: <985@sunc.osc.edu>
Date: 1 Oct 90 16:16:52 GMT
References: <2859@litchi.bbn.com> <51467@brunix.UUCP> <3417@gmdzi.gmd.de>
Sender: news@osc.edu
Organization: Ohio SuperComputer Center, Columbus, OH, USA
Lines: 27

In article <3417@gmdzi.gmd.de> wittig@gmdzi.gmd.de (Georg Wittig) writes:
>tac@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@osc.edu		And you all know
The Ohio Supercomputer Center	djh@ohstpy.bitnet	security Is mortals'
Columbus, Ohio  43212		ohstpy::djh		chiefest enemy.