Producing MOD(x,y) with Arithmetic Operations

Date: 03/04/98 at 16:49:33
From: Steve Lundberg
Subject: can the MOD(x,y) function be re-created using basic math?

Is there any way to produce the "MOD(dividend,divisor)" spreadsheet 
function using basic math (i.e., +,-,*,/)?

Unlike division ...
   200/7 = 28.571428571

... MOD(x,y) gives the remainder after division: 
   MOD(200,7) = 4

Is there anyway to produce the value 4, given the other numbers, using 
only basic math?

I've gotten this far ...
   (200/7 - INT(200/7)) * 7
... but I'm still relying on the INT(n) spreadsheet function, which is 
the TRUNC(n) function in some spreadsheets.

Background:
It's in a course on computer spreadsheets that this question came up. 
I was stumped!

Thanks for your help.

Date: 03/05/98 at 18:16:58
From: Doctor Daniel
Subject: Re: can the MOD(x,y) function be re-created using basic math?

Hi there,

You asked about modulo arithmetic, specifically if there is any way to 
produce the "MOD(dividend,divisor)" spreadsheet function using basic 
arithmetic operations (i.e., +,-,*,/).

The short answer: No.

The longer answer: No, because it's actually impossible to do even 
MOD(n,2) with just these operations. That is, suppose that I want a 
function that returns 0 on all even numbers and 1 on all odd numbers.  
Suppose I give you an even easier problem: give me a function that 
returns 0 on all even numbers and I don't care what on all odd numbers 
(so long as it's not always zero). Here's a proof that you can't do it 
with just +-*/.

First, hopefully you'll agree that any such function is equivalent to 
a function of the form f(x) = A(x)/B(x), where A(x) and B(x) are both 
polynomials in x, that is, something like a + bx + cx^2 + ... + zx^k.  

So, for example, something like 

         2x^5 + 4x^4 + 3x^2 + 1
f(x) =   ----------------------
           x^6 - x^4 + 2x + 41

That's because if it's anything else, say the sum of two fractions, or 
whatever, you can combine terms using least common denominator, or by 
multiplying out products.

Next, it's clear that the denominator of the function doesn't matter.  
Why? Well, if it's ever zero on an even number, then we have major 
problems of the divide-by-zero type, and if it's not, then the 
numerator is always zero on evens and we-don't-care-what on odd 
numbers as well. So just let f(x) equal a polynomial (in other words, 
we can get it with just +-*/).

But we know that a polynomial with highest exponent k which is not 
always zero evaluates to zero on at most k values. 

That means that, for example, 

        x^2 - 4

is zero on at most 2 values, while

        x^66 - 54x^32 + 41x^5 - 1 

is zero on at most 66 (possibly fewer, but at most 66). This is called 
the Fundamental Theorem of Algebra, and is not trivial to prove, but 
it's true.

But our polynomial is supposed to be not always zero, but zero on an 
infinite number of values -- all even numbers!  Therefore, there 
exists no finite-degree polynomial which can be not always zero but 
zero on all evens.

Hence, we can't compute MOD(n,2) with a finite polynomial, since it's 
even more complicated!

Incidentally, if that seemed silly, computer scientists who are 
concerned with proving what certain models of computers can and can't 
compute were very excited with a much more complicated version of this 
sort of argument about 15 years ago, when someone used it to prove 
something which looked for a while like an approach to the P vs NP 
problem that is very critical in our area. So it's not as silly as you 
might think.

Thanks for your question ... enjoy!

Doctor Daniel, The Math Forum
 Check out our web site! http://mathforum.org/dr.math/