2

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}}$$

Stefan Hamcke
  • 27,733
leeha
  • 157
  • 1
  • 5
  • 1
    (a) Use Fermat's little theorem to show that $b^q=1$. (b) How many roots can the polynomial $x^q-1$ have in a field? Use the existence of a primitive root to argue there is a $b\ne1$ with $b^q=1$ (hint: set $a$ to be a primitive root). Now the $b$s with $b^q=1$ form a subgroup of order...? – anon Sep 16 '13 at 02:07

1 Answers1

2

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}$.

6infinity8
  • 178
André Nicolas
  • 507,029