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?


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.

  • $\begingroup$ what do you mean by closed under? $\endgroup$ – user136088 Mar 29 '14 at 23:49
  • $\begingroup$ "closed under subtraction" means if $a$ is there and $b$ is there then $a-b$ is also there. $\endgroup$ – Gerry Myerson Mar 30 '14 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$ – Bill Dubuque Mar 30 '14 at 0:04

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.