Explaining solution of Project Euler problem #5

Question

Here is the problem. Pretty simple to brute force, but more gently solutions are not that easy to understand, and I'm not talking about programming issue, but math-affiliated.
For example, I'm struggling with this, more precisely:

ans *= i // eulerlib.gcd(i, ans)

Where // is floor division in Python, and eulerlib.gcd(i, ans) - greatest common divisor of numbers i and ans.
It works - but why? Can someone explain why the output is product of all numbers from 1 to 20, divided by gcd of particular number and current 'answer'?

Answer 1

Let $a_i$ be the smallest positive integer that is divisible by all the numbers $1, \ldots, i$, i.e. $a_i = \operatorname{lcm}(1, \ldots, i)$. Basic properties of the least common multiple show

$$a_i = \operatorname{lcm}(1, \ldots, i) = \operatorname{lcm}(\operatorname{lcm}(1, \ldots, i - 1), i) = \operatorname{lcm}(a_{i - 1}, i) = \frac{a_{i - 1} i}{\gcd(a_{i - 1}, i)}.$$

The two identities $\operatorname{lcm}(a_1, \ldots, a_i) = \operatorname{lcm}(\operatorname{lcm}(a_1, \ldots, a_{i - 1}), a_i)$ and $\operatorname{lcm}(a, b) \gcd(a, b) = ab$ can easily be seen from considering the prime factorization of the occuring integers.

Answer 2

You want to find the smallest number $n$ that each of the numbers $1,2,\ldots,20$ divide. This number $n$ is called the least common multiple of $1,2,\ldots,20$, and you denote it by

$$n=\text{lcm}(1,2,\ldots,20).$$

There is a connection between $\text{lcm}$ and $\text{gcd}$ as follows:

$$\frac{1\cdot 2\cdots 19\cdot20}{\text{gcd}(1,2,\ldots,20)} = \text{lcm}(1,2,\ldots,20).$$

In order to solve your problem, it is thus enough to find the left hand side of this identity, and this is exactly what the solution does, only iteratively.