Answer to Question #146228 in Combinatorics | Number Theory for ankit

Question

Let us consider two irreducible fractions. The denominator of the first one is equal to 4600,and the denominator of the second to 7900. What is the smallest possible denominator of afraction equal to the sum of these fractions, after the fraction is reduced? (For example, \frac{2}{3} + \frac{8}{15} = \frac{18}{15} = \frac{6}{5}, and the denominator after the reduction is equal to 5.)

Answer 1

Suppose $a,b$ such that $a$ is coprime with 4600, $b$ is coprime with 7900. Now let's find out the possible denominators of $\frac{a}{4600}+\frac{b}{7900}$ :

$\frac{a}{4600}+\frac{b}{7900} = \frac{1}{100}(\frac{a}{46}+\frac{b}{79}) = \frac{1}{100}\frac{79a+46b}{46\times 79}$

What are the possible reductions of this fraction ?

First of all, $79a+46b$ is coprime with $46$ and $79$. Let's prove, for example, that it is coprime with 79 (the case of 46 is completely symmetrical) :

$b$ is coprime with 7900 and thus is coprime by 79, therefore $46*b$ is also coprime with 79 (as 46 and 79 are coprime), but $79a$ is divisible by 79, and therefore their sum is necessarily coprime with 79.

So we can't reduce our fraction by the divisors of 46 or 79. The only possibility is to reduce by divisors of 100 then. The divisors of 100 are of the form $2^a5^b, 0\leq a,b\leq 2$ . We can't reduce by powers of 2, because $79a+46b$ is coprime with 46 and thus is coprime with 2 (2 divides 46). Therefore our best hope is to reduce by powers of 5. We need to find such $a,b$ coprime with respectively 4600, 7900, that $79a+46b$ is divisible by 25. And this is possible due to Bezout's theorem, but if we want the explicit coefficients, we can take $a=1,b=1$ (they are obviously coprime with 4600 and 7900). In this case $79a+46b=125$ and our final fraction is:

$\frac{5}{4\times46\times79}$ , denominator = $4\times46\times79=2^3\times 23 \times 79 = 14536$

and we have already proven that this is the best reduction we can hope for.