I just stumbled, by pure accident, on this: $$ \gcd \left(\frac{(m+1)^n-1}{m},m\right)=\gcd \left(\frac{(n+1)^m-1}{n},n\right) $$ It probably has a straightforward proof but more than a proof I want a conceptual background for it. Is it related to any known reciprocity laws or something?

  • 4
    $\begingroup$ No. The first number simply equals $\gcd (n,m)$ and the second is $\gcd (m,n)$. To show this, use just one step of the Euclidean algorithm for the $\gcd$. $\endgroup$ – Crostul May 3 '17 at 5:51

Note that $$(m+1)^n=1+nm+\frac{n(n-1)}2m^2+\ldots $$ where everything hidden in the dots is also a multiple of $m^2$. Hence $\frac{(m+1)^n-1}{m}$ is just $n$ plus a multiple o $m$, which can be ignored when taking the $\gcd$ with $m$. In other words, the left hand side is just$\gcd(n,m)$ (and the right hand side $\gcd(m,n)$).

  • $\begingroup$ Great, thanks. Except that you should share credit with @Crostul who noticed this (without proof, but...) slightly earlier in a comment above. $\endgroup$ – მამუკა ჯიბლაძე May 3 '17 at 5:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.