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.

I have two prime powers $2^n$ and $5^n$ for some arbitrary $n$. Their gcd is $1$ but how do I get their integer linear combination which is $1$ in terms of $n$. In other words what will be the integers $a,b$ as functions of $n$ such that $a2^n+b5^n=1$.

The reason I am unable to apply the Euclidean algorithm is that I don't know $n$ beforehand.

Any help would be greatly appreciated. Thanks

share|improve this question
    
what do you mean integer linear combination which is 1 in terms of n.? might be obvious, but I am not aware of terminology, but that doesn't mean I will not be of help. :) –  Sabyasachi Mar 8 at 5:06
    
@Sabyasachi: It means what will be the integers $a,b$ such that $a2^n+b5^n=1$. –  Shahab Mar 8 at 5:09
    
@Sabyasachi Bezout's Theorem is that for integers $a,b$, $\exists x,y$ s.t. $ax+by=gcd(a,b)$. We seek to find this $x, y$. –  WChang Mar 8 at 5:10
    
@Mathster: Yes I know that. In that context what will be $x,y$ for $2^n,5^n$ is my question. –  Shahab Mar 8 at 5:11
    
Sorry, I was addressing that to Sabyasachi. –  WChang Mar 8 at 5:11

1 Answer 1

up vote 5 down vote accepted

There is undoubtedly a nicer answer, but here goes.

Note that $3\cdot 2+(-1)\cdot 5=1$. Because it looks nicer, let $a=3$ and $b=-1$.

Consider $(2a+5b)^{2n-1}$, and expand using the Binomial Theorem. Then the first $n$ terms will be divisible by $2^n$, and the last $n$ will be divisible by $5^n$.

That gives us the desired linear combination. Explicitly, the coefficient of $2^n$ is $\sum_{k=0}^{n-1}\binom{2n-1}{k}a^{n-1-k}b^{k}$, and we can write a similar expression for the coefficient of $5^n$.

share|improve this answer

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.