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]

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