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