Return to Answer

The answer is yes, there exists $c$ and $d$, even with $c = 1$, and $d \ll (\log(n))^{O(1)}$. This follows from a result of Iwaniec.

It suffices to assume that $(a,b) = 1$. Suppose that $(n,b) = e$, which implies that $(a,e) = 1$.

Since $b$ is divisible by $e$, it follow that $(a+bk,e) = 1$ for all integers $k$. Let $m$ denote the largest factor of $n$ such that $(m,e) = 1$, it clearly satisfies $(m,b) = 1$.

If $(a+bk,m) = 1$, then because $(a+bk,e) = 1$, one also has $(a+bk,n) = 1$.

Hence the problem becomes: given an integer $m$, and an arithmetic progression $$a, a + b, a + 2b, a+3b, a+4b, \ldots $$ with common difference $b$ prime to $m$, can one find a small integer $d$ such that $a+db$ is prime to $m$? Equivalently, let $g \in \mathbf{Z}$ be any multiplicative inverse to $b$ mod $m$, then does there exist a small $d$ such that $ag + dbg$ is prime to $m$? Equivalently, does there exist a small $d$ such that $ag + d$ is prime to $m$?

Recall the definition of the Jacobsthal function: $j(m)$ is the smallest integer such that any arithmetic progression of length $j(m)$ (with common difference one) contains an element which is co-prime to $m$.

If $m|n$, then $j(m) \le j(n)$. In particular, there exists a $d \le j(m) \le j(n)$ with $c = 1$ such that $ac+bd$ is prime to $n$.

Finally (the hard part), by a result of Iwaniec, one has $$j(n) \ll \log^{2+\epsilon}(n) = \log(n)^{O(1)}.$$

The answer is yes, there exists $c$ and $d$, even with $c = 1$, and $d \ll (\log(n))^{O(1)}$. This follows from a result of Iwaniec.

It suffices to assume that $(a,b) = 1$. Suppose that $(n,b) = e$, which implies that $(a,e) = 1$.

Since $b$ is divisible by $e$, it follow that $(a+bk,e) = 1$ for all integers $k$. Let $m$ denote the largest factor of $n$ such that $(m,e) = 1$, it clearly satisfies $(m,b) = 1$.

If $(a+bk,m) = 1$, then because $(a+bk,e) = 1$, one also has $(a+bk,n) = 1$.

Hence the problem becomes: given an integer $m$, and an arithmetic progression $$a, a + b, a + 2b, a+3b, a+4b, \ldots $$ with common difference $b$ prime to $m$, can one find a small integer $d$ such that $a+db$ is prime to $m$? Equivalently, let $g \in \mathbf{Z}$ be any multiplicative inverse to $b$ mod $m$, then does there exist a small $d$ such that $ag + dbg$ is prime to $m$? Equivalently, does there exist a small $d$ such that $ag + d$ is prime to $m$?

Recall the definition of the Jacobsthal function: $j(m)$ is the smallest integer such that any arithmetic progression of length $j(m)$ (with common difference one) contains an element which is co-prime to $m$.

If $m|n$, then $j(m) \le j(n)$. In particular, there exists a $d \le j(m) \le j(n)$ with $c = 1$ such that $ac+bd$ is prime to $n$.

Finally (the hard part), by a result of Iwaniec (Demonstratio Math. 11 (1978), 225-231 (MR0499895)), if $n$ has $r$ distinct prime factors, then $j(n) \ll r^2 \log^2 r$, which implies that $$j(n) \ll \log^{2}(n) = \log(n)^{O(1)}.$$

The answer is yes, there exists $c$ and $d$, even with $c = 1$, and $d \ll \log^2(n)$. This follows from a result of Iwaniec.

It suffices to assume that $(a,b) = 1$. Suppose that $(n,b) = e$, which implies that $(a,e) = 1$.

Since $b$ is divisible by $e$, it follow that $(a+bk,e) = 1$ for all integers $k$. Let $m$ denote the largest factor of $n$ such that $(m,e) = 1$, it clearly satisfies $(m,b) = 1$.

If $(a+bk,m) = 1$, then because $(a+bk,e) = 1$, one also has $(a+bk,n) = 1$.

Hence the problem becomes: given an integer $m$, and an arithmetic progression $$a, a + b, a + 2b, a+3b, a+4b, \ldots $$ with common difference $b$ prime to $m$, can one find a small integer $d$ such that $a+db$ is prime to $m$? Equivalently, let $g \in \mathbf{Z}$ be any multiplicative inverse to $b$ mod $m$, then does there exist a small $d$ such that $ag + dbg$ is prime to $m$? Equivalently, does there exist a small $d$ such that $ag + d$ is prime to $m$?

Recall the definition of the Jacobsthal function: $j(m)$ is the smallest integer such that any arithmetic progression of length $j(m)$ (with common difference one) contains an element which is co-prime to $m$.

If $m|n$, then $j(m) \le j(n)$. In particular, there exists a $d \le j(m) \le j(n)$ with $c = 1$ such that $ac+bd$ is prime to $n$.

