IMC 2006, Day 1, Problem 3
Let be an -matrix with integer entries and be integers satisfying . Prove that there exist -matrices with integer entries such that and for all .
Original from the official PDF

This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
Solution. By induction, it is enough to consider the case . Furthermore, we can multiply with any integral matrix with determinant 1 from the right or from the left, without changing the problem. Hence we can assume to be upper triangular.
Lemma. Let be an integral upper triangular matrix, and let be integers satisfying . Then there exist integral upper triangular matrices such that , , .
Proof. The proof is done by induction on , the case being obvious. Assume the statement is true for . Let , , as in the statement of the lemma. Define to be the greatest common divisor of and , and put . Since divides , divides , which divides . Hence divides . Therefore, and are integers. Define to be the upper-left -submatrix of ; then . By induction we can find the upper-left -part of and in such a way that , and holds on the upper-left -submatrix of . It remains to define and such that also holds for the -th entry for all .
First we check that and are relatively prime for all . Since divides , it is certainly enough to prove that and are relatively prime, i.e.
Transcribed from the official solutions, pages 1–2. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.
How did it go?
Moves you mark come back sooner in triage.