Find all integers $a$ that satisfy $c \equiv a \pmod{ab+1}$

143 Views Asked by At

Let $a,b,c$ positive integers with $b|c$ I am looking for triplets that satisfy $c \equiv a \pmod{ab+1}$.

What I found by now is that given a solution, we can write $c=q(ab+1)+a=a(qb+1)+q$ So we get $c \equiv q \pmod{qb+1}$ where q is the whole part of $\frac{c}{ab+1}$.

Another thing I observed is that both $a$ and $c$ are coprime to $ab+1$. This means they are both elements of the multiplicative group modulo $ab+1$. It seems like something can be done to get more information, but I am stuck.

Thanks

1

There are 1 best solutions below

2
On BEST ANSWER

First, we have $b \mid c$, which means that we can replace $c = bk$. Now, we have $a \equiv bk \pmod{ab+1}$. As you noted, we can see that $\gcd(b,ab+1)=1$. Thus, we can instead write $k \equiv \frac{a}{b} \pmod{ab+1}$.

We can also note that- $$ab \equiv -1 \pmod{ab+1} \implies \frac{1}{b} \equiv -a \pmod{ab+1} \implies k \equiv \frac{a}{b} \equiv -a^2 \pmod{ab+1}$$ Thus, $k = (ab+1)q - a^2$ . Substituting this back, we get our solutions: $$\{a,b,c\} = \{a \space ,\space b \space, \space b ((ab+1)q-a^2)\}$$ where $q$ is any integer.

If you want $a$ instead in terms of $b,c$ , we can see that $c = -a^2+b^2a+bq$ $$a^2-(b^2)a+(c-bq)=0$$ This provides us a quadratic equation. $$a = \frac{b^2 \pm \sqrt{b^4+4bq-4c}}{2}$$ where $q$ is a suitable integer such that $b^4+4bq-4c=x^2$