Generators and Quadratic Residue

Theorem 2.1.17 (properties of generators of Z*n)

1. Z*n has a generator if and only if n =2, 4,p^k or 2p^k, where p is an odd prime and

k ≥ 1. In particular, if p is a prime, then Z*n has a generator.

2. If g is a generator of Z*n, then Z* n = {a^i (mod n)| 0 ≤ i ≤ φ(n) - 1}.

3. Suppose that g is a generator of Z*n. Then b = g^i (mod n) is also a generator of Z*n

if and only if gcd(i, φ(n)) = 1. It follows that if Z*n is cyclic, then the number of

generators is φ(φ (n)).

4. g Є Z*n is a generator of Z*n if and only if g^ [φ (n)/p]≠ 1(mod n) for each prime divisor p of φ(n).

Definition 2.1.15 Let a Є Z*n. a is said to be quadratic residue modulo n , or square

modulo n, if there exists an x Є Z*n such that x^2 ≡ a (mod n). If no such x exists, then a

is called a quadratic non-residue modulo n. The set of all quadratic residues modulo n is

denoted by Qn and the set of all quadratic non-residues is denoted by Ộn.

Example 2.1.8 g = 6 is a generator of Z*13. The powers of g are listed in the following

table. Q13 = {1, 3, 4, 9, 12} and Ộ13 = {2, 5, 6, 7, 8, 11}.