Skip to main content
added 18 characters in body
Source Link
Maciej Ulas
  • 801
  • 10
  • 14

As was observed by @JoshuaZ, for given $a, c\in\mathbb{N}$, the equation $(*)\; a^xy+x=c$ has only finitely many solutions. On the other hand, I show that for any $a$ and any $N\in\mathbb{N}$ one can find $c=c(a, N)$ such that the equation $(*)$ has at least $N$ solutions. To see this, let us observe that $(*)$ has a solution if and only if $$ c\equiv x\pmod{a^x}. $$ Thus, to show that $(*)$ it is enough to find posittive integers $x_{1}<x_{2}<\ldots<x_{N}$ such that the system of congruences $$ (**)\quad c\equiv x_{1}\pmod{a^{x_{1}}},\; c\equiv x_{2}\pmod{a^{x_{2}}},\;\ldots, \;c\equiv x_{N}\pmod{a^{x_{N}}}. $$$$ (**)\quad c\equiv x_{1}\pmod{a^{x_{1}}},\; c\equiv x_{2}\pmod{a^{x_{2}}},\;\ldots, \;c\equiv x_{N}\pmod{a^{x_{N}}} $$ Applyting gneralhas a solution. Applying general form of cheineschinese remainder theorem we need to find $x_{1}, x\ldots, x_{N}$ such that for each $i, j\in\{1,\ldots, N\}, i\neq j$ we have $\gcd(a^{x_{i}},a^{x_{j}})=a^{x_{i}}|x_{j}-x_{i}$. To construct suitable sequence it is is enough to define $$ x_{1}=1, x_{n}=a^{x_{n-1}}+x_{n-1} $$
and observe (using simple induction on $k$) that $$ x_{n+k}=\sum_{i=0}^{k-1}a^{x_{n+i}}+x_{n}. $$ This clearly implies that $a^{x_{i}}|x_{j}-x_{i}$ for $j>i$. Computing now the solution $c=c(a, N)$ of the system $(**)$ we get that there are positive integers $y_{1}, \ldots, y_{N}$ such that the equation $(*)$ has solutions $(x_{1}, y_{1}), \ldots, (x_{N}, y_{N})$.

As was observed by @JoshuaZ, for given $a, c\in\mathbb{N}$, the equation $(*)\; a^xy+x=c$ has only finitely many solutions. On the other hand, I show that for any $a$ and any $N\in\mathbb{N}$ one can find $c=c(a, N)$ such that the equation $(*)$ has at least $N$ solutions. To see this, let us observe that $(*)$ has a solution if and only if $$ c\equiv x\pmod{a^x}. $$ Thus, to show that $(*)$ it is enough to find posittive integers $x_{1}<x_{2}<\ldots<x_{N}$ such that the system of congruences $$ (**)\quad c\equiv x_{1}\pmod{a^{x_{1}}},\; c\equiv x_{2}\pmod{a^{x_{2}}},\;\ldots, \;c\equiv x_{N}\pmod{a^{x_{N}}}. $$ Applyting gneral form of cheines remainder theorem we need to find $x_{1}, x\ldots, x_{N}$ such that for each $i, j\in\{1,\ldots, N\}, i\neq j$ we have $\gcd(a^{x_{i}},a^{x_{j}})=a^{x_{i}}|x_{j}-x_{i}$. To construct suitable sequence it is is enough to define $$ x_{1}=1, x_{n}=a^{x_{n-1}}+x_{n-1} $$
and observe (using simple induction on $k$) that $$ x_{n+k}=\sum_{i=0}^{k-1}a^{x_{n+i}}+x_{n}. $$ This clearly implies that $a^{x_{i}}|x_{j}-x_{i}$ for $j>i$. Computing now the solution $c=c(a, N)$ of the system $(**)$ we get that there are positive integers $y_{1}, \ldots, y_{N}$ such that the equation $(*)$ has solutions $(x_{1}, y_{1}), \ldots, (x_{N}, y_{N})$.

As was observed by @JoshuaZ, for given $a, c\in\mathbb{N}$, the equation $(*)\; a^xy+x=c$ has only finitely many solutions. On the other hand, I show that for any $a$ and any $N\in\mathbb{N}$ one can find $c=c(a, N)$ such that the equation $(*)$ has at least $N$ solutions. To see this, let us observe that $(*)$ has a solution if and only if $$ c\equiv x\pmod{a^x}. $$ Thus, to show that $(*)$ it is enough to find posittive integers $x_{1}<x_{2}<\ldots<x_{N}$ such that the system of congruences $$ (**)\quad c\equiv x_{1}\pmod{a^{x_{1}}},\; c\equiv x_{2}\pmod{a^{x_{2}}},\;\ldots, \;c\equiv x_{N}\pmod{a^{x_{N}}} $$ has a solution. Applying general form of chinese remainder theorem we need to find $x_{1}, x\ldots, x_{N}$ such that for each $i, j\in\{1,\ldots, N\}, i\neq j$ we have $\gcd(a^{x_{i}},a^{x_{j}})=a^{x_{i}}|x_{j}-x_{i}$. To construct suitable sequence it is is enough to define $$ x_{1}=1, x_{n}=a^{x_{n-1}}+x_{n-1} $$
and observe (using simple induction on $k$) that $$ x_{n+k}=\sum_{i=0}^{k-1}a^{x_{n+i}}+x_{n}. $$ This clearly implies that $a^{x_{i}}|x_{j}-x_{i}$ for $j>i$. Computing now the solution $c=c(a, N)$ of the system $(**)$ we get that there are positive integers $y_{1}, \ldots, y_{N}$ such that the equation $(*)$ has solutions $(x_{1}, y_{1}), \ldots, (x_{N}, y_{N})$.

Source Link
Maciej Ulas
  • 801
  • 10
  • 14

As was observed by @JoshuaZ, for given $a, c\in\mathbb{N}$, the equation $(*)\; a^xy+x=c$ has only finitely many solutions. On the other hand, I show that for any $a$ and any $N\in\mathbb{N}$ one can find $c=c(a, N)$ such that the equation $(*)$ has at least $N$ solutions. To see this, let us observe that $(*)$ has a solution if and only if $$ c\equiv x\pmod{a^x}. $$ Thus, to show that $(*)$ it is enough to find posittive integers $x_{1}<x_{2}<\ldots<x_{N}$ such that the system of congruences $$ (**)\quad c\equiv x_{1}\pmod{a^{x_{1}}},\; c\equiv x_{2}\pmod{a^{x_{2}}},\;\ldots, \;c\equiv x_{N}\pmod{a^{x_{N}}}. $$ Applyting gneral form of cheines remainder theorem we need to find $x_{1}, x\ldots, x_{N}$ such that for each $i, j\in\{1,\ldots, N\}, i\neq j$ we have $\gcd(a^{x_{i}},a^{x_{j}})=a^{x_{i}}|x_{j}-x_{i}$. To construct suitable sequence it is is enough to define $$ x_{1}=1, x_{n}=a^{x_{n-1}}+x_{n-1} $$
and observe (using simple induction on $k$) that $$ x_{n+k}=\sum_{i=0}^{k-1}a^{x_{n+i}}+x_{n}. $$ This clearly implies that $a^{x_{i}}|x_{j}-x_{i}$ for $j>i$. Computing now the solution $c=c(a, N)$ of the system $(**)$ we get that there are positive integers $y_{1}, \ldots, y_{N}$ such that the equation $(*)$ has solutions $(x_{1}, y_{1}), \ldots, (x_{N}, y_{N})$.