# 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?

• This question has been asked recently. – Lucian Jan 23 '14 at 16:20

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.)

• It might help to look at the roots of unity in the field of complex numbers first, as they are nicely around a circle and give much of the right ideas about the general case. – user21820 Jan 23 '14 at 15:17
• I got hte list of the roots of unity for 42nd and 70th: 1, e^pi i / 21, e ^ 2 pi i /21 .... e^41pi i /21 for 42nd and 70th: 1, e^pi i / 35, e^2pi i /35 .... e^69 pi i/ 35 So should I go and find literally each one one by one? – Math Dude Jan 23 '14 at 15:43
• is the answer 8? that's what i got – Math Dude Jan 23 '14 at 15:46
• The list you have is just the $n$-th roots of unity. A primitive $n$-th root of unity is one that is not a $k$-th root of unity for any positive integer $k<n$. For example, $1$ isn't a (complex) primitive $n$-th root of unity for any $n>1$. Likewise $e^{i2\pi\frac{2}{42}} = e^{i2\pi\frac{1}{21}}$ isn't a primitive $42$nd root of unity. Also I realized that there is a simpler way than what I had in mind. I'll edit to give more detail of both. – user21820 Jan 24 '14 at 1:09