# is there a formula for modulo

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)

• 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?
– anon
Commented Feb 12, 2014 at 23:06
• 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. Commented Feb 12, 2014 at 23:09
• See my comment on @Dan's answer. Commented Feb 13, 2014 at 17:32
• @anon, what is the formula that uses the sine? Commented Feb 13, 2014 at 17:34
• @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.)
– anon
Commented Feb 14, 2014 at 4:32

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

• 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. Commented Feb 13, 2014 at 17:31
• Although if you use a more basic calculator, you may wish to use my form of the formula. Commented Feb 13, 2014 at 17:57
• 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.$ Commented Feb 14, 2014 at 18:06
• 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$. Commented Feb 14, 2014 at 18:27

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

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

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.

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

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$$