Find all elements of \(Z_{19}^*\) of multiplicative order 18.

== Attempt ==

Since 19 is a prime number, \(\varphi(19) = 19 - 1 = 18\). Using Euler's theorem, we know that \( \alpha^{\varphi(19)} = \alpha^{18} = 1 \) for \( \alpha \in Z_{19}^* \).

(For a given positive integer \(n\), we say that \(a \in \mathbb{Z}\) with \(gcd(a, n) = 1\) is a primitive root modulo \(n\) if the multiplicative order of \(a\) modulo \(n\) is equal to \(\varphi(n)\). Since the multiplicative order 18 is equal to \(\varphi(19)\), this exercise is equivalent to finding the primitive roots modulo 19.)

Note that if \(\alpha^k = 1\) with \(k < 18\), \(k\) must divide 18. Since the multiplicative order of 1 is always limited to 1, we only need to check \(k\) that divides 18 except 1:

== Python ==

n = 19
ks = [2,3,6,9]    # k that divides 18 except 1
output = []
for i in xrange(2,n):
    primitive_root = True
    for k in ks:
        e = i**k
        if e - e/n*n == 1:
            primitive_root = False
            break;  # multiplicative order less than 18
    if primitive_root:
        output.append(i)
print 'Elements with multiplicative order 18:', output

== Output ==

Elements with multiplicative order 18: [2, 3, 10, 13, 14, 15]