# 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: