# Sequences of Coefficients in $a p^i + b q^j = 1$

Let $p$ and $q$ be different primes. Then for all positive integers $i$ and $j$ there exists integers $a_{ij}$ and $b_{ij}$ with

$$a_{ij} p^i + b_{ij} q^j = 1.$$

What is known about the sequence $\left((a_{ij},b_{ij})\right)_{i,j}$ of coefficients? Is there an explicit formula for calculating them? If no, is there a subsequence $i_k$, $j_k$ of indices, for which the sequence of coefficients $a_{i_kj_k}$ and $b_{i_kj_k}$ are known?

-
For every (i,j) pair there a lot of pairs (a,b) satisfacting this equation, so are there any other restrictions? Also, how explicit formula for them should be? Is something like $a_{ii}=p^{-i}\mod q^i$ acceptable? –  Nurdin Takenov Nov 25 '10 at 18:37
$b_{ij}$, for a fixed $j$, converges $p$-adically to $q^{-j}$. What else would you like ? –  Chris Wuthrich Nov 25 '10 at 18:51
$a_{ij} = p^{i(q^{j-1}(q-1)-1)}$. Too localized. –  Felipe Voloch Nov 25 '10 at 18:59
Euclid's algorithm gives an algorithm for computing these things. Is a "formula" different from an algorithm? If so, can you define "formula"? –  Kevin Buzzard Nov 25 '10 at 20:34
Let's make it $a_{ij}p^i-b_{ij}q^j=1$. Then there's a unique solution with $0\lt a_{ij}\lt q^j$ and $0\lt b_{ij}\lt p^i$. Conceivably, one could say something about this solution that OP would find satisfactory, though I doubt it. –  Gerry Myerson Nov 25 '10 at 21:55

At least some things can be said. Say we are looking at $a_{ij}p^i-b_{ij}q^j=1$ with $0\lt a_{ij}\lt q^j$ and $0\lt b_{ij}\lt p^i$. Then for fixed $j$ there are at most $q^j-q^{j-1}$ possible values for $a_{ij}.$ These values cycle periodically with each completely determined by the previous. (the period is likely to be too large to be practical though) and knowing any $a_{ij}$ yields the corresponding $b_{ij}$ Furthermore, $a_{0j}=1$ and $b_{0j}=0$. Similar remarks holds for fixed $i$ with $j$ allowed to grow. None of this is very useful computationally.
To partially avoid subscripts for the moment, let $a_{ij}p^i-b_{ij}q^j=1$ and also $up^{i+1}-vq^j=1$. Since $(up)p^i-vq^j=1$ we know that $up=a_{ij}+mq^j$ and $v=b_{i,j}-mp^i$ where $0 \le m \le p-1$ is the unique value making $\frac{a_{ij}+mq^j}{p}$ an integer. For example, in the simplest case of $p=2$ , we either have $a_{i+1,j}=a_{ij}/2$ and $b_{i+1,j}=b_{i,j}$ or else $a_{i+1,j}=(a_{ij}+q^j)/2$ and $b_{i+1,j}=b_{i,j}-2^i$ according as $a_{ij}$ is even or odd.
Also, we only need that $p$ and $q$ are relatively prime.