MathLabs

Problem 4

Given a set MM of 19851985 distinct positive integers, none of which has a prime divisor greater than 2323, prove that MM contains four distinct elements whose product is the fourth power of an integer.
Step 1 of 4: Encode each number by nine prime exponents
Previous stepNext step
In plain words

Forget the exact size of each prime exponent and keep only whether it is even or odd: this compresses every integer into one of 512 parity boxes.

2,3,5,7,11,13,17,19,23(9 primes)2,3,5,7,11,13,17,19,23\quad(9\text{ primes})
Detailed analysis

Every element x∈Mx\in M has a unique factorization x=2a13a25a37a411a513a617a719a823a9x=2^{a_1}3^{a_2}5^{a_3}7^{a_4}11^{a_5}13^{a_6}17^{a_7}19^{a_8}23^{a_9}. Record only the parity vector (a1,…,a9)(mod2)(a_1,\dots,a_9)\pmod2. There are 29=5122^9=512 possible vectors.