These are all the numbers between $0$ and $19$ which are relatively prime to $20$. It is almost obvious that the product of two numbers relatively prime to $m$ is itself relatively prime to $m$.
For a formal proof, let's concentrate on $m=20$. Suppose that $a$ and $b$ are relatively prime to $20$. We show that $ab$ must be relatively prime to $20$. For if it is not, then $ab$ is divisible by $2$ or by $5$ (or both). But if $ab$ is divisible by the prime $2$, then $a$ or $b$ must be. the argument for the prime $5$ is the same.
This is a good question. As you may have gathered from the comments, in the absence of any further information about the group, the answer is no, all you can do is to successively try higher powers.
But in most situations that arise in practice you do have extra information of one kind or another. For example, if your element is a matrix over a finite field, or even over the rational number or a number field, then the set of all possible orders of elements is known (at least in theory).
In such situations, you typically have a multiplicative upper bound for the order. In other words, you know a (possibly very large) integer $N$ such that the order of the element $g$ divides $N$. Then you can proceed as follows
For all primes $p$ dividing $N$, compute $g^{N/p}$. If $g^{N/p} = 1$ for some $p$, then replace $N$ by $N/p$ and start again - note that there will be a maximum of $\log n$ reductions of this kind. Otherwise, if $g^{N/p} \ne 1$ for all $p$, then the order of $g$ must be $N$.
Note also that computing $g^N$ can be accomplished on $O(\log n)$ group operations, by writing $N$ in binary $N = 2^{n_1} + \cdots + 2^{n_k}$, and then you can compute $g^N$ as $g^{2^{n_1}} \cdots g^{2^{n_k}}$.
Best Answer
Lagrange's theorem says you only have to check $2^2,2^3,2^4,2^6,2^9,2^{12}$ and $2^{18}$. The checking itself is a lot easier if you exploit relations like $2^6\cdot 2^3=2^9$ and $(2^6)^2=2^{12}$.