Complex Numbers and Primitive Roots of Unity I'm not super familiar with primitive roots of unity and I am not quite sure how to express the following problem in algebraic form. Help is appreciated, thanks :D
Let R be the set of primitive $42^{\text{nd}}$ roots of unity, and let S be the set of primitive $70^{\text{th}}$ roots of unity. How many elements do R and S have in common?
 A: Can you express the set of primitive $n$-th roots of unity in terms of $n$ using $\gcd$? Once you have that, it should not be hard to find the two desired sets and their intersection.
[Edit: Here is the way I had in mind, which uses more than necessary.]
(We actually know what the set of primitive $n$-th roots of unity are, if we have just one of them. I will give a proof here, but the result is well-known.)
If $r$ is a primitive $n$-th root of unity,
  Let $f(x) = x^n-1$
  Let $S = \{ r^k : k \in \{1,2,...,n\} \}$
  $S$ contains only roots of $f$ because $(r^k)^n = (r^n)^k = 1^k = 1$
  $S$ contains exactly $n$ elements otherwise:
    $r^{k-m} = 1$ for some distinct $k,m \in \{1,2,...,n\}$
    $r$ is not a primitive $n$-th root of unity because $|k-m|<n$
    $\Rightarrow\Leftarrow$
  Therefore $S$ is all the roots of $f$ because $f$ has at most $\deg(f) = n$ roots
  The primitive $n$-th roots of unity are $\{ r^k : k \in \{1,2,...,n\} \wedge gcd(k,n) = 1 \}$
(Note that some fields do not have primitive roots, such as $\mathbb{R}$ does not have a primitive cube-root of unity, and $\overline{\mathbb{F}_2}$ does not have a primitive square-root of unity. But the algebraic closure of any field of characteristic $0$ has $\phi(n)$ primitive $n$-th roots of unity.)
Now here is an alternative method that doesn't make use of the above information at all:
If $r$ is both a $42$nd and $70$th primitive root of unity,
  $r^{14} = r^{gcd(42,70)} = 1$ and hence a contradiction
(In general, the sets of primitive $n$-th roots of unity are disjoint and partition the set of all roots of unity.)
