Olympiad Maths Prep

Library / /7 of 14

Number theory Difficulty 6.3 National olympiad Prove it Czech Republic

A number nn is a product of three (not necessarily distinct) prime numbers. Adding 1 to each of them, after multiplication we get a larger product n+963n + 963. Determine the original product nn. (Pavel Novotný)

Solution

We look for n=pqrn = p \cdot q \cdot r, with primes pqrp \le q \le r satisfying
(p+1)(q+1)(r+1)=pqr+963.(1)(p+1)(q+1)(r+1) = pqr + 963. \quad (1)
If p=2p=2, the right-hand side of (1) is odd, hence the factors q+1,r+1q+1, r+1 on the left must be odd too. This implies that p=q=r=2p=q=r=2, which contradicts to (1). Thus we have proved that p3p \ge 3.
Now we will show that p=3p=3. Suppose on the contrary that 3<pqr3 < p \le q \le r. Then the right-hand side of (1) is not divisible by 33. The same must be true for the product (p+1)(q+1)(r+1)(p+1)(q+1)(r+1). Consequently, all the primes p,q,rp, q, r are congruent to 11 modulo 33, and hence (p+1)(q+1)(r+1)pqr(p+1)(q+1)(r+1) - pqr is congruent to 222111=72 \cdot 2 \cdot 2 - 1 \cdot 1 \cdot 1 = 7, which contradicts to (p+1)(q+1)(r+1)pqr=963(p+1)(q+1)(r+1) - pqr = 963. Therefore, the equality p=3p=3 is established.
Putting p=3p=3 into (1) we get 4(q+1)(r+1)=3qr+9634(q+1)(r+1) = 3qr + 963, which can be rewritten as (q+4)(r+4)=975(q+4)(r+4) = 975. In view of the prime factorization 975=35213975 = 3 \cdot 5^2 \cdot 13 and inequalities 7q+4r+47 \le q+4 \le r+4, we conclude that q+4975<32q+4 \le \sqrt{975} < 32 and hence q+4{13,15,25}q+4 \in \{13, 15, 25\}. Since qq is a prime, it holds that q=11q=11. Then r+4=65r+4=65, and hence r=61r=61 (which is a prime indeed). Consequently, the problem has a unique solution
n=31161=2013. n = 3 \cdot 11 \cdot 61 = 2013.

Looking for a route rather than 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.