1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ This question has been asked recently. $\endgroup$ – Lucian Jan 23 '14 at 16:20
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user21820 Jan 23 '14 at 15:17
  • $\begingroup$ 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? $\endgroup$ – Math Dude Jan 23 '14 at 15:43
  • $\begingroup$ is the answer 8? that's what i got $\endgroup$ – Math Dude Jan 23 '14 at 15:46
  • $\begingroup$ 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. $\endgroup$ – user21820 Jan 24 '14 at 1:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.