## count number of i such that ( (p_2*i) mod p_2) == l [closed]

How to determine the number of $i$'s, as fast as possible, such that $1\le i \le L$ and $((a*i+b)\mod p) \mod k = l$, where $1\lt a,b\lt p-1, p$ is a prime number, and $l \lt k \lt L \lt p$.

This problem seems to be too complex, let me begin with a simple one:

given two different primes $p_1, p_2$, integer $L$ and another integer $l< p_1$. Is there any way to compute the number of solutions of $1\leq i\leq L$ s.t., $$(p_2i)\mod p_1 = l$$

we can assume $L=c*2^d$ for some integers $c,d$, because we can first use dyadic intervals

-
 It sshould be close to L/k. How accurate of a count do you need? Gerhard "Ask Me About System Design" Paseman, 2012.09.26 – Gerhard Paseman Sep 26 at 14:33 Also, are a and k relatively prime? Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2012.09.26 – Gerhard Paseman Sep 26 at 14:37 Your new problem is easily seen to have the answer as either floor of or ceiling of L/p_1, and the method I suggest of using a multiplicative inverse (over p_1, called) f of p_2 will help you determine which, by checking if L mod p_1 is at most lf or not. Gerhard "Really, Ask Me About Jacobsthal" Paseman, 2012.09.29 – Gerhard Paseman Sep 29 at 14:26 yes, I realize it after this one is closed.. BYT, the way you propose for the original one is right. The problem is reduced to count the number of integer points in a triangle where the vertex is rational. thx a lot! – xwangae Sep 30 at 11:03

## closed as off topic by Franz Lemmermeyer, Noah Stein, Bugs Bunny, Dan Petersen, Gjergji ZaimiSep 29 at 13:17

Reduce the problem to $i + B \pmod p$ by the following. Find $f$ so that $fa\equiv1 \pmod p$. then transform the set $ai+b$ to $i +fb \pmod p$. You will also have to transform the set of numbers in $[0,p)$ of the form $tk+l$ to $tfk+fl \pmod p$, but if this set is nice you might be able to find quickly which parts lie in the transformed interval.