Vtyjkyuk

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.

$aequiv b pmod c$ means that

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

$13d equiv 1 pmod 1680$ means that:

$13d-1=kcdot 1680$ for some integer $k$

Edit:

Maple code :

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

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

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 (textmod 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 dequiv 1 qquad (operatornamemod 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 $13dequiv 1 quad (operatornamemod 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.

$pmod 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 $13^-1=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$).