Maths Olympiad Prep

Library / /17 of 18

Number theory Difficulty 7.7 National olympiad, round 2 Prove it Argentina

We say that a positive integer NN is *rioplatense* if it satisfies the following two conditions:
* It is possible to find 34 consecutive integers such that their product is divisible by NN but none of them is divisible by NN.
* It is *not* possible to find 30 consecutive integers such that their product is divisible by NN but none of them is divisible by NN.
Find all rioplatense integers.

Solution

Notice N>34N > 34 so that the first condition can hold.

First we will show that NN must be a prime power. Assume the contrary, so NN has two or more distinct prime factors. In this case, we can write N=abN = ab with a,ba, b relatively prime integers greater than 1. By the Chinese Remainder Theorem, there exists an integer xx such that x0(moda)x \equiv 0 \pmod a and x1(modb)x \equiv -1 \pmod b. Thus xx and x+1x+1 are not divisible by NN, but their product is. Now, if we take 30 consecutive integers which include xx and x+1x+1 but none of them is divisible by NN (this can be done because N>30N > 30), we see the second condition is not fulfilled.

So N=pkN = p^k, with pp prime and kk a positive integer. In fact, k2k \ge 2, because a product of integers is divisible by pp if and only if one of the factors is divisible by pp. Hence if k=1k = 1 the first condition will not be fulfilled. Now let us find the possible values for pp.

If p37p \ge 37, in any set of 34 consecutive integers there is at most one of them which is divisible by pp. Therefore, the product of 34 consecutive integers can only be divisible by N=pkN = p^k if one of those integers is divisible by NN, because all factors pp must come from the same number. In conclusion, we need p<37p < 37 in order for the first condition to be plausible.

On the other hand, if p29p \ge 29, we consider the 30 consecutive integers
pk1,pk1+1,,pk1+29. p^{k-1}, p^{k-1} + 1, \dots, p^{k-1} + 29.
Since this list contains at least one more multiple of pp besides pkp^k, the product of these numbers is divisible by N=pkN = p^k. This contradicts the second desired condition unless one of these numbers is divisible by NN. This can only happen if pkpk1+29p^k \le p^{k-1} + 29, or equivalently,
pk1(p1)29.() p^{k-1}(p-1) \le 29. \quad (*)
This rules out p7p \ge 7, as the left hand side of ()(*) would be at least 76=427 \cdot 6 = 42 (recall that kk is at least 2). If p=5p=5, for N>34N > 34 to hold, it must be k3k \ge 3. But in this case, the left hand side of ()(*) is at least 524=100>295^2 \cdot 4 = 100 > 29. If p=3p=3, it must be k4k \ge 4 and the left hand side of ()(*) is at least 332=54>293^3 \cdot 2 = 54 > 29. Finally, if p=2p=2, then k6k \ge 6 and the left hand side of ()(*) is at least 25=32>292^5 = 32 > 29. Having exhausted all cases, we conclude that the required conditions cannot hold if p29p \ge 29.

So we have 29<p<3729 < p < 37, and there is exactly one prime number in this range, which is 31. We will now prove that all numbers of the form 31k31^k, where k2k \ge 2, are solutions. The second condition is satisfied, as we explained previously, because in any set of 30 consecutive integers there is at most one of them which is divisible by 31. For the first one, consider the 34 consecutive integers 31k1,31k1+1,,31k1+3331^{k-1}, 31^{k-1} + 1, \dots, 31^{k-1} + 33. As before, we know that their product is divisible by 31k31^k because there is another multiple of 31 besides 31k131^{k-1} in the set (namely 31k1+3131^{k-1} + 31). To prove that none of these numbers is divisible by 31k31^k, it is enough to check that 31k1+33<31k31^{k-1} + 33 < 31^k. This is equivalent to 31k1(311)>3331^{k-1}(31-1) > 33, which is true for k2k \ge 2.

In conclusion, rioplatense numbers are those of the form 31k31^k for k2k \ge 2.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.