Number theoryDifficulty 7.2National olympiad, round 2Prove it
Example 3 Let b1,b2,⋯,bm be m non-negative integers, and let (bi1,⋯,bis) denote the greatest common divisor of bi1,⋯,bis, then LCM{b1,b2,⋯,bm}=b1⋯bm(b1,b2)−1⋯(bm−1,bm)−1⋅(b1,b2,b3)⋯(b1,b2,⋯bm)(−1)m+1
where (α1,⋯,αs) is the greatest common divisor of α1,⋯,αs.
Solution
By definition, LCM{b1,b2,⋯bm} is the smallest positive integer that can be divided by b1,⋯,bm. 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,
then the following formula holds: LCM{b1,⋯,bm}=p1a1⋯pnan
where aj=max{aj(1),⋯,aj(m)},j=1,⋯,n
By the result of Example 2, we have aj=i∑aj(i)−i1i2∑min{aj(i1),aj(i2)}+−⋯+(−1)m+1min{aj(1),⋯,aj(m)},j=1,⋯,n
Also, note that (bi1,⋯,bis)=p1c1⋯pncn
where cj=min{aj(ij),⋯,aj(is)},j=1,⋯,n
We can easily see that
This is exactly what we need to prove. p1a1⋯pnan=p1∑ia1(i)⋯pn∑ian(i)⋅p1−∑min{a1(i1)⋅a1(i2)}⋯pn−∑min{an(i1)⋅an(i2)} =(b1⋯bm)⋅(b1,b2)−1⋯(bm−1,bm)−1⋯(b1,b2,⋯,bm)(−1)m+1,
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.