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]

See Also

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