How many $x$ less than or equal to $n$ are there when
$x\equiv i(\text{mod }q) \equiv 0(\text{mod }p)$?
I am just looking for an upper and lower bound.
Asked
Active
Viewed 20 times
0
Varun Rajkumar
- 201
1 Answers
1
If $\gcd(p,q)=1$, there is exactly one solution in any consecutive block of $pq$ integers. Thus in the range $1,2,\ldots, n$ (or any range of $n$ consecutive integers), the number of solutions is in the range $$ \left\lfloor\frac {n}{pq}\right\rfloor\ \ldots\ \left\lceil \frac n{pq}\right\rceil .$$
Hagen von Eitzen
- 374,180