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?
Asked
Active
Viewed 820 times
0
user136088
- 251
1 Answers
2
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.
Bill Dubuque
- 272,048
-
what do you mean by closed under? – user136088 Mar 29 '14 at 23:49
-
"closed under subtraction" means if $a$ is there and $b$ is there then $a-b$ is also there. – Gerry Myerson Mar 30 '14 at 00: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 00:04