Maths Olympiad Prep

Library / /105 of 520

Number theory Difficulty 6.5 National olympiad Find the answer

Baron Munсhausen discovered the following theorem: "For any positive integers aa and bb there exists a positive integer nn such that anan is a perfect square, while bnbn is a perfect cube". Determine if the statement of Baron’s theorem is correct.

Solution

To determine if Baron Munchausen's theorem is correct, we need to show that for any positive integers aa and bb, there exists a positive integer nn such that anan is a perfect square and bnbn is a perfect cube.

1. Prime Factorization:
Let aa and bb be expressed in their prime factorizations:
a=p1x1p2x2pkxk a = p_1^{x_1} p_2^{x_2} \ldots p_k^{x_k}
b=p1y1p2y2pkyk b = p_1^{y_1} p_2^{y_2} \ldots p_k^{y_k}
where xi,yi0x_i, y_i \geq 0 for all ii.

2. **Form of nn**:
Assume nn can be written as:
n=p1z1p2z2pkzk n = p_1^{z_1} p_2^{z_2} \ldots p_k^{z_k}
where zi0z_i \geq 0 for all ii.

3. **Conditions for anan to be a Perfect Square**:
For anan to be a perfect square, the exponent of each prime in its factorization must be even. Therefore, we need:
xi+zi0(mod2)for all i x_i + z_i \equiv 0 \pmod{2} \quad \text{for all } i

4. **Conditions for bnbn to be a Perfect Cube**:
For bnbn to be a perfect cube, the exponent of each prime in its factorization must be divisible by 3. Therefore, we need:
yi+zi0(mod3)for all i y_i + z_i \equiv 0 \pmod{3} \quad \text{for all } i

5. Chinese Remainder Theorem:
We need to find ziz_i such that both conditions are satisfied simultaneously. This can be formulated as a system of congruences:
zixi(mod2) z_i \equiv -x_i \pmod{2}
ziyi(mod3) z_i \equiv -y_i \pmod{3}

By the Chinese Remainder Theorem, since 2 and 3 are coprime, there exists a unique solution modulo 6 for each ziz_i. Therefore, there exists ziz_i such that:
zixi(mod2) z_i \equiv -x_i \pmod{2}
ziyi(mod3) z_i \equiv -y_i \pmod{3}

6. Conclusion:
Since we can find such ziz_i for each prime factor, we can construct nn such that anan is a perfect square and bnbn is a perfect cube.

\blacksquare

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.