Skip to main content
OlympiadHQ

Browse · MathNet

Print

Cesko-Slovacko-Poljsko

number theory

Problem

The -tuple of positive integers satisfies the following conditions: (i) ; (ii) for any -tuple of positive integers , there exist a positive integer and an -tuple of positive integers such that Prove that and find the number of different -tuples satisfying the given conditions for .
Solution
First we prove the numbers are mutually relatively prime. If this is not true, we have for some . Put , . Set , . By (ii), there exist , , and such that So , which is not possible, since the exponent of in the prime factorization of the right hand side is and the one of the left hand side is not a multiple of .

Assume that are mutually relatively prime. We shall prove that the condition (ii) is fulfilled. Let be any -tuple of positive integers and be all the prime divisors of . We look for in the form For , denote by the exponent of in the prime factorization of . In order for to be an -th power, it suffices to be a multiple of for . So we need fulfilling the congruences The existence of such is guaranteed by Chinese Remainder Theorem (as being mutually relatively prime).

We have proved the condition (ii) is satisfied if and only if the numbers are mutually relatively prime. Among , there are exactly primes. If then among , there must be at least two numbers sharing the same prime number in their prime factorizations, hence not being relatively prime. Therefore we have .

If , then and must be the powers of different primes. We list the powers of primes which can be used: Then the total number of the corresponding -tuples is .
Final answer
n ≤ 16; for n = 16 there are 60 such n-tuples

Techniques

Chinese remainder theoremGreatest common divisors (gcd)Prime numbersPigeonhole principle