A mathematical formula for p mod q

1. Jun 3, 2013

s0ft

What would be an expression for the modulo operation based only on basic arithmetic i.e. addition, subtraction, multiplication and division?
For example, if I would like to define 7 mod 3 using only the basic arithmetic operations, how would I write a function for it in a programming language?
Of course p and q are integers.

2. Jun 3, 2013

Staff: Mentor

There is no way to write (a mod b) as a general formula with just addition, subtraction, multiplication and division, without any tools like loops (programming) or mathematical logic.

To write a function, consider 7 mod 3, 4 mod 3 and 1 mod 3. Which one is easy to evaluate? Can you transform the others into this?

3. Jun 3, 2013

s0ft

Thanks. I was suspecting that was the case.

4. Jun 3, 2013

s0ft

I'd heard some reputed mathematician had made an attempt to "rigorize" mathematics which I think is to be able to do maths without having to use one's conscience or judgement. So the modulo doesn't fall in that category I guess?

5. Jun 3, 2013

Office_Shredder

Staff Emeritus
No, p mod q is something that can be computed. I think you're confused by what you heard (or the person saying it was confused as to what they were saying)- math has been rigorous for quite a long time now. p mod q is rigorously defined and can be rigorously calculated.

If you wanted to write a program to calculate this you could do so recursively like this:
mod(p,q)
// returns a number between 0 and q-1

if p < 0
return mod(p+q,q)
elseif p>q-1
return mod(p-q,q)
else
return p
end

It's a good exercise to prove that this program is correct (try a couple examples if you're not sure what's going on - what does it do when I plug in mod(10,3)?). You can also do the calculation in one shot if you're willing to work with non-integers

mod(p,q)
remainder = p/q-floor(p/q)
return round(remainder*q)
end

This version really just obfuscates the fact that division is defined by repeatedly subtracting (actually it's probably not done exactly like this in modern processors but the point that division is hard to do still stands)

6. Jun 3, 2013

s0ft

Thanks for your help but I didn't mean achieving it with a computer program using conditional statements. Of course life would be easy if that was allowed. Conditional judgements are acts of choosing and destroy rigor, don't they?
See, like the floor() function you used, you don't get something like that in pure rigorous mathematics, do you?

7. Jun 3, 2013

8. Jun 3, 2013

rcgldr

The floor function effectively restricts the result of division to be an integer. To get the proper sign for negative numbers you'd have to define integer division to round down towards -∞, so that (+7) / (+3) or (-7) / (-3) = 2 and (+7) / (-3) or (-7) / (+3) = -3, so that the result of p mod q is zero or has the same sign as q.

Using integer division as defined above, then p mod q = p - (p/q)*q.

7 mod 3 = 7 - (7/3)*3 = 7 - 6 = 1
7 mod -3 = 7 - (7/-3)*-3 = 7 - 9 = -2
-7 mod 3 = -7 - (-7/3)*3 = -7 + 9 = 2
-7 mod -3 = -7 - (-7/-3)*-3 = -7 + 6 = -1

9. Jun 3, 2013

Office_Shredder

Staff Emeritus
What do you think the definition of rigor is?

You definitely do.

Rigor is just making sure that every statement made is a true. You can define functions however you want - your choice of definition doesn't change whether you are being rigorous or not

10. Jun 4, 2013

s0ft

Maybe I used the wrong term 'rigor'.
What I wanted to say was : using nothing more than a general universal single rule or function, here, for the modulo operation, exactly as mfb got me.

11. Jun 4, 2013

rcgldr

All that is needed is a redefinition of division so that division only produces integers (rounded downwards towards -∞). Note that integer division on most processors rounds towards 0 instead of -∞, so a post division correction step would be needed.

12. Jun 4, 2013

Staff: Mentor

(a mod b) is the unique natural number x with $0 \leq x < b$ such that there exists a $k \in \mathbb{Z}$ with (x-a)=kb.

13. Jun 4, 2013

s0ft

So we can only define it as another function, requiring us to think what 'k' is going to be. There is no escaping from 'thinking' what it is going to be. Alright.
Thank you.

14. Jun 5, 2013

rcgldr

The normal definition for modulo is the remainder after performing integer division, so the only function that needs to be defined is the integer division used for the modulo function.

Wiki article:

http://en.wikipedia.org/wiki/Modulo_operation