1977 IMO Problems/Problem 3

Problem

Let $n$ be a given number greater than 2. We consider the set $V_n$ of all the integers of the form $1 + kn$ with $k = 1, 2, \ldots$ A number $m$ from $V_n$ is called indecomposable in $V_n$ if there are not two numbers $p$ and $q$ from $V_n$ so that $m = pq.$ Prove that there exist a number $r \in V_n$ that can be expressed as the product of elements indecomposable in $V_n$ in more than one way. (Expressions which differ only in order of the elements of $V_n$ will be considered the same.)

Solution

Lemma: there are $\infty$ many prime numbers $p \not\equiv 1 \mod n$ .

Proof:

Assume that there are only finitely many of them and let their product be $k$ . Then all prime factors of $nk - 1$ must be $\equiv 1 \mod n$ since this number is coprime with $k$ . But that would mean that $- 1 \equiv nk - 1 \equiv 1 \mod n$ which is impossible for $n > 2$ .

Now we can tackle the problem: There are only finetely many residue classes $\mod n$ , thus we can find two primes $p,q$ with $p \equiv q \not\equiv 1 \mod n$ and coprime with $n$ . Let $s$ be the smallest positive integer with $p^s \equiv 1 \mod n$ , then the same property holds for $q$ too. Now we have that $p^s, q^s, pq^{s - 1} , p^{s - 1}q \equiv 1 \mod n$ are all indecomposable since all their nontrivial divisors are $\not\equiv 1 \mod n$ . But the product $p^sq^s = (pq^{s - 1})(p^{s - 1}q)$ gives a number that is represented in two ways.

The above solution was posted and copyrighted by ZetaX. The original thread for this problem can be found here: [1]

The lemma is incorrect. A simple example: k=5, n=3, 2 is a prime factor of nk-1=14 but 2≡2 (not 1) mod n. Following is my approach. We build r=abcd, ab≡cd≡ac≡bd≡1 mod n, ab,cd,ac,bd are indecomposable, a≠d, b≠c. Then r=ab•cd=ac•bd satisfies the requirement. Let a,b,c,d all be written in the form of kn-1, so that their pairwise products≡1 mod n. We set the values of elements as small as possible to maximize the chance of being indecomposable. So we set a=b=n-1, c=d=2n-1. ab=(n-1)^2<(n+1)(2n+1), therefore indecomposable; ac,bd=(n-1)(2n-1)<(n+1)(2n+1), therefore indecomposable; cd=(2n-1)^2, if it’s decomposable, its factors must include n+1, because the only element in V(n) smaller than 2n-1 is n+1. Then n+1 | 4n^2-4n+1=4n(n+1)-8n+1, n+1 | 8n-1=8(n+1)-9, therefore n+1 | 9, n+1=1,3,9, since n>=3, n=8, meaning if n≠8, (2n-1)^2 is indecomposable; If n≠8, set a=b=n-1, c=d=2n-1, r=ab•cd=ac•bd, ab=(n-2)n+1, ac,bd=(2n-3)n+1, cd=(n-4)n+1, all conforming to the form of kn+1; As aforementioned, (n-1)^2, (n-1)(2n-1), (2n-1)^2 are now all indecomposable, and obviously (n-1)^2≠(n-1)(2n-1), valid; If n=8, we can take a=b=n-1=7, c=d=3n-1=23, r=49•529=161•161=25921, the first few elements are: n+1=9, 2n+1=17, 3n+1=25, and the only prime factors of 49,161,529 are 7 and 23, therefore they are indecomposable, valid. Proof completed.

1977 IMO (Problems) • Resources
Preceded by Problem 2	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 4
All IMO Problems and Solutions

Page

Toolbox

Search

1977 IMO Problems/Problem 3

Problem

Solution

See Also