Let $p$ be a prime and let $q$ be a prime that divides $p − 1.$
(a) Let $a \in F_p$ and let $b = a^{\frac{p−1}{q}}$. Prove that either $b = 1$ or else $b$ has order $q.$ (Recall that the order of $b$ is the smallest $k \ge 1$ such that $b^k = 1$ in $F_{p}.$
(b) Suppose that we want to find an element of $F_{p}$ of order $q.$ Using (a), we can randomly choose a value of $a \in F_{p}$ and check whether $b = a^{\frac{p−1}{q}}$ satisfies $b \neq 1$. How likely are we to succeed? In other words, compute the value of the ratio $$\frac{a \in F_{p} : a^{\frac{p−1}{q}} \neq 1}{F_{p}}$$
By Fermat's Theorem, we have $b^q\equiv (a^{(p-1)/q})^q\equiv 1\pmod{p}$. So the order of $b$ divides the prime $q$. But $q$ has very few divisors: if $b\ne 1$, then $b$ has order $q$.
For the second problem, the "bad" $a$ are the $a$ such that $a^{(p-1)/q}\equiv 1\pmod{p}$. These are the $a$ whose order divides $(p-1)/q$.
It is convenient now to use a primitive root $g$ of $p$ for the rest of the argument. Let $a\equiv g^k\pmod{p}$. Then $(g^k)^{(p-1)/q}\equiv 1\pmod{p}$ if and only if $p-1$ divides $k(p-1)/q$, that is, if and only if $k$ is a multiple of $q$. There are $(p-1)/q$ such multiples of $q$ in the interval $0$ to $p-1$. Thus the proportion of "bad" $a$ is $\frac{(p-1)/q}{p-1}$, that is, $\frac{1}{q}$. It follows that the probability of success is $1-\dfrac{1}{q}$.