Maths Olympiad Prep

Library / /3 of 65

Number theory Difficulty 4.7 AIME Prove it Romania

Let n5n \ge 5 be an integer. Prove that nn is prime if and only if for any representation of nn as a sum of four positive integers n=a+b+c+dn = a+b+c+d, it is true that abcdab \ne cd.

Solution

The statement of the problem is equivalent to saying that an integer n5n \ge 5 is composite if and only if there exists a representation of nn as the sum of four positive integers such that ab=cdab = cd.

(\Leftrightarrow) If ab=cdab = cd and n=a+b+c+dn = a+b+c+d, then
an=a2+ab+ac+ad=a2+cd+ac+ad=(a+c)(a+d),() an = a^2 + ab + ac + ad = a^2 + cd + ac + ad = (a+c)(a+d), (*)
hence n(a+c)(a+d)n \mid (a+c)(a+d).

(\Rightarrow) If n=pqn = pq, with p,q2p, q \ge 2, is a composite number, we can choose a=1a = 1, b=(p1)(q1)b = (p-1)(q-1), c=p1c = p-1, d=q1d = q-1. This choice can easily be guessed by writing ()(*) with a=1a = 1.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.