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.)
Problem
Source: IMO LongList, Netherlands 1, IMO 1977, Day 1, Problem 3
Tags: number theory, prime numbers, prime factorization, Dirichlet s Theorem, IMO, IMO 1977
27.12.2005 13:59
Nice Lemma: there are $ \infty$ many prime numbers $ p \not\equiv 1 \mod n$. Proof: Assume that there are only finetely 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.
27.10.2018 17:33
Similar to above but there are a little difference.By Dirichlet's theorem there are infinity many primes congurent to $-1$ modulo $n$ take two of them like $p,q$ then $(pq)(pq)=(p^2)(q^2)=p^2q^2 \in V_n$ obviously $pq,p^2,q^2$ are indecomposable in $V_n$ so we are done.
09.07.2021 20:26
hello!
this observation helps in the second part(which I proved similarly like @above
09.07.2021 20:26
aakhri2205 wrote: hello!
this observation helps in the second part(which I proved similarly like @above is there some technical error in the obs pls reply