Divisible by Every Common Divisor of $a$ and $b$

It is easier to count for how many of the $\binom{100}{2} = 4950$ pairs $(a,b)$ the condition is not met.

Let $d$ be the greatest common divisor, then $a = xd$ , $b = yd$ , and there should not exist an $m$ such that $m = nd$ . But this means that there is no integer between $x$ and $y$ ; therefore $y = x + 1$ .

For any given value of $d$ there are $\lfloor 100/d \rfloor$ positive integers less than or equal to 100, and therefore $N(d) = \lfloor 100/d \rfloor - 1$ of the pairs $(x,y)$ . Thus we count:

$\begin{array}{ccc} d & N(d) & \text{pairs} \\ \hline 1 & 99 & 99 \\ 2 & 49 & 49 \\ 3 & 32 & 32 \\ 4 & 24 & 24 \\ 5 & 19 & 19 \\ 6 & 15 & 15 \\ 7 & 13 & 13 \\ 8 & 11 & 11 \\ 9 & 10 & 10 \\ 10 & 9 & 9 \\ 11 & 8 & 8 \\ 12 & 7 & 7 \\ 13-14 & 6 & 12 \\ 15-16 & 5 & 10 \\ 17-20 & 4 & 16 \\ 21-25 & 3 & 15 \\ 26-33 & 2 & 16 \\ 34-50 & 1 & 17 \\ \hline \text{total} & & 382 \end{array}$

Thus the solution is $4950 - 382 = \boxed{4568}$ .

I've written a Python 3 program to solve this for us:

1
2
3
4
5
6
7
8

divisors = lambda n: [x for x in range(1, n + 1) if n % x == 0]
s = 0
for i in range(1,101):
    for j in range(1, 101):
        if i < j:
            comdiv = {*divisors(i)} & {*divisors(j)}
            s += any(m for m in range(i + 1, j) if all(m % div == 0  for div in comdiv))
print(s)

This will yield the correct result, 4568 .

This is equivalent to pairs $1<=a<b<=100$ such that $b-a \neq gcd(a,b)$

My python solution

1
2
3
4
5
6
7

from fractions import gcd
count = 0
for a in range(1,100):
  for b in range(a+1,101):
    if (b-a)!=gcd(a,b):
      count += 1
print(count)

here is a matlab code to solve the problem

X = [] ;
for a = 1:99
    for b = (a+1):100
        for m = (a+1):(b-1)
            if mod(m,gcd(a,b)) == 0
                X = [X; a b] ;
                break
            end
        end
    end
end
k = size(X,1)

Of course it returns the same $k = 4568$ that everyone else mention :)

The matrix $X$ saves all the valid pairs.

In the programming package $Mathematica$ the solution is obtained by means of a simple program. i.e.

k = 1; Do[

            Do[

                  If[Mod[m, GCD[a, b]] == 0, k++ && Goto[end]], 

            {m, a + 1, b - 1}]; 

             Label[end], 

     {a, 1, 98}, {b, 3, 100}]; Print["k = ", k - 1]