2
$\begingroup$

Given $\mathsf{c\geq1}$, what is the probability that if you choose $\mathsf{A,B,\alpha\in\Bbb N}$ such that $\mathsf{A,B<\alpha<AB}$ holds we will have both $$\mathsf{gcd(A,B)=1}$$$$\mathsf{(AB)^{-1}\bmod\alpha<\log^c\alpha}\mbox{ or }\mathsf{(A^{-1}B)\bmod\alpha<\log^c\alpha}$$ satisfied?

Condition $\mathsf{gcd(A,B)=1}$ has probability $\frac{6}{\pi^2}$ asymptotically.

What is the probability if $\mathsf{A,B<\alpha<AB}$ is not enforced?

$\endgroup$
  • $\begingroup$ You need to specify more about how you choose the three integers before a probability can be determined. $\endgroup$ – Greg Martin Oct 31 '15 at 17:55
1
$\begingroup$

I assume that you choose $(A,\alpha)=(B, \alpha)=1$, for otherwise the inverses don't exist.

As $A, B$ run over all integers $\leq\alpha$ which are coprime to $\alpha$, $(AB)^{-1}$ attains each residues coprime to $\alpha$ with equal frequency. Hence the probability for the event $(AB)^{-1}\bmod\alpha< N$ equals $$ \frac{1}{\varphi(\alpha)}|\{n\leq N:(n, \alpha)=1\} \leq \frac{N\alpha}{\varphi(\alpha)}\ll \frac{N\log\log\alpha}{\alpha}, $$ and similarly for $A^{-1}B\bmod{\alpha}$.

The difference between "two residues chosen at random" and "two residues satisfying $\alpha<AB$" is $\ll\frac{\log\alpha}{\alpha}$. Whether this matters or not depends on the precision you are aiming at.

$\endgroup$
  • $\begingroup$ What is odds that both $(AB)^{-1}$ and $A^{-1}B$ are both larger than $\log^c\alpha$? $\endgroup$ – user76479 Sep 1 '15 at 10:07
  • $\begingroup$ Are you sure such small residues exist even though probability is small? Could you give some examples of construction? $\endgroup$ – user76479 Sep 2 '15 at 1:49
  • 1
    $\begingroup$ 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 . $\endgroup$ – Jan-Christoph Schlage-Puchta Sep 3 '15 at 15:43
  • $\begingroup$ 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$? $\endgroup$ – user76479 Sep 3 '15 at 15:54
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Jan-Christoph Schlage-Puchta Sep 3 '15 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy