Timeline for Odds of residue being small
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 3, 2015 at 16:01 | comment | added | Jan-Christoph Schlage-Puchta | There exists such a $\beta$ if and only if $AB^{-1}\equiv xy^{-1}\pmod{\alpha}$, where $1\leq x, y\leq \log\alpha$. As $AB^{-1}$ could be anything in $[1, \alpha]$ with equal probability, and there are less than $\log^2\alpha$ values $xy^{-1}$, chances are $<\frac{\log^2\alpha}{\alpha}$. | |
| Sep 3, 2015 at 15:54 | comment | added | user76479 | DO you think that given $A, B \bmod \alpha$, there will be a $\beta$ so that $\beta A,\beta B\bmod\alpha\leq\log\alpha$? If not always, what is probability that you can find a coprime pair $(A,B)$ so that such $\beta$ will exist to a given $\alpha$? | |
| Sep 3, 2015 at 15:43 | comment | added | Jan-Christoph Schlage-Puchta | Let $x_i$, $1\leq i\leq \log\alpha$ be the modular inverse of $i\pmod{\alpha}$. If $\alpha+x_i$ is not prime, write $AB=\alpha+x_i$ with $2\leq A, B<\alpha$. Hence you get small residues, unless all numbers in a certain set are prime, which is quite unlikely. If you are unlucky, you can look at some $i$, such that $2\alpha+x_i$ is neither prime not twice a prime and do the same trick. This leads into the area of large prime tuples, see e.g. math.tugraz.at/~elsholtz/WWW/papers/papers13clusteractarith.ps . | |
| Sep 2, 2015 at 1:49 | comment | added | user76479 | Are you sure such small residues exist even though probability is small? Could you give some examples of construction? | |
| Sep 1, 2015 at 10:07 | comment | added | user76479 | What is odds that both $(AB)^{-1}$ and $A^{-1}B$ are both larger than $\log^c\alpha$? | |
| Sep 1, 2015 at 9:27 | history | answered | Jan-Christoph Schlage-Puchta | CC BY-SA 3.0 |