Maths Olympiad Prep

Library / /283 of 299

Number theory Difficulty 7.6 National Olympiad, round 2 Prove it Iran

Let aa, bb, cc, dd be pair-wise coprime positive integers not all equal to 11. Let f,g:N{0,1}f, g: \mathbb{N} \to \{0, 1\} be two multiplicative functions such that for all positive integers nn, f(an+b)=g(cn+d)f(an + b) = g(cn + d). Prove that at least one of these two claims are true:

i. f(an+b)=g(cn+d)=0f(an + b) = g(cn + d) = 0, for all positive integers nn.

ii. There is a positive integer DD such that for all positive integers nn with gcd(n,D)=1\text{gcd}(n, D) = 1, we have f(n)=g(n)=1f(n) = g(n) = 1.

(We call a function h:NRh: \mathbb{N} \to \mathbb{R} multiplicative if h(mn)=h(m)h(n)h(mn) = h(m)h(n) for all positive integers mm, nn.)

Solution

Assume that the first claim is false, we then prove the truth of the second claim. Letting n=p1α1ptαtn = p_1^{\alpha_1} \dots p_t^{\alpha_t} it follows that f(n)=f(p1)f(pt)f(n) = f(p_1) \dots f(p_t). Thus, the value of ff is only depending upon the values of ff at prime points. Hence, it suffices to prove that for all large enough pp, f(p)=1f(p) = 1. Let us define the set AA as follows:
A={an+b:f(an+b)=1,nN} A = \{an + b : f(an + b) = 1, n \in \mathbb{N}\}
The first criterion ensures that AA is nonempty. We shall prove that every large enough prime has a multiple in that set. Take n0n_0, m0m_0 such that an0+1=(ak+b)φ(a)an_0 + 1 = (ak + b)\varphi(a) and cm0+1=(ak+b)φ(c)cm_0 + 1 = (ak + b)\varphi(c) then f(an0+1)=g(cm0+1)=1f(an_0 + 1) = g(cm_0 + 1) = 1.

Then, if an+bAan + b \in A then
1=f((an+b)(an0+1))=f(a(ann0+bn0+n)+b)=g(c(ann0+bn0+n)+d). 1 = f((an + b)(an_0 + 1)) = f(a(ann_0 + bn_0 + n) + b) = g(c(ann_0 + bn_0 + n) + d).
Hence,
1=g(c(ann0+n+bn0)+d)g(cm0+1)=g(c(cm0(ann0+n+bn0)+(ann0+n+bn0)+dm0)+d)=f(a((cm0+1)(ann0+n+bn0)+dm0)+b). \begin{align*} 1 &= g(c(ann_0 + n + bn_0) + d)g(cm_0 + 1) \\ &= g(c(cm_0(ann_0 + n + bn_0) + (ann_0 + n + bn_0) + dm_0) + d) \\ &= f(a((cm_0 + 1)(ann_0 + n + bn_0) + dm_0) + b). \end{align*}
That is, (cm0+1)(an0+1)(an+b)+(adbc)m0=s(an+b)+tA(cm_0 + 1)(an_0 + 1)(an + b) + (ad - bc)m_0 = s(an + b) + t \in A. That is, for all xAx \in A we shall have sx+tAsx + t \in A. By choosing another n0n_0 we can find another s1s_1 such that s1x+tAs_1x + t \in A for all xAx \in A. Now, take a large prime pp and let us denote by b1,,bkb_1, \dots, b_k the residues of elements of AA modulo pp. Hence,
{s0b1+t,,s0bk+t}{s1b1+t,,s1bk+t}{b1,,bk}(modp). \{s_0 b_1 + t, \dots, s_0 b_k + t\} \equiv \{s_1 b_1 + t, \dots, s_1 b_k + t\} \equiv \{b_1, \dots, b_k\} \pmod{p}.
That is, s0(i=1kbi)+tks1(i=1kbi)+tki=1kbi(modp)s_0(\sum_{i=1}^k b_i) + tk \equiv s_1(\sum_{i=1}^k b_i) + tk \equiv \sum_{i=1}^k b_i \pmod{p}. Therefore, i=1kbi0(modp)\sum_{i=1}^k b_i \equiv 0 \pmod{p} and k=pk = p. That is, 0A0 \in A. It yields that, there is a number of the form an+ban + b in AA that is a multiple of pp. So, f(an+b)=1f(an + b) = 1 implies that f(p)=1f(p) = 1. By the same argument we find that g(p)=1g(p) = 1. Taking D=q<pqD = \prod_{q < p} q, we are done. \blacksquare

