1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A mathematical formula for p mod q

  1. Jun 3, 2013 #1
    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. jcsd
  3. Jun 3, 2013 #2

    mfb

    User Avatar
    2016 Award

    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?
     
  4. Jun 3, 2013 #3
    Thanks. I was suspecting that was the case.
     
  5. Jun 3, 2013 #4
    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?
     
  6. Jun 3, 2013 #5

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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)
     
  7. Jun 3, 2013 #6
    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?
     
  8. Jun 3, 2013 #7

    Borek

    User Avatar

    Staff: Mentor

  9. Jun 3, 2013 #8

    rcgldr

    User Avatar
    Homework Helper

    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
     
  10. Jun 3, 2013 #9

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  11. Jun 4, 2013 #10
    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.
     
  12. Jun 4, 2013 #11

    rcgldr

    User Avatar
    Homework Helper

    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.
     
  13. Jun 4, 2013 #12

    mfb

    User Avatar
    2016 Award

    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.
     
  14. Jun 4, 2013 #13
    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.
     
  15. Jun 5, 2013 #14

    rcgldr

    User Avatar
    Homework Helper

    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: A mathematical formula for p mod q
  1. 1/p + 1/q + 1/r (Replies: 12)

  2. Mathematics Q (Replies: 8)

  3. P = np formula (Replies: 7)

Loading...