China TST 14′ Q3 & USA TSTST 12′ Q3

Suppose f:\mathbb N^+ \to \mathbb N^+ satisfies:

1) \gcd(f(m),f(n))\le \gcd (m,n)^{2014},\forall m,n\in \mathbb N^+

2) n\le f(n)\le n+2014,\forall n \in \mathbb N^+.

Show that \exists \Omega \in \mathbb N^+,f(n)=n, \forall n \ge \Omega.

Let \mathcal B = \{n\in \mathbb N^+ | f(n) \ne n\}.

The 2014 looks DAUNTING. Let’s try a small case with both the 2014‘s replaced with 1.

If \exists n large enough, f(n)=n+1, we will need f(n+1)=n+2 because if f(n+1)=n+1, we will have \gcd(f(n+1),f(n))=\gcd(n+1,n+1)=n+1 > \gcd(n+1,n)=1 which is bad. Therefore we inductively show that all large enough n will have f(n)=n+1. Then we will choose large enough odd n and n+2, and thus f(n)=n+1 and f(n+2)=n+3, which blows up the inequality 1) by \gcd (f(n),f(n+2)) =2 \ge \gcd(n,n+2)=\gcd(n,2)=1

Right. We have a rough idea now: letting infinitely many non-fixed points exist and then we show that there are A LOT of non-fixed points, in which set we can do stuff. Note that the above ‘very large’ only requires n+1 > 1.

Choose \Omega = 2014^{2014} +1. We claim that  \forall n\in \mathcal B, n \le 2014 ^{2014}.

We suppose it is not true, and let q \ge \Omega and q\in \mathcal B, with f(q)=q+c.

We want to control \gcd(f(n),q+c) and \gcd(n,q) at the same time, thus we want to use Chinese Remainder Theorem to get a good residue modulo q and q+c. But CRT requires co-primality of the different modulos that we are putting together, thus \gcd(q,q+c)=\gcd(q,c)=g \le 2014, because 1\le c \le 2014.

Let \displaystyle \frac ng \equiv g \mod \frac qg,

\displaystyle \frac ng \equiv 0 \mod \frac {q+c}{g}. (This can be done now by definition of g.)

We claim that for such n, n \in \mathcal B.

Because if not, \gcd(f(n),f(q))=f(q+c,n)=q+c, and \gcd (n,q)=g. The second equation is true because if g|q, we have \gcd(n,q)=\gcd(n,g)=g. If g \not | q, we then have \displaystyle \gcd (n,g\frac qg)=\gcd (\frac ng,\frac qg)g=\gcd(1,\frac qg)g=g. We thus need g^{2014} \ge q+c which is not true as g^{2014} \le 2014^{2014} and q+c > \Omega > 2014 ^{2014}.

(This is why we defined \Omega to be that number !!!)

Thus we see that there exists an infinite arithmetic progression whose large enough terms are all elements of \mathcal B. We will just write \mathcal A for the arithmetic progression.

We now want to let (a\in \mathcal A) f(a)=a+k have prime factors that we push to infinity, whereas a themselves must not be tainted with those factors. And then we will compare it with other stuff, with the ‘other stuff’ better be coprime with a, with f(\textnormal {other stuff}) having enough common factor with f(a) to blow up the inequality. (Don’t say this word at airport.)

Choose p_{i,j}, where i \in \{1,2, ... , 2014\}, j\in \{0,1,...,2014\} to be a collection of 2014 \times 2015 = 4058210 different primes which are all greater than 2014 and all greater than the common difference in \mathcal A. This can be done as there are infinitely many primes. (Yes, infinitude of primes is a GREAT theorem. It gives you a nice collection of modulos to Chinese Remainder on. And Chinese Remainder theorem is used almost always to only show the existence of a certain desired solution taking the form of an A.P., while not accentuating on the numerial value of the solution.)


