# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* jeevanjyot

*nishant403, satyam_343*

**Testers:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

None

# PROBLEM:

You are given integers A and B. Find the smallest possible value of \text{lcm}(A, X) - \gcd(B, X) across all positive integers X.

# EXPLANATION:

The answer is probably guessable by looking at the sample tests and/or working out a few small examples.

## Short answer

The answer is simply

## Long answer

Iâ€™ll focus a bit on how one can derive this without guessing.

Our expression is \text{lcm}(A, X) - \gcd(B, X).

In particular, the first part of that expression is always a multiple of A.

Letâ€™s fix the value of this lcm: suppose we choose X such that \text{lcm}(A, X) = k\cdot A.

Notice that this means that X is a factor of k\cdot A.

Our objective is now to *maximize* \gcd(B, X), since thatâ€™s what would make the difference as small as possible.

For \gcd(B, X) to be as large as possible, X should contain as many prime factors in common with B as possible.

Along with the constraint that X is a factor of k\cdot A, this tells us that the best choice of X is k\cdot A itself; choosing a strict factor isnâ€™t going to help us increase the gcd.

Ok, so now we have k\cdot A - \gcd(B, k\cdot A).

What value of k minimizes this?

Intuitively, k = 1 seems good; after all, the second part is a factor of B so will always be \leq B no matter how large k is; while the first part keeps increasing without bound.

k = 1 gives us A - \gcd(A, B), which if you notice is the expression given in the â€śshort answerâ€ť above.

Letâ€™s try to prove that this is optimal.

## Proof

First, notice that for any k\geq 1, we have \gcd(B, k\cdot A) \leq \gcd(k\cdot B, k\cdot A); since k\cdot B is a multiple of B.

But itâ€™s also true that \gcd(k\cdot B, k\cdot A) = k\cdot\gcd(A, B).

So, we have \gcd(B, k\cdot A) \leq k\cdot \gcd(A, B).

This means that

which is exactly what we set out to prove!

All that remains is computing the answer quickly, which requires us to compute \gcd(A, B) quickly.

This can be done in \mathcal{O}(\log\min(A, B)) using the Euclidean algorithm.

# TIME COMPLEXITY:

\mathcal{O}(\log\min(A, B)) per testcase.

# CODE:

## Code (Python)

```
from math import gcd
for _ in range(int(input())):
a, b = map(int, input().split())
print(a - gcd(a, b))
```