# Bezouts Identity for prime powers

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

-
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 '14 at 5:06
@Sabyasachi: It means what will be the integers $a,b$ such that $a2^n+b5^n=1$. – Shahab Mar 8 '14 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$. – William Chang Mar 8 '14 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 '14 at 5:11
Sorry, I was addressing that to Sabyasachi. – William Chang Mar 8 '14 at 5:11

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