Maths Olympiad Prep

Library / /480 of 520

Number theory Difficulty 7.2 National olympiad, round 2 Prove it

Example 3 Let b1,b2,,bmb_{1}, b_{2}, \cdots, b_{m} be mm non-negative integers, and let (bi1,,bis)\left(b_{i_{1}}, \cdots, b_{i_{s}}\right) denote the greatest common divisor of bi1,,bisb_{i 1}, \cdots, b_{i s}, then
LCM{b1,b2,,bm}=b1bm(b1,b2)1(bm1,bm)1(b1,b2,b3)(b1,b2,bm)(1)m+1\begin{array}{c} \operatorname{LCM}\left\{b_{1}, b_{2}, \cdots, b_{m}\right\}=b_{1} \cdots b_{m}\left(b_{1}, b_{2}\right)^{-1} \cdots\left(b_{m-1}, b_{m}\right)^{-1} \\ \cdot\left(b_{1}, b_{2}, b_{3}\right) \cdots\left(b_{1}, b_{2}, \cdots b_{m}\right)^{(-1)^{m+1}} \end{array}

where (α1,,αs)\left(\alpha_{1}, \cdots, \alpha_{s}\right) is the greatest common divisor of α1,,αs\alpha_{1}, \cdots, \alpha_{s}.

Solution

By definition, LCM{b1,b2,bm}\operatorname{LCM}\left\{b_{1}, b_{2}, \cdots b_{m}\right\} is the smallest positive integer that can be divided by b1,,bmb_{1}, \cdots, b_{m}. If we set their factorization as
{b1=p1a1(1)pnan(1),a1(1)0,,an(1)0,bm=p1a1(m)pnan(m),a1(m)0,,an(m)0,\left\{\begin{array}{l} b_{1}=p_{1}^{a_{1}^{(1)}} \cdots \cdots p_{n}^{a_{n}^{(1)}}, a_{1}^{(1)} \geqslant 0, \cdots, a_{n}^{(1)} \geqslant 0, \\ \cdots \cdots \cdots \cdots \\ b_{m}=p_{1}^{a_{1}^{(m)}} \cdots \cdots p_{n}^{a_{n}^{(m)}}, a_{1}^{(m)} \geqslant 0, \cdots, a_{n}^{(m)} \geqslant 0, \end{array}\right.

then the following formula holds:
LCM{b1,,bm}=p1a1pnan\operatorname{LCM}\left\{b_{1}, \cdots, b_{m}\right\}=p_{1}^{a_{1}} \cdots p_{n}^{a_{n}}

where
aj=max{aj(1),,aj(m)},j=1,,na_{j}=\max \left\{a_{j}^{(1)}, \cdots, a_{j}^{(m)}\right\}, j=1, \cdots, n

By the result of Example 2, we have
aj=iaj(i)i1i2min{aj(i1),aj(i2)}++(1)m+1min{aj(1),,aj(m)},j=1,,n\begin{aligned} a_{j}= & \sum_{i} a_{j}^{(i)}-\sum_{i_{1} i_{2}} \min \left\{a_{j}^{\left(i_{1}\right)}, a_{j}^{(i 2)}\right\}+-\cdots \\ & +(-1)^{m+1} \min \left\{a_{j}^{(1)}, \cdots, a_{j}^{(m)}\right\}, j=1, \cdots, n \end{aligned}

Also, note that
(bi1,,bis)=p1c1pncn\left(b_{i_{1}}, \cdots, b_{i_{s}}\right)=p_{1}^{c_{1}} \cdots p_{n}^{c_{n}}

where
cj=min{aj(ij),,aj(is)},j=1,,nc_{j}=\min \left\{a_{j}^{\left(i_{j}\right)}, \cdots, a_{j}^{\left(i_{s}\right)}\right\}, j=1, \cdots, n

We can easily see that

This is exactly what we need to prove.
p1a1pnan=p1ia1(i)pnian(i)p1min{a1(i1)a1(i2)}pnmin{an(i1)an(i2)}\begin{array}{l} p_{1}^{a_{1}} \cdots p_{n}^{a_{n}}=p_{1}^{\sum_{i} a_{1}^{(i)}} \cdots p_{n}^{\sum_{i} a_{n}^{(i)}} \cdot p_{1}^{-\sum \min \left\{a_{1}^{\left(i_{1}\right)} \cdot a_{1}^{\left(i_{2}\right)}\right\}} \cdots p_{n}^{-\sum \min \left\{a_{n}^{\left(i_{1}\right)} \cdot a_{n}^{\left(i_{2}\right)}\right\}} \end{array}
=(b1bm)(b1,b2)1(bm1,bm)1(b1,b2,,bm)(1)m+1,\begin{array}{l} =\left(b_{1} \cdots b_{m}\right) \cdot\left(b_{1}, b_{2}\right)^{-1} \cdots\left(b_{m-1}, b_{m}\right)^{-1} \\ \cdots\left(b_{1}, b_{2}, \cdots, b_{m}\right)^{(-1)^{m+1}}, \end{array}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.