0
$\begingroup$

Let $m,n \in \mathbb N$ and $d=gcd(m,n).$
Prove that if w is both an m-th root of unity and an n-th root of unity, then w is a d-th root of unity.

How would i begin about starting this type of proof?

$\endgroup$

1 Answer 1

2
$\begingroup$

Hint $ $ The set $E\,$ of exponents $\,k\,$ such that $\,w^k = 1\,$ are closed under subtraction so, iterating, also closed under mod, so also under gcd. $\ $ Or, explicitly, use the Bezout identity for the gcd.

$\endgroup$
3
  • $\begingroup$ what do you mean by closed under? $\endgroup$
    – user136088
    Commented Mar 29, 2014 at 23:49
  • $\begingroup$ "closed under subtraction" means if $a$ is there and $b$ is there then $a-b$ is also there. $\endgroup$ Commented Mar 30, 2014 at 0:01
  • $\begingroup$ @user136088 That $E$ is closed under subtraction means $\,j,k\in E\,\Rightarrow\, j-k\in E.\,$ So you can do Euclid's algorithm in $E$ since $\, n< m\in E\,\Rightarrow\, n,\,m\!-\!n\in E\,\Rightarrow\,\cdots\,\Rightarrow\ n,\ m\ {\rm mod}\ n\in E,\,$ since $\,m\ {\rm mod}\ n\, = m-qn = m-n-n-\cdots -n.$ Continuing as in the Euclidean algorithm we reach $\,\gcd(n,m)\in E.\,$ Or you can derive that in one fell swoop using the Bezout identity for the gcd $\,d = jn+km\,$ to rewrite $\,w^d\,$ as a product of powers of $\,w^a,\,w^b,\,$ so $\,w^d = 1.$ $\endgroup$ Commented Mar 30, 2014 at 0:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .