What is modulo arithmetic

I'm trying to understand what mod means in this equation and how to solve it:

d * 13 = 1 mod 1680


This is from how to make a public and private key pair. The answer is 517 apparently and I can get that from wolfram. I assume mod is %, but that doesn't seem to work out. I've also seen that this could me mod( 1, 1680 ) which supposedly equals

mod( m, n ) = m - n ( m / n )


But for that I get 1 and then 1 / 13 is obviously not 517. Just looking for some direction. Thanks.

Ha, I know so little that I can't even find a tag to add.

-
Compare Math use and programming use. – Jyrki Lahtonen Nov 9 '11 at 14:22

5 Answers

I think that you are interpreting the original statement incorrectly. Mod is, indeed, in most programming languages the binary operator %. So, for instance,

5 % 4 = 1


This implies that $$5 \equiv 1 \qquad (\text{mod } 4)$$ (It is not the same, however. See Michael Hardy's comments below.)

However, this will not help you solve the original equation. My interpretation of your question leads me to believe that you tried something like this:

(note to anyone scanning, the following is intentionally incorrect)

13 * d = 1 mod 1680 = 1 % 1680 = 1


and then conclude that d=1/13. Similarly, your mod function mod(m,n) performs the equivalent operation, resulting again in 1/13.

The original equation asks,

$$13 d\equiv 1 \qquad (\operatorname{mod} 1680)$$

or, what number, when multiplied by 13, is equivalent to 1 mod 1680? The first thing to realize is that, if 13 does not divide 1680, there are infinitely many numbers. Chances are, we want the smallest positive number for which this is true.

There are many, many ways to think about this. You could just start plugging in numbers, trying to find one which satisfies this condition. If you were doing this by hand, that would be a terrible way to go, however if you are programming it this won't take very long:

d=1
while (d * 13 % 1680 != 1):
d++


On the other hand, for really large numbers this is pretty inefficient. One approach is to rewrite your equation as an equivalent one (as pedja suggested):

If we are looking for $d$ such that $13d\equiv 1 \quad (\operatorname{mod} 1680)$, then we are looking for a number $d$ such that $13d-1=1680k$ for some integer $k$. Let's rearrange that to make it:

$$13d-1680k=1$$

This is as a linear Diophantine equation, and one can use the Euclidean Algorithm to solve linear Diophantine equations. This approach is algorithmic in nature, so it could certainly be programmed.

Another method would be to use rules about the modulus to find one such $d$. This method works well by hand when the modulus is small, but I doubt it could be (easily) programmed. This relies more on your mathematical sense, to choose suitable operations which will eventually remove the multiplier of 13 on the left side.

-
5 % 4 = 1 does not mean the same thing as $5\equiv 1\mod 4$, because it is true that, for example, $62 \equiv 67\mod 5$, but certainly not true that $62\ \%\ 5=67$. – Michael Hardy Nov 9 '11 at 19:26
Ah, I said the same, and I should have said implies. – process91 Nov 9 '11 at 19:45

Well, we learnt in childhood that 53 divided by 7 leaves a remainder 4. In modular arithmetic. we write that as $53\equiv4 \mod 7$. Given $n\equiv k \mod j$, we interpret it as $j$ divides $(n-k)$ or $j|(n-k)$.Here is a link. I hope that helps.

-

$a\equiv b \pmod c$ means that

$a-b=k\cdot c$ for some integer $k$ so:

$13d \equiv 1 \pmod {1680}$ means that:

$13d-1=k\cdot 1680$ for some integer $k$

Edit:

Maple code :

-

mod 1680 means you consider all integers that differ by a multiple of 1680 to be equivalent. They form a ring, which means (like the integers) you can add, subtract, multiply, and maybe divide. If the modulus is prime, you have a field and can divide as well. In this case you can divide and 13*517=6721=4*1680+1, so 1/13=517. You will be able to do any division where the values are coprime to 1680 (do not share any factors, which are 2,3,5,7)

-

To same that $a= b\,\operatorname{mod} n$ is to say that when you divide $a$ and $b$ by $n$ you end up with the same remainder. So, $517\cdot 13=6721$. Divide $6721$ by $1680$ and you get a remainder of $1$.

-
I'm starting to better understand how to read the equation, but you could point me to a resource that explains how to solve it? – Brian Nov 9 '11 at 14:13
It is called modular arithmetic. If you google it, you will find tons of resources. You can also start at wikipedia: en.wikipedia.org/wiki/Modular_arithmetic – Joe Johnson 126 Nov 9 '11 at 14:40
This site seems helpful too: math.rutgers.edu/~erowland/modulararithmetic.html – Joe Johnson 126 Nov 9 '11 at 14:40
From the article I read I saw modulo and assumed modular was something completely different. Thanks for the info. – Brian Nov 9 '11 at 17:03