Associated Topics || Dr. Math Home || Search Dr. Math

### 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!

```

```
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 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/
```
Associated Topics:
College Algorithms
College Modern Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search