A few months ago while dealing with squarefree integers in arithmetic progressions, this problem arose about finding bounded solutions to linear congruences.
The problem:
I have constants $a$ and $q$ with $(a,q)=1$, and a variable $x$, and my goal is to show that
$$\sum_{d\le \sqrt{x}}{\left[\exists~n\le x~|~d^2|n,~n\equiv a~(\text{mod}~q)\right]} = O\left(\left(\frac{x}{q}\right)^{1/2}\right)$$
Basically, for each value of $d$, the sum adds $1$ if there exists an $n\le x$ satisfying the linear congruences $n\equiv a~(\text{mod}~q)$ and $n\equiv 0~(\text{mod}~d^2)$.
I already know that $d$ and $q$ are coprime from the fact that $(a,q)=1$, meaning there is a solution to the congruences less than $d^2q$. This means for $d^2q\le x$ the inside of the summation is always one, but for $d^2q>x$ there isn’t always a solution.
My heuristics:
The sum $\sum_{d\le\sqrt{x}}$ can be split into two parts $\sum_{d^2q\le x} + \sum_{x/q\lt d^2\le x}$, where the first part is $O((x/q)^{1/2})$ trivially, and the second can be manipulated as follows:
$$\sum_{x/q\lt d^2\le x}{\left[\exists~n\le x~|~d^2|n,~n\equiv a~(\text{mod}~q)\right]} = \sum_{x/q\lt d^2\le x}{\left[\exists~k\le \left[\frac{x}{d^2}\right]\mid~kd^2\equiv a~(\text{mod}~q)\right]}$$
and since $\left[\frac{x}{d^2}\right] \le q$, this is equivalent to asking the question - is the quantity $a(d^2)^{-1}~(\text{mod}~q)$ less than $\left[\frac{x}{d^2}\right]$? To which there is most likely an $\left(\frac{x}{d^2q}\right)$ probability. Then sum these probabilities up over the interval to get $O((x/q)^{1/2})$ again.
In fact, I believe it should be possible to get this bound
$$O\left(\left(\frac{x}{q}\right)^{1/2}\prod_{p\mid q}{\left(1-\frac{1}{p}\right)}\right)$$
instead, since $(d,q)=1$ would introduce the product factor.
What I've tried so far:
From the heuristics, it seems to me that there should be a fairly simple solution to this problem. But despite my best efforts, I've still made no progress.
One thing I tried was noticing that $n(n-a)\equiv 0~(\text{mod}~d^2q)$ and setting up a quadratic equation. This made the problem of finding a solution to the congruences equivalent to finding a $k$ less than $x^2/{d^2q}$ such that $a^2+4kd^2q$ is a perfect square. However, this didn't work in the end.
I've tried searching on the internet for things like "bounded solutions to congruences" without any luck.
I also manipulated the sum so that I could expand the congruence condition into another summation. Then interchanging summations turned the problem into finding the number of integers $k$ less than $q$ such that $ak^{-1}~(\text{mod}~q)~<~\sqrt{x/k}$, but I didn't know how to proceed from here.
I'd be grateful if anyone can provide a solution to this problem or can tell me if this type of sum is already known. It would be nice if there was already a paper that includes sums of this type so that I can do more of my own research.