Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).$$

share|improve this question
3  
What have you tried? –  TMM May 15 '13 at 18:13
    
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
2  
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
add comment

2 Answers 2

up vote 2 down vote accepted

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?

share|improve this answer
    
((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
1  
@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
show 1 more comment

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?

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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