# Proof with roots of unity

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.
• "closed under subtraction" means if $a$ is there and $b$ is there then $a-b$ is also there. – Gerry Myerson Mar 30 '14 at 0:01
• @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.$ – Bill Dubuque Mar 30 '14 at 0:04