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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ What is odds that both $(AB)^{-1}$ and $A^{-1}B$ are both larger than $\log^c\alpha$? $\endgroup$
    – user76479
    Commented Sep 1, 2015 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
    Commented Sep 2, 2015 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
    Commented Sep 3, 2015 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
    Commented Sep 3, 2015 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
    Commented Sep 3, 2015 at 16:01

You must log in to answer this question.