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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Mar 29, 2014 at 23:29
-
-
$\begingroup$ "closed under subtraction" means if $a$ is there and $b$ is there then $a-b$ is also there. $\endgroup$ 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$ Mar 30, 2014 at 0:04