Suppose there is a solution a. By Fermat's Little Theorem, 1 ≡ ap−1 = (a2)p−1/2 ≡ (−1)p−1/2. Since 1 ̸≡ −1 (mod p), the number (p−1)/2 must be divisible by 2, thus 4 | (p − 1).
By Wilson's Theorem, the left hand side is congruent to −1, while (p−1)/2 is even by assumption, thus (−1)(p−1)/2 ≡ 1. It follows that x = ((p − 1)/2)! satisfies x2 ≡ −1 (mod p).
If m1, . . . , mk are pairwise coprime and a1, . . . , ak ∈ Z, then the simultaneous congruences x ≡ a1 (mod m1), x ≡ a2 (mod m2), ..., x ≡ ak (mod mk) have a solution x ∈ Z. Moreover, any two solutions are congruent modulo m1 · · · mk.
1. Consider the mapping F: {0, 1, ..., mn - 1} → {0, 1, ..., m - 1} × {0, 1, ..., n - 1} defined by F(k) = (a, b), where a is the remainder of k modulo m and b the remainder of k modulo n
2. By the Chinese Remainder Theorem, the map F is both onto and injective
3. The map Z/mnZ → Z/mZ × Z/nZ defined as above is a bijection