Olympiad Maths Prep

Library / /53 of 55

Number theory Difficulty 7.3 National olympiad, round 2 Prove it Ukraine

Consider the m×nm \times n table, m,n2m, n \ge 2 (mm rows are enumerated 1,2,,m1, 2, \ldots, m and nn columns are enumerated 1,2,,n1, 2, \ldots, n), which is filled with positive integers. Let bib_i be the lcmlcm (least common multiple) of all numbers in the ithi^{th} row, 1im1 \le i \le m, and let BB be the gcdgcd (greatest common divisor) of numbers (b1,b2,,bm)(b_1, b_2, \ldots, b_m). Also, let cjc_j be the gcdgcd of all numbers in jthj^{th} column, 1jn1 \le j \le n, and let CC be the lcmlcm of numbers (c1,c2,,cn)(c_1, c_2, \ldots, c_n). Is it true that BB is divisible by CC, or is CC divisible by BB?

Solution

Answer: BB is divisible by CC.

Consider any prime number pp, and its power for each number in the table. Replace all the numbers in the table with a power of the chosen prime number. Let the m×nm \times n table is filled with αi,j\alpha_{i,j}, i=1,mi=1, \overline{m}, j=1,nj=1, \overline{n}. Now βi\beta_i is the greatest number from the corresponding row, and BB is the smallest of βi\beta_i. Similarly, γj\gamma_j is the smallest number of the corresponding column, and Γ\Gamma is the greatest of γj\gamma_j. Thus both BB and Γ\Gamma are in the table. If they belong to the same row or column, then BΓB \ge \Gamma by construction. If they are in different rows and columns, find Δ\Delta, which is the number on the intersection of the column of Γ\Gamma and the row of BB. Then by construction ΓΔB\Gamma \le \Delta \le B. Thus, the power of pp in BB is not less than its power in CC. Since pp is arbitrary, CBC|B.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.