Maximum GCD Among Pairs of Random Integers

Details Maximum GCD Among Pairs of Random Integers Maximum GCD Among Pairs of Random Integers

2009-11-13

arxiv.org/abs/0911.2660v1

Mathematics

Number Theory

11 pages

Scientific paper

Fix $\alpha >0$, and sample $N$ integers uniformly at random from $\{1,2,\ldots ,\lfloor e^{\alpha N}\rfloor \}$. Given $\eta >0$, the probability that the maximum of the pairwise GCDs lies between $N^{2-\eta }$ and $N^{2+\eta}$ converges to 1 as $N\to \infty $. More precise estimates are obtained. This is a Birthday Problem: two of the random integers are likely to share some prime factor of order $N^2/\log [N]$. The proof generalizes to any arithmetical semigroup where a suitable form of the Prime Number Theorem is valid.

Affiliated with

Also associated with

No associations

Rating

Maximum GCD Among Pairs of Random Integers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Maximum GCD Among Pairs of Random Integers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximum GCD Among Pairs of Random Integers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-113160