Counting Restricted Integers

There are $103$ ordered pairs of positive intergers such that $a+b = 104$ .

$gcd(a, b) = gcd(a, a+b) = gcd(b, a+b)$

if $gcd(a, b) = 1 => gcd(a, a+b) = 1 => gcd(a, 104) = 1$ There are $\phi(104)$ numbers $a$ satisfying this condition, where $\phi(n)$ - Euler's function. If we choose some $a$ then $b$ is defined automatically. So there are $\phi(104) = \phi(2^3\times13) = (2^3-2^2)*(13-1) = 48$ pairs.

if $gcd(a, b) = 2 => gcd(a/2, b/2) = 1 => gcd(a/2, (a+b)/2) = 1 => gcd(a/2, 52) = 1$ There are $\phi(52)$ numbers $a/2$ (and $a$ ) sutisfying this condition. So there are $\phi(52) = \phi(2^2\times13) = (2^2-2)*(13-1) = 24$ pairs.

if $gcd(a, b) = 3 =>$ $a$ is divided by $3$ and $b$ is divided by $3 => (a + b)$ is divided by $3 => 104$ is divided by $3$ . Contradiction. Therefore there are not pairs $(a, b)$ such that $gcd(a, b) = 3$ .

The other pairs satisfy the condition.

So answer is equal to $103 - 48 - 24 = \boxed{31}$

Divide equation (2) by $\text{gcd}(a,b)$ to obtain $\frac{104}{\text{gcd}(a,b)}=\frac{a}{\text{gcd}(a,b)}+\frac{b}{\text{gcd}(a,b)}=(\text{integer})+(\text{integer})\Rightarrow \text{gcd}(a,b)|104$ .

The prime factorization of $104$ is $2^313^1$ . However, $\text{gcd}(a,b)>3$ , so it must be $4,8,13,26,$ or $52$ , This means any $\text{gcd}(a,b)$ that is a multiple of $4$ or $13$ will work. Thus the ordered pairs are the multiples of $4$ and $13$ from $1$ to $52$ ; there are precisely $13+4-1=16$ integers, so $2\cdot16-1=\boxed{31}$ ordered pairs.

104=2^3 * 13 As we want GCD > 3 we take all multiples of 4,8,13 and their corresponding pairs.

Therefore multiples of 4 are from 4-100 i.e 25 pairs.((52,52) is a common pair)

Multiples of 13 are 13-91 i.e 6 pairs ((52,52) already taken)

So total pairs=25+6=31

gcd(a,b) will be a factor of 104. thus possible gcds are 4,8,13,26,52.
let gcd = n a/n,b/n are coprime a/n+b/n=104/n.
for n = 4,8,13,26,52 we can count no of coprime nos that add up to 104/n.
{for ex for n=13 we have 104/n = 8 coprime pairs are (1,7) (3,5) (7,1) (5,3)}.
there are 31 such pairs.

{(100,4),(96,8),(92,12),(91,13),(88,16),(84,20),(80,24),(78,26),(72,32),(68,36),(65,39),(60,44),(56,48),(64,40),(76,28)}x2 + (52,52) = 15 x 2 + 1 = 30 + 1 = 31. Answer : 31