# Proving two equations involving the greatest common divisor

Show or prove that $$\gcd \left(\frac{a^{2m}-1}{a+1} ,a + 1\right )=\gcd(a + 1 , 2m),$$ and that $$\gcd \left(\frac{a^{2m + 1}+1}{a+1} , a + 1\right)=\gcd(a + 1 , 2m + 1).$$

-
I have an example! – marcelolpjunior May 15 '13 at 18:38
((a^(m)-1)/(a-1),a-1)=(a-1,m) d = (a^(m−1) + a^(m−2) + • • • + a + 1, a − 1)= (a^(m−1) − 1) + (a^(m−2) − 1) + • • • + (a − 1) + m, a – 1 we know that a − 1|(a^(m−1) − 1) + (a^(m−2) − 1) + • • • + (a − 1) (a^(m−1) − 1) + (a^(m−2) − 1) + • • • + (a − 1) = n(a − 1) Soon d = (n(a − 1) + m, a − 1) = (a − 1, n(a − 1) + m) = (a − 1, m) – marcelolpjunior May 15 '13 at 18:46
Does that help? – marcelolpjunior May 15 '13 at 19:07
Try to invest some time into making it readable. (This site supports LaTeX, which makes mathematical formulas much easier to read.) Also consider editing your question to add your own work to it. – TMM May 15 '13 at 19:10

Let integer $d\ne0$ divides $a+1$ i.e., $a+1=c\cdot d$(say) where $c\ne0$ is some integer

$\implies a=c\cdot d-1$

$$\gcd \left(\frac{a^{2m}-1}{a+1} ,a + 1\right )$$ $$=\gcd \left(\frac{(c\cdot d-1)^{2m}-1}{c\cdot d} ,c\cdot d\right )$$ $$=\gcd \left( (c\cdot d)^{2m-1}-\binom{2m}1(c\cdot d)^{2m-2}+ \binom{2m}2(c\cdot d)^{2m-3}+\cdots+\binom{2m}{2m-2}(c\cdot d)-\binom{2m}{2m-1},c\cdot d\right)$$

$$=\gcd\left( c\cdot d\{(c\cdot d)^{2m-2}-\binom{2m}1(c\cdot d)^{2m-3}+ \binom{2m}2(c\cdot d)^{2m-4}+\cdots+\binom{2m}{2m-2}\}-2m,c\cdot d\right)\text{ as } \binom{2m}{2m-1}=\binom{2m}{2m-(2m-1)}=\binom{2m}1=2m$$

$$=\gcd(-2m, c\cdot d)\text{ as }\gcd(p+kq,q)=\gcd(p,q)$$

$$=\gcd(2m, a+1)$$

Can you solve the second one now?

-
((a^(m)-1)/(a-1),a-1)=(a-1,m) d = (a^(m−1) + a^(m−2) + • • • + a + 1, a − 1)= (a^(m−1) − 1) + (a^(m−2) − 1) + • • • + (a − 1) + m, a – 1 we know that a − 1|(a^(m−1) − 1) + (a^(m−2) − 1) + • • • + (a − 1) (a^(m−1) − 1) + (a^(m−2) − 1) + • • • + (a − 1) = n(a − 1) Soon d = (n(a − 1) + m, a − 1) = (a − 1, n(a − 1) + m) = (a − 1, m) – marcelolpjunior May 15 '13 at 18:46
@user77961, that's what I did , may be in a different way – lab bhattacharjee May 15 '13 at 18:49
Your answer is very good, but I think for the level I'm can not understand well ... Not yet know these figures in parentheses are one above the other. I'm sorry. – marcelolpjunior May 15 '13 at 18:53
@user77961, do you know Binomial Theorem? – lab bhattacharjee May 15 '13 at 18:55
Yes I know. This number then, are the binomial coefficients? – marcelolpjunior May 15 '13 at 19:02

I will show that $$\gcd \left(\frac{a^{2m}-1}{a+1} ,a + 1\right )=\gcd(a + 1 , 2m)$$

First note that $$a^{2m}-1=(a^2)^m-1=(a^2-1)(a^{2(m-1)}+ a^{2(m-2)}+\cdots+1)$$

so that $$\frac{a^{2m}-1}{a+1}=(a-1)(a^{2(m-1)}+\cdots+1)$$

But $a\equiv -1 \mod a+1$ so we have

$$\frac{a^{2m}-1}{a+1}\equiv -2((-1)^{2(m-1)}+\cdots+1)=-2m$$

which means $$\gcd \left(\frac{a^{2m}-1}{a+1} ,a + 1\right )=\gcd(a + 1 , 2m)$$ Can you do something similar with the other?

-
Is to make this statement without using mod? More or less as in the example of the issue: math.stackexchange.com/questions/392745/theory-number-gcd – marcelolpjunior May 15 '13 at 19:41
@user77961 Could you rephrase? – Pedro Tamaroff May 15 '13 at 20:00