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]