Possible Duplicate:
Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$
Let $p$ and $q$ be distinct primes.
I wonder is the following statement always true? $$\gcd(x^p-1, x^q-1) \stackrel{?}{=} x-1$$
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Related : math.stackexchange.com/questions/7473/… $\endgroup$– lab bhattacharjeeJan 2, 2013 at 16:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
More generally, we have $\gcd(x^n-1,x^m-1)=x^{\gcd(n,m)}-1$.
answered Jan 2, 2013 at 15:39
-
$\begingroup$ I have just found www2.hawaii.edu/~robertop/Courses/Math_454/Handouts/… Do you know a proof? $\endgroup$ Jan 2, 2013 at 15:50
-
$\begingroup$ @user706071 Strong induction works, since for $n\geq m$, $\gcd(x^n-1, x^m-1) = \gcd(x^n-x^m, x^m-1) = \gcd(x^{n-m} -1, x^m-1)$ $\endgroup$ Jan 2, 2013 at 16:24