Finally (the hard part), by a result of Iwaniec, one has $$j(n) \ll \log^{2+\epsilon}(n) = \log(n)^{O(1)}.$$

The answer is yes, there exists $c$ and $d$, even with $c = 1$, and $d \ll (\log(n))^{O(1)}$. This follows from a result of Iwaniec.

It suffices to assume that $(a,b) = 1$. Suppose that $(n,b) = e$, which implies that $(a,e) = 1$.

Since $b$ is divisible by $e$, it follow that $(a+bk,e) = 1$ for all integers $k$. Let $m$ denote the largest factor of $n$ such that $(m,e) = 1$, it clearly satisfies $(m,b) = 1$.

If $(a+bk,m) = 1$, then because $(a+bk,e) = 1$, one also has $(a+bk,n) = 1$.

Hence the problem becomes: given an integer $m$, and an arithmetic progression $$a, a + b, a + 2b, a+3b, a+4b, \ldots $$ with common difference $b$ prime to $m$, can one find a small integer $d$ such that $a+db$ is prime to $m$? Equivalently, let $g \in \mathbf{Z}$ be any multiplicative inverse to $b$ mod $m$, then does there exist a small $d$ such that $ag + dbg$ is prime to $m$? Equivalently, does there exist a small $d$ such that $ag + d$ is prime to $m$?

Recall the definition of the Jacobsthal function: $j(m)$ is the smallest integer such that any arithmetic progression of length $j(m)$ (with common difference one) contains an element which is co-prime to $m$.

If $m|n$, then $j(m) \le j(n)$. In particular, there exists a $d \le j(m) \le j(n)$ with $c = 1$ such that $ac+bd$ is prime to $n$.

Finally (the hard part), by a result of Iwaniec, one has $$j(n) \ll \log^{2+\epsilon}(n) = \log(n)^{O(1)}.$$

The answer is yes, there exists $c$ and $d$, even with $c = 1$, and $d \ll \log^2(n)$. This follows from a result of Iwaniec.

It suffices to assume that $(a,b) = 1$. Suppose that $(n,b) = e$, which implies that $(a,e) = 1$.

Since $b$ is divisible by $e$, it follow that $(a+bk,e) = 1$ for all integers $k$. Let $m$ denote the largest factor of $n$ such that $(m,e) = 1$, it clearly satisfies $(m,b) = 1$.

If $(a+bk,m) = 1$, then because $(a+bk,e) = 1$, one also has $(a+bk,n) = 1$.

Hence the problem becomes: given an integer $m$, and an arithmetic progression $$a, a + b, a + 2b, a+3b, a+4b, \ldots $$ with common difference $b$ prime to $m$, can one find a small integer $d$ such that $a+db$ is prime to $m$? Equivalently, let $g \in \mathbf{Z}$ be any multiplicative inverse to $b$ mod $m$, then does there exist a small $d$ such that $ag + dbg$ is prime to $m$? Equivalently, does there exist a small $d$ such that $ag + d$ is prime to $m$?

Recall the definition of the Jacobsthal function: $j(m)$ is the smallest integer such that any arithmetic progression of length $j(m)$ (with common difference one) contains an element which is co-prime to $m$.

If $m|n$, then $j(m) \le j(n)$. In particular, there exists a $d \le j(m) \le j(n)$ with $c = 1$ such that $ac+bd$ is prime to $n$.

Finally (the hard part), by a result of Iwaniec, one has $$j(n) \ll \log^2(n).$$

The answer is yes, there exists $c$ and $d$, even with $c = 1$, and $d \ll \log^2(n)$. This follows from a result of Iwaniec.

It suffices to assume that $(a,b) = 1$. Suppose that $(n,b) = e$, which implies that $(a,e) = 1$.

Since $b$ is divisible by $e$, it follow that $(a+bk,e) = 1$ for all integers $k$. Let $m$ denote the largest factor of $n$ such that $(m,e) = 1$, it clearly satisfies $(m,b) = 1$.

If $(a+bk,m) = 1$, then because $(a+bk,e) = 1$, one also has $(a+bk,n) = 1$.

Hence the problem becomes: given an integer $m$, and an arithmetic progression $$a, a + b, a + 2b, a+3b, a+4b, \ldots $$ with common difference $b$ prime to $m$, can one find a small integer $d$ such that $a+db$ is prime to $m$? Equivalently, let $g \in \mathbf{Z}$ be any multiplicative inverse to $b$ mod $m$, then does there exist a small $d$ such that $ag + dbg$ is prime to $m$? Equivalently, does there exist a small $d$ such that $ag + d$ is prime to $m$?

Recall the definition of the Jacobsthal function: $j(m)$ is the smallest integer such that any arithmetic progression of length $j(m)$ (with common difference one) contains an element which is co-prime to $m$.

If $m|n$, then $j(m) \le j(n)$. In particular, there exists a $d \le j(m) \le j(n)$ with $c = 1$ such that $ac+bd$ is prime to $n$.

Finally (the hard part), by a result of Iwaniec, one has $$j(n) \ll \log^{2+\epsilon}(n) = \log(n)^{O(1)}.$$