12
$\begingroup$

I have been trying to find a formula for modulo for a long time now. I was wondering, is this even possible? I know there are lot's of solutions for this problem in computer science but is there a solution for this problem in arithmetics? I mean is there a function that uses only arithmetics actions that can solve this problem? (I mean actions like $\log$ or $\sqrt{}$ or something like that)

$\endgroup$
11
  • 2
    $\begingroup$ First off, mod is considered as a binary operation in computer science and programming and $\bmod~m$ (for fixed $m$) is considered a binary relation in mathematics. You are talking about the former, mod. There are elementary ways to express Mod[a,b] in terms of the floor function or the sine function. Are these acceptable to you? $\endgroup$
    – anon
    Commented Feb 12, 2014 at 23:06
  • 1
    $\begingroup$ Depends what you mean by formula. If you allow the use of the "floor function" $\lfloor x\rfloor$ (the greatest integer $\le x$), there is a simple formula. It is a good way of calculating $a\bmod m$ on a simple calculator. $\endgroup$ Commented Feb 12, 2014 at 23:09
  • $\begingroup$ See my comment on @Dan's answer. $\endgroup$ Commented Feb 13, 2014 at 17:32
  • $\begingroup$ @anon, what is the formula that uses the sine? $\endgroup$ Commented Feb 13, 2014 at 17:34
  • 1
    $\begingroup$ @Brian You mean the sine thing? I think I was misremembering a different fact. (And, frankly, if there were a formula for mod in terms of sine, which there probably is with a sufficient amount of cleverness, it's sure to be very boring and artificial.) $\endgroup$
    – anon
    Commented Feb 14, 2014 at 4:32

4 Answers 4

12
$\begingroup$

If your definition of “arithmetics actions” includes the floor function, then this is straightforward:

$a \text{ mod } b = a - b ⌊\frac{a}{b}⌋ $

(Assuming you want the semantics of Python's % operator, as opposed to C's.)

$\endgroup$
4
  • $\begingroup$ Indeed this formula is more straightforward than the form than I used. You can get the "floor" function by using the Int key or simply retyping the value before the decimal point. $\endgroup$ Commented Feb 13, 2014 at 17:31
  • $\begingroup$ Although if you use a more basic calculator, you may wish to use my form of the formula. $\endgroup$ Commented Feb 13, 2014 at 17:57
  • $\begingroup$ Consider the consequences when only one number is negative: $-4 \text{ mod } 3=-4-3\left\lfloor\tfrac{-4}{3}\right\rfloor=-4+6=2.$ $\endgroup$ Commented Feb 14, 2014 at 18:06
  • $\begingroup$ Perhaps it would be better to say, $-4\text{ mod }3=-4-3\left\lceil\tfrac{-4}{3}\right\rceil=-4+3=-1$, like C does? I know $-4\equiv-1\equiv2\mod 3$. $\endgroup$ Commented Feb 14, 2014 at 18:27
7
$\begingroup$

Only formula I know of for mod is:$$n\hspace{1mm}mod\hspace{1mm}2 = \frac{1+(-1)^{n-1}}{2} $$

$\endgroup$
2
  • $\begingroup$ Of course (-1)^x is shorthand for e^ipx which essentially just uses sine to "modulo" by looping around the interval. $\endgroup$ Commented Sep 2, 2019 at 4:29
  • $\begingroup$ This only works for integers $\endgroup$
    – 0x777C
    Commented Aug 15, 2020 at 11:27
1
$\begingroup$

To find $a\mod 9$, all you have to do is add the digits together, take the result and add up its digits, and so on, until you only have $1$ digit left. I'm pretty sure it's possible to extend it to $\mod n$.

In fact, here's the trick: you multiply each digit by the difference between 10 and the number, raised to that digit's power of 10. For example: $$\begin{align}145\text{ mod }8&=(5+4\cdot2+1\cdot4)\text{ mod }8\\&=(5+8+4)\text{ mod }8\\&=17\text{ mod }8\\&=(7+1\cdot2)\text{ mod }8\\&=9\text{ mod }8\\&=9-8=1\end{align}$$

Here's some code in JavaScript I dug up that I wrote a couple years ago.

function mod(n,d,b)                      // n is number, d is divisor, b is base
{
 if (n==0)
  return 0;
 else
 {
  var m=(n%b)+((b-d)*mod(Math.int(n/b),d,b)); // add n mod b to next lower call
  if (m<=d)                                   // times (base minus divisor)
   return m;
  else
   return mod(m,d,b);                         // call the function again if sum is
 }                                            // too large
}
function mod9(n)
{
 if (n==0)
  return 0;
 else
 {
  var m=(n&7)-mod9(n>>3);
  if (m<=8&&m>=0)
   return m;
  else
   return mod9(m);
 }
}

There's always repeated subtraction until the number is less than $n$. You can also use: $$a \mod n = ((a/n)-\lfloor(a/n)\rfloor)*n$$ A mathematically correct notation would be: $$a\equiv(a-n\lfloor\tfrac{a}{n}\rfloor)\equiv(a-n\lceil\tfrac{a}{n}\rceil)\mod n$$

Using only the ceiling function will give a negative result; with the floor function the result will be positive.

$\endgroup$
2
  • 1
    $\begingroup$ The same process works for any $n$ ... as long as you write numbers in base $n+1$. $\endgroup$
    – anon
    Commented Feb 13, 2014 at 6:26
  • $\begingroup$ Of course, there's always $a-n-n-n\cdots - n$ until $<n$. $\endgroup$ Commented Feb 13, 2014 at 6:40
1
$\begingroup$

For positive integers $x$ and $n$, a solution for $x$ modulo $n$ is $$\bmod \left( {x,n} \right) = \frac{1}{n}\mathop \sum \limits_{i = 1}^{n - 1} \mathop \sum \limits_{k = 0}^{n - 1} i\exp \left( {j\left( {x - i} \right)\frac{{2\pi k}}{n}} \right)$$ where ${j^2} = - 1$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .