MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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.

share|cite|improve this answer

Your Answer


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.