Sunday, August 26, 2018

elementary number theory - Prove: $gcd(n^a-1,n^b-1)=n^{gcd(a,b)}-1$

I'm trying to prove the following statement:
$$\forall_{a,b\in\Bbb{N^{+}}}\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1$$




As for now I managed to prove that $n^{\gcd(a,b)}-1$ divdes $n^a-1$ and $n^b-1$:



Without loss of generality let $a>b$ (if $a=b$, the result is obvious), $n\neq1$ ($\gcd(0,0)$ makes no sense). Then if we let $a=kd, b=jd, d=\gcd(a,b)$, we see that for $n^{kd}-1$ we have $\frac{(n^d)^k-1}{n^d-1}=1+n^d+...+n^{d(k-1)}=C$ (it's a finite geometric series), so $n^a-1=(n^d-1)C$. Same works for $n^b-1$, so $n^d-1$ divides both of these numbers.



How to prove that $n^d-1$ not only divides both numbers, but is greatest common divisor?

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...