is there a formula for modulo

Question

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)

Answer 1

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.)

Answer 2

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

Answer 3

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.

Answer 4

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$