I have a quick question regarding modular multiplication.

I know that a ≅ b (mod n) is true if n | (a-b). However, in the example given below proving the existence of a multiplicative inverse p, they placed the b ≅ (a mod(n)).

Lemma 4.6.1.

If p is prime and k is not a multiple of p, then k has a multiplicative inverse modulo p.

Proof: Since p is prime, it has only two divisors: 1 and p. And since k is not a multiple of p, we must have gcd(p,k)= 1.

Therefore, there is a linear combination of p and k equal to sp + tk = 1.

Rearranging terms gives: sp = 1 - tk. This implies that pj | (1 - tk)
by the definition of divisibility, and therefore tk ≅ 1 (mod p) by the definition of congruence. Thus, t is a multiplicative inverse of k.

So, for example:

7*3 ≅ 1 mod(5) is true, and therefore, 1 ≅ 7 * 3 mod(5).

So in other words, this is like saying 1 ≅ tk (mod p) is the same thing as tk ≅ 1 (mod p). It's also possible to conclude that 1 ≅ tk (mod p) && tk ≅ 1 (mod p) is only true if and only if t is a multiplicative inverse of k.

Source: (https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_chap04.pdf)

  • 1
    $\begingroup$ What is the question? $\endgroup$ – user52969 Jun 15 '17 at 1:02

if $n| (b-a)$, then $\exists k \in \mathbb{Z}$, $(b-a)=nk$.

We also have $(a-b)=n(-k)$ and since $(-k) \in \mathbb{Z}$,

$n|(a-b)$ as well.

Does this answer your question?

$a \equiv b \mod n$ if and only if $b \equiv a \mod n$.

  • $\begingroup$ This answers my question thank you. $\endgroup$ – fncischen Jun 15 '17 at 3:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.