\displaystyle \\  \eta \in \mathcal A \\  \\  \eta \equiv -1 \mod p_{1,j}, \forall j, \\  \\  \eta \equiv -2 \mod p_{2,j}, \forall j, \\  \\  ... \\  \\  \eta \equiv -i \mod p_{i,j}, \forall j, \\  \\  ... \\  \\  \eta \equiv -2014 \mod p_{2014, j}, \forall j .

We need to show that this can be done. All we need to show is that all the p_{i,j}‘s are coprime to the common difference of \mathcal A, which is true since we have chosen them to be large enough.

(This step is why we took all the pain to show that elements of \mathcal B not only exist, but exist IN AN ARITHMETIC PROGRESSION, and then we can select the desired subsequence we want from it by Chinese Remaindering the arithmetic progression with other prime modulos. Only assuming that \mathcal B has infinitely many elements restricts what we can do on it.)

Note that what we are doing now DEVIATES from what we did with the simple case, because now it is rather difficult to control over what happens to f(\eta) as now we only have f(\eta) \ne \eta instead of what it actually is. Thus I wish to restrict all the values of f(\eta) and then compare it with OTHER positive integer’s function values instead of integers in the arithmetic progression that defined \eta.

Fix the \eta, and suppose f(\eta) = \eta +c, where 1\le c \le 2014.

Now let

\displaystyle \sigma \equiv - j \mod p_{c,j} for each p_{c,j}, 0\le j \le 2014.

and \sigma \equiv 1 \mod \eta.

Again, we need to show that this can be done, and it suffices to check that \gcd (\eta, p_{c,j})=1, \forall p_{c,j}. Assume this is not true, and p_{c,\rho} | \eta. Recall that \eta + c \equiv 0 \mod p_{c,\rho}, \implies \gcd(\eta, \eta+c) =\gcd(\eta, c) \ge p_{c, \rho}.

The above inequality is impossible due to the fact that p_{c,\rho} > 2014 \ge c >0. Thus the Chinese Remainder construction of \sigma is indeed possible. (Note that the c>0 requires the full power of \eta \in \mathcal B.)

OMG SO MANY CHINESE REMAINDERS… We use it to control the remainders of the variables dividing each other so as to manipulate the gcd’s.

Finally, we have an \eta \in \mathcal B with all its possible function values being star-crossed, and a \sigma, not necessarily in \mathcal B, with all its function values holding such an enmity with function values of \eta. This will blow up the inequality.

Substitute \eta and \sigma into the inequality, \implies \gcd(f(\eta),f(\sigma)) \le \gcd (\eta, \sigma)^{2014}. The RHS =1 as \sigma \equiv 1 \mod \eta. The LHS = \gcd (\eta +c, \sigma + k), where 0 \le k \le 2014, and since p_{c,k} | \eta+c, p_{c,k} | \sigma + k, LHS \ge p_{c,k} >1. Contradiction.

Comment: while the idea is easy, it takes great care to babysit all the details in the Chinese Remainder Constructions, as one easily runs into modulos not being coprime or remainder actually \equiv 0 which must be evaded if we wish to estimate the gcd. All the first half is done to generate an A.P. of \mathcal B‘s elements. I admit it can be annoying to see such problem posed in an exam, but we now see that all the crazy and daunting 2014‘s are indeed red herrings (its status of red herring should be apparent on first glance), the factor that really matters here is the FINITENESS of all the indices, for which a Chinese Remainder will always work because we only need finitely many congruence equations to hold simultaneously–and we can use A LOT of difference congruence equations to make our life easy as there’s not taxation on considering  many congruence equations at the same time.


Suppose f:\mathbb N^+ \to \mathbb N^+ satisfies:

1) \gcd(f(m),f(n))=1 if and only if \gcd (m,n)=1

2) n\le f(n) \le n+2012.

Show that \forall n\in \mathbb N^+, \forall p prime, p|f(n) implies p|n.

This problem seems to be the precursor of the one in 2014, and is left to the reader as an exercise.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s