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