IMO 1977 · Problem 3

Let \(n\) be a given integer \(>2\), and let \(V_n\) be the set of integers \(1+kn\), where \(k=1,2,\ldots\). A number \(m\in V_n\) is called indecomposable in \(V_n\) if there do not exist numbers \(p,q\in V_n\) such that \(pq=m\). Prove that there exists a number \(r\in V_n\) that can be expressed as the product of elements indecomposable in \(V_n\) in more than one way. (Products which differ only in the order of their factors will be considered the same.)

Official text of the problem. Official problem paper (PDF)

Solution

We first prove that there are infinitely many primes which are coprime to \(n\) and are not congruent to \(1\) modulo \(n\).

Suppose instead that all such primes form a finite list \(p_1,\ldots,p_s\). Put \[ P=p_1\cdots p_s,\qquad N=nP-1, \] taking \(P=1\) if the list is empty. Since \(n>2\), we have \(N>1\). Every prime divisor of \(N\) is coprime to \(n\), and none is among \(p_1,\ldots,p_s\), because \(N\equiv-1\pmod{p_i}\). Consequently, every prime divisor of \(N\) is congruent to \(1\) modulo \(n\). Multiplying these prime factors, with their multiplicities, gives \[ N\equiv1\pmod n. \] But \(N\equiv-1\pmod n\), which is impossible for \(n>2\). This proves the assertion.

There are only finitely many residue classes modulo \(n\). Thus we can choose distinct primes \(p,q\), both coprime to \(n\), such that \[ p\equiv q\equiv a\pmod n,\qquad a\not\equiv1\pmod n. \] Let \(h\) be the least positive integer for which \(a^h\equiv1\pmod n\). Such an integer exists: two powers of \(a\) have the same residue modulo \(n\), and cancellation is possible because \(\gcd(a,n)=1\). Moreover, \(h\ge2\).

We claim that each of the numbers \[ m_i=p^i q^{h-i}\qquad(0\le i\le h) \] is indecomposable in \(V_n\). First, \(m_i>1\) and \[ m_i\equiv a^h\equiv1\pmod n, \] so \(m_i\in V_n\). Any divisor \(d\) of \(m_i\) with \(1<d<m_i\) has the form \(p^u q^v\), where \[ 0\le u\le i,\qquad 0\le v\le h-i,\qquad 1\le u+v<h. \] Hence \[ d\equiv a^{u+v}\not\equiv1\pmod n \] by the minimality of \(h\). Thus no proper divisor of \(m_i\) greater than \(1\) belongs to \(V_n\), proving the claim.

Now take \(r=p^h q^h\). It belongs to \(V_n\) and has the two factorizations \[ r=(p^h)(q^h) =(p^{h-1}q)(pq^{h-1}). \] All four displayed factors are among the \(m_i\), so they are indecomposable in \(V_n\). Since \(h\ge2\), both factors in the second factorization are divisible by both \(p\) and \(q\), whereas each factor in the first is a power of just one of these distinct primes. Therefore the factorizations are different even when order is disregarded. This also covers \(h=2\), when the second factorization has two equal factors. \(\square\)

The solution was checked against John Scholes' IMO solution archive (Kalva).