Is $\gcd(an + 1, bn) = 1$ for infinitely many integers $n$?

74 Views Asked by At

Let $a,b,n$ be positive integers. If $a$ and $b$ are coprime, then is $\gcd(an + 1, bn) = 1$ for infinitely many integers $n$?

Clearly the result doesn't have to hold for all $n$; take $n = 3, a = 5, b = 4.$ Also, $\dfrac{an+1}{bn}\to \dfrac{a}b$ as $n\to\infty$, but I'm not sure if this is useful. I know that to show two numbers are coprime it suffices to show that there's no prime dividing both of them or that an integer linear combination of the two numbers equals one.

2

There are 2 best solutions below

4
On

This is essentially never true: take $p$ a prime factor of $b$. Then $a$ is prime to $p$, hence there are infinitely many $n$ so that $an=-1$ mod $p$; this implies that $an+1$ and $bn$ are both divisible by $p$. On the other hand, if $b=1$ then it is true that $an+1$ and $n$ are coprime for all $n$ no matter what $a$ is.

(This answered the first version of the question---whether or not $an+1$ and $bn$ were coprime for sufficiently large $n$; after this answer was posted the OP then edited to ask a different question.)

2
On

If $n$ is a multiple of $ab$ i.e. $n=kab$ for some positive integer $k$, then the only prime factors that would divide $bn$ are the prime factors of $a$, $b$, and $k$, and $an+1$ wouldn't be divisible by any of these prime factors (it is $1$ in modular $a$, $b$, and $k$), therefore the two quantities are relatively prime. So the answer to your question is yes.