|
0
2
|
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? |
|||||||||||||||||||||||
|
|
1
|
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. |
||
|
|
