While studying the basics of arithmetic, I've found one problem that I'm not able to solve:
Let a and m be two integers, $a \geq 2$ and $ m \geq 1$, with greatest common divisor $1$ ($\gcd(a,m) = 1$). Prove that $$\gcd\left(\frac{a^m - 1}{a -1},a -1\right) = \gcd(a-1, m)$$
As I said, I can't get it... probably it is very easy, but I don't see it. I suppose it should be possible to prove it just from definition and valuation p-adic.
From the definition of gcd, we have
$$\gcd\left(\frac{a^m - 1}{a -1},a -1\right) = \prod_{p \in\Bbb P} p^{\min\left(v_p\left(\frac{a^m - 1}{a -1}\right), v_p(a-1)\right)} $$ where $\Bbb P$ is the set of prime numbers.
We also have $$ \gcd(m,a -1) = \prod_{p \in\Bbb P} p^{\min(v_p(m), v_p(a-1))} $$
But what to do then?
I've also proved that $$ a^m - 1 = (a-1)\left(a^{m-1} + a^{m-2} + \cdots + 1\right)$$
However, I don't see if I can use it somehow.
I don't want you to solve it for me, but I would appreciate some small hint.
Thank you very much!
Use Euclidean algorithm.
$$\frac{a^m-1}{a-1}=a^{m-1}+a^{m-2}+\cdots + 1$$
$$\equiv 1^{m-1}+1^{m-2}+\cdots + 1\equiv m\pmod{a-1}$$
Therefore $\gcd\left(\frac{a^m-1}{a-1},a-1\right)=\gcd(m,a-1)$.
More generally:
$$\gcd\left(\frac{a^m-b^m}{a-b},a-b\right)=\gcd\left(m(\gcd(a,b))^{m-1},a-b\right)$$