ABCD Probability problem:   

Given k | ab-cd for integers a,b,c,d,k what is the probability that k | a-c ?

We'll call the ABCD probability function P(k)

Background: Sometime in late 1999 I noticed that if k | ab-cd, you have an increased chance of k | a-c. With some quick hand calculations I had crudely estimated it to be 1/(k-1) but have since taken another look.

Info: For the special case of k=2x, you will find the probability is exactly:

P(2x) = (x+2) / (3*2x-1).

You could use this measure to approximate the probability in all cases using the formula:
P(k) approximately equals (2+log2k)/(3k-1).

For the special case of k=3x, you will find the probability is exactly:

P(3x) = (2x+3) / (4*3x-1)

Extrapolating along these lines with empirical data you will find where k=zx, with z prime:
P(zx) = ((z-1)x+z) / (z+1)*zx-1)

Now, analyzing k=3*2x you find the formula:

P(3*2x) = (5/11) * (x+2) / (3*2x-1)

And notice that:
P(3*2x) = P(3) * P(2x)

P(k) looks multiplicative! It turns out this is true. That is P(xy) = P(x)*P(y) . A general solution is now at hand...

Resulting method for finding solution:
Step 1 - Break k into prime factors q0e0, q1e1, q2e2, etc.
Step 2 - For each prime factor and its exponent, calculate P(qe) using the formula:

P(qe) = ((q-1)e+q) / (q+1)*qe-1)

Step 3 - P(k) is the product of P(q0e0), P(q1e1), P(q2e2), ...
For prime k, this simplifies to just:
P(k) = (2k-1) / (k*(k+1)-1)

Proving these results (like any other probability question) is only a matter of effective counting. Henry Shin (aka 'Paint'), an online pal from the mIRC #math channel, wrote up a sketch of a proof for prime k along with a sample program.
Additional Notes:
  • P(k) equivalent to probability k|a+c where k|ab-cd
  • P(k) equivalent to probability k|a+c where k|ab+cd
  • P(k) equivalent to probability k|a-c where k|ab+cd
    Joe K. Crump | Number Theory Home
    •