Comment 1. The criterion that aa, bb, cc, dd are pair-wise coprime can be reduced to the condition adbcad \neq bc.

Comment 2. We can indeed prove that there is a positive integer DD such that for all positive integers nn, mm, gcd(nm,D)=1\text{gcd}(nm, D) = 1 we have f(n)=g(m)=1f(n) = g(m) = 1. Here we provide the sketch of the solution. If f(an+b)=g(cn+d)f(an + b) = g(cn + d) for some positive integer nn. Assume that gcd(a,b)=gcd(c,d)=1\text{gcd}(a, b) = \text{gcd}(c, d) = 1. Let pp be a prime dividing an+ban + b then gcd(a,p)=1\text{gcd}(a, p) = 1 hence Pt=ptφ(a)=aTt+1P_t = p^{t\varphi(a)} = aT_t + 1 and f(Pt)=1f(P_t) = 1. Hence,
g(cn+d)=f(an+b)=f(Pt)f(an+b)=f(a(nPt+bTt)+b)(1) g(cn + d) = f(an + b) = f(P_t)f(an + b) = f(a(nP_t + bT_t) + b) \quad (1)
=g(c(nPt+bTt)+d),(2) = g(c(nP_t + bT_t) + d), \quad (2)
for all positive integers nn, tt. Let Sf={n:f(n)=1}S_f = \{n : f(n) = 1\}, Sg={n:g(n)=1}S_g = \{n : g(n) = 1\}.
It follows that c(nPt+bTt)+dSgc(nP_t + bT_t) + d \in S_g for each tt. Now, we can prove the following interesting lemma that can be proved by use of techniques presented above.

Lemma. Let aa, bb, cc, dd be integers such that aa, c>0c > 0, adbcad \neq bc. We define the set SS as follows:
i. If xx, ySy \in S, gcd(x,y)=1\text{gcd}(x, y) = 1, then xySxy \in S,
ii. If xSx \in S, yxy \mid x and gcd(xy,y)=1\text{gcd}(\frac{x}{y}, y) = 1, then ySy \in S,
iii. an+bSan + b \in S if and only if cn+dScn + d \in S.

Let rr be a prime number that doesn't divide acac and mm be a positive integer such that {rm,rm+1,}\{r^m, r^{m+1}, \dots\} is a subset of SS and there is a positive integer nn such that cn+dScn + d \in S, for some positive integer nn, there is a prime number qq that doesn't divide acac and {1,q,q2,}S\{1, q, q^2, \dots\} \subseteq S and all integers that are coprime to D=(adbc)gcd(a,c)D = (ad - bc)\gcd(a, c) are in SS.

According to this interesting lemma, Nt={nN:gcd(n,c(adbc)Tt)Sg, for all tN}N_t = \{n \in \mathbb{N} : \gcd(n, c(ad - bc)T_t) \subseteq S_g, \text{ for all } t \in \mathbb{N}\}. Now, using Chinese Remainder Theorem (CRT) to choose m0m_0 such that gcd(am0+1,(adbc)T1)=1\gcd(am_0 + 1, (ad - bc)T_1) = 1 and gcd(m0,T1)=2\gcd(m_0, T_1) = 2. Hence, {nN:gcd(n,c(adbc)m0)Sg\{n \in \mathbb{N} : \gcd(n, c(ad - bc)m_0) \subseteq S_g and therefore, {nN:gcd(n,2c(adbc))Sg}\{n \in \mathbb{N} : \gcd(n, 2c(ad - bc)) \subseteq S_g\}. Continuing this way, we can prove that {nN:gcd(n,2a(adbc))Sf\{n \in \mathbb{N} : \gcd(n, 2a(ad - bc)) \subseteq S_f. The rest is clear.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.