# 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

-

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

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

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 '12 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 '12 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 '12 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 '12 at 11:03

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.