Modular Arithmetic

First, if N is prime, then ab≡0 (mod N) is true if and only if a≡0(mod N) or b≡0(mod N). In other words, if a prime number N divides a prime number N divides a product of two numbers, it divides at least one of the two numbers.

Second, if N is prime, then the equation ax≡1(mod N) has a unique solution(mod N) for all 0<a<N. This solution, 0<x<N, is the multiplicative inverse.

Third, if N is prime, then the equation x2≡a(mod N) has either two solutions (mod N) for all 0<a<N, or it has no solutions.