USA TSTST 2012/3

[Phlembac Adib Hasan]

A function $f:\mathbb N\to \mathbb N$ satisfies:
1. $\gcd (m,n) =1 \Longrightarrow \gcd (f(m),f(n))=1$
2. $n\leq f(n) \leq n+2012$
Prove, for every prime $p$, $p|f(n)\Longrightarrow p|n$

Remark: $2012$ can be replaced by any nonnegative integer constant.

[Fm Jakaria]

I solve the problem for a fixed general nonnegative integer $ c$.

My solution: For $c = 0; f(n) = n$ for all $n$; so done. Assume $c > 0$.

One thing is obvious, $f(n) > 1$ for all $n > 1$.

Definitions:
Call a finite nonempty sequence $A$ of positive integers ‘discrete’ if it contains no repeatetion of terms. Any discrete sequence has length $|A|$.
For any positive integer $n > 1$, call a discrete sequence $A$ to be ‘$n$-good’ if it’s terms are in the interval $(1,n]$ and are pairwise coprime[it may have a single term only].
Call a n-good sequence ‘primary $n$-good’ if all of it’s terms are primes. If the sequence $A,B$ are respectively $n$-good and primary $n$-good of same length; and any term of $A$ is divisible by the respective term in $B$; we’ll say $A$ dominates $B$.
If of all $n$-good sequences, $S$ has maximum possible length; call $S$ ‘maximum $n$-good’. Similiarly, if of all primary $n$-good sequences, $S$ has maximum possible length; call $S$ ‘maximum primary $n$-good’.

For any integer $m > 1$, let $A(m)$ be the set of distinct prime divisors of $m$. Let $P(m)$ be the sequence of primes $\leqslant m$.

Criterion 1: Let $a_1,…,a_k$ be a $n$-good sequence $A$. Then any element of the Cartesian product $C(A)$ of $A(a_1),….,A(a_k)$ gives a primary $n$-good sequence dominated by $A$.

Criterion 2: A maximum primary $n$-good sequence has length $\pi(n)$. The only such sequences are $P(n)$ with permuted terms.

Lemma 1: A maximum $n$-good sequence have length $\pi(n)$.
Proof: An example of a $n$-good sequence with length $\pi(n)$ is $P(n)$.
Now consider any $n$-good sequence $S$. Consider any element $T$ in $C(S)$. So by criterion 1 and 2, $|S| = |T| \leqslant \pi(n)$.

Lemma 2: A maximum $n$- good sequence $S$ contains perfect positive powers of $|S|$ distinct primes which constitute the set $P(n)$.
Proof: Consider any sequence $T$ dominated by $S$. Then $|T| = |S| = \pi(n)$; so by the second criterion, $T$ coincides with $P(n)$, after suitably permuted: of course there can be at most one permutation since $S$ is $n$-good. So we note any term $s_i$ of $S$ can have at most one prime divisor, since $T$ was arbitrary.

Lemma 3: There exists arbitrary large positive integers $x$ such that the interval $(x,x+c]$ contains no primes.
Proof: For any positive integer $n > c + 2$, we may set $x = n! + 1$.

Lemma 4: For all primes $p$; $f(p)$ is a positive perfect power of $g(p)$; for some bijective function $g: P \rightarrow P$.
Proof: We show that there exists sufficiently large positive integers $z$ such that exists a bijective function $h : P(z) \rightarrow P(z)$ such that for all $p$ in $P(z)$, $f(p)$ is a perfect positive power of $h(p)$. Then the lemma is proved.
By lemma 3; we may choose sufficiently large positive integers $z > 1$ such that $\pi(z + c) = \pi(z)$. We show that any such $z$ works.
For any $z$-good sequence $S$ consisting of terms $a_1,a_2,….,a_n$; let us define the sequence with terms $f(a_1),f(a_2),…..,f(a_n)$ to be $f(S)$.
By the given conditions; for any $z$-good sequence $S$, $f(S)$ is a $(z+c)$-good sequence.
Suppose we choose $S$ to be maximum $z$-good. Then $|f(S)| = |S| = \pi(z) = \pi(z+c)$. So $f(S)$ is maximum $(z+c)$-good. In particular; taking $S$ to be $P(z)$; and using lemma 2; we note that terms of $f(S)$ are perfect positive powers of distinct primes which exactly constitute the set $P(z+c) = P(z)$.

Lemma 5: Suppose $p$ is a prime divisor of $f(m)$, for a positive integer $m$. Then there exists a prime $q$ dividing $m$ such that $g(q) = p$.
Proof: Suppose $g(r) = p$ for $r$ prime. Then $f(r)$ and $f(m)$ are not coprime. So $r$ divides $m$.

Lemma 6: For all primes $p$; $g(p) = p$.
Proof: Suppose the converse: for some prime $p$, this do not hold. Let $g(r) = p$ with $r$ prime, $r \neq p$.
We choose $c$ distinct primes $s_1,….,s_c$ such that the following inequalities hold: for all integers $i$ in $[1,c)$;
$s_{i+1},g(s_{i+1}) > s_i + g(s_i)$; and $s_1, g(s_1) > c + p + r$. This choice is possible as $g$ is bijective.
We set $r_i = g(s_i)$. Using the Chinese remainder theorem, we may choose an integer $k > 1$ such that the three conditions hold.:
1. For all integers $i$ in $[1,c]; k \equiv –i(mod r_i)$.
2. For all integers $i$ in $[1,c]$ such that $r_i \neq s_i; k \equiv 1(mod s_i)$.
3. $k \equiv 0(mod p); k \equiv 1(mod r)$.
We consider two cases:
Case-1: $f(k) = k$. Now $p | f(k)$; as $g$ is bijective, lemma 5 gives that $r$ divides $k$; a contradiction.
Case-2: $f(k) = k + j$ for some integer $ j$ in $[1,c]$. Now $r_j | f(k)$, gives $s_j$ divides $k$. The last is impossible unless $r_j = s_j$, by congruence condition 2. But now congruence condition 1 gives that $r_j | j$; which is impossible as $r_j > c$.

Now in the main proof, fix arbitrary positive integer $m$; and let a prime $p$ divides $f(m)$. As $g(p) = p$; $f(p)$ and $f(m)$ are not coprime; so $p | m.$.