Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

closed as off topic by Franz Lemmermeyer, Noah Stein, Bugs Bunny, Dan Petersen, Gjergji Zaimi Sep 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
add comment

1 Answer 1

up vote 1 down vote accepted

Until a better idea strikes me, why not give this one a go?

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.

Gerhard "I Saw This On ArXiv" Paseman, 2012.09.26

share|improve this answer
    
thanks for your idea, I will try your ways to see want I can get. I update a simple version, which seems to be much easier.(although I don't know how to solve it :-) –  xwangae Sep 29 '12 at 13:18
    
exatly solution is wanted, a relative error one might also work for my problem –  xwangae Sep 29 '12 at 13:19
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.