1977 IMO Problems/Problem 3
Problem
Let be a given number greater than 2. We consider the set
of all the integers of the form
with
A number
from
is called indecomposable in
if there are not two numbers
and
from
so that
Prove that there exist a number
that can be expressed as the product of elements indecomposable in
in more than one way. (Expressions which differ only in order of the elements of
will be considered the same.)
Solution
Lemma: there are many prime numbers
.
Proof:
Assume that there are only finitely many of them and let their product be .
Then all prime factors of
must be
since this number is coprime with
. But that would mean that
which is impossible for
.
Now we can tackle the problem:
There are only finetely many residue classes , thus we can find two primes
with
and coprime with
.
Let
be the smallest positive integer with
, then the same property holds for
too.
Now we have that
are all indecomposable since all their nontrivial divisors are
. But the product
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 |
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.