most recent 30 from http://mathoverflow.net 2013-05-21T17:59:52Z http://mathoverflow.net/feeds/question/108160 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108160/count-number-of-i-such-that-p-2i-mod-p-2-l xwangae 2012-09-26T12:45:20Z 2012-09-29T23:19:26Z

<p>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$.</p> <p>This problem seems to be too complex, let me begin with a simple one:</p> <p>given two different primes $p_1, p_2$, integer $L$ and another integer $l&lt; 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$$</p> <p>we can assume $L=c*2^d$ for some integers $c,d$, because we can first use dyadic intervals</p>

http://mathoverflow.net/questions/108160/count-number-of-i-such-that-p-2i-mod-p-2-l/108174#108174 Gerhard Paseman 2012-09-26T15:50:37Z 2012-09-29T23:19:26Z

<p>Until a better idea strikes me, why not give this one a go?</p> <p>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.</p> <p>Gerhard "I Saw This On ArXiv" Paseman, 2012.09.26</p>