E[gcd(p-1,q-1)]
Carl Ellison
cme at ellisun.sw.stratus.com
Mon Oct 11 08:51:32 PDT 1993
I just wrote:
>
> E = sum_i sum_m p_i^{-m}
>
>where p_i is the i-th prime.
That didn't take into account that p and q were knwn to be odd. So,
assuming p and q are randomly chosen odd numbers:
E[gcd(p-1,q-1)] < 2.5 + sum_j 1/(p_j - 1)
where p_j is the j-th odd prime.
It's "<" because this doesn't take into account that there are (relatively
small) values of m such that p_i^m > min(p,q). It also doesn't take into
account the second order probability effects from depeltion of range.
- Carl
More information about the Testlist
mailing list