Redacted... @below thanks

Rg230403 wrote: Is there a typo in this? The two parts seem inconsistent. If there is such a $k$ then you should be able to find $n$ such that $\gcd(an+b, k)=1$ which would mean $f(an+b)=1=0$. Also $f,g$ being identically $0$ seem like a solution. The problem asks that at least one of the two conditions must hold, not both.

Dear Mr.C can you give us some hint?

Justanaccount wrote: Dear Mr.C can you give us some hint? it is trivial that if $$n=p_1^{a_1} ... p_m^{a_m}$$then $$f(n)=f(p_1)f(p_2)...f(p_m)$$Define the set $A$ as following : $$A=\{an+b | f(an+b)=1 , n \in \mathbb{N} \}$$

My idea is a little bit different than Mr. C’s. This problem is misplaced in my opinion. It is easier than 1 and 2 for me... Assume i) is false. If $bc=da$ then since $(bc,da)=1$ it follows $abcd=(bc)(da)=1$, contradicting $abcd\ne 1$, so $bc\ne da$. Let $n_0$ such that $$f(an_0+b)=g(cn_0+d)=1$$ Suppose $p|cn+d, p\nmid abcd (bc-da)(an_0+b)$ where $an+b=(an_0+b)^k$. Then I have $an+b \equiv -a\frac dc + b \equiv \frac{bc-da}{c} (\bmod\; p)$ Claim: for all $p>\max\{bc+da, 10(b+d), cn_0+d+1, an_0+b+1, \varphi(a), \varphi(c)\}, \gcd(4\varphi(a)\varphi(c),p-1)=2$, $f(p)=g(p)=1$.

Proof: Let $f_i=ax_i+b$ be a number such that $f(f_i)=1, f_i\equiv b(\bmod\; a), f_i\equiv i(\bmod\; p)$, if it exists. (If there are multiple such $f_i$'s, any $f_i$ will work in the same way) We can see that at least two $f_i$, namely $an_0+b$ and $(an_0+b)^{1+\varphi(a)}$. Suppose $f_{a_1}, \cdots, f_{a_k}$ exist. Then note $\prod\limits_{i=1}^k f_{a_i}^{e_i} \in \{f_{a_1},\cdots, f_{a_k}\}$ if $\sum e_i\equiv 1(\bmod\; \varphi(a))$. Let $g$ be a generator mod $p$, and let $f_{a_i}=g^{t_i}$ where $0\le t_i<p-1$. Then we have $\sum t_ie_i \in \{t_1,\cdots, t_k\}$ whenever $\sum e_i \equiv 1(\bmod\; \varphi(a))$ Since $\gcd(4\varphi(a),p-1)=2$, I claim that the set of $t_i$ is $x$ odd, $d\mid x, 2d\nmid x$ where $d\mid p-1$ or $d\mid x$ for some $d\mid p-1$. We can note if $t_i$ is in one of the $f_{a_i}$'s then note $3t_i, 5t_i, \cdots, (2k+1)t_i$ are all in the $f_{a_i}$'s, which takes care of the odd factors. For the even stuff, we note that if there is one even element $d$ then all even elements are divisible by $\gcd(d,p-1)$ are in the $f_{a_i}$'s. Also, all of these sets work. So the first case is that $ax_i+b $ are all $M$th powers mod $p$ where $M|p-1$. Then there are $\frac{p-1}{M}$ terms among the $x_i$'s, $f_i$'s. Let $g_i=Xf_i+Y$ such that $cn+d\equiv X(an+b)+Y(\bmod\; p)$. The $g_i$'s are either all $M$th powers mod $p$ or all $\frac M2$th powers but not $M$th powers. This is true because the $g_i$'s are all the $N$th powers mod $p$, so it has $\frac{p-1}{N}$ terms if we use all $N$th powers or $\frac{p-1}{2N}$ terms if we only use $N$th powers that aren't $2N$th powers (only applies if $N$ is odd) If the second case is true, then all the $-g_i$'s are the $M$th powers mod $p$. In this case we will negate $X,Y$. In the end, $Xf_i+Y$ maps all $M$th powers to all $M$th powers mod $p$ for some $p\nmid Y$. Note $\sum f_i \equiv \sum\limits_{i=0}^{\frac{p-1}{M}-1} g^{iM} \equiv \frac{g^{p-1}-1}{g^M-1} \equiv 0(\bmod\; p)$ (the only exception to this is $M=p-1$ but that cannot happen because $p>an_0+b+1$) Since $\sum f_i \equiv \sum g_i\equiv 0(\bmod\; p)$, $0\equiv \sum g_i \equiv\sum (Xf_i+Y) \equiv \sum Y \equiv\frac{p-1}{M} Y (\bmod\; p)$ No matter what $M$ is, this always gives a contradiction (even $M=1$ is impossible because we can eventually force $f(p)=g(p)=1$.) Therefore, there exists $f_i\equiv \frac{bc-da}{c} (\bmod\; p)$ so $g(p)=1$. Similarly $f(p)=1$. Now I contend all large $p$ satisfy $f(p)=1$. By Dirichlet + QR+ CRT, there exists a prime $q>\max\{bc+da, 10(b+d), cn_0+d+1, an_0+b+1, \varphi(a), \varphi(c)\}, \gcd(4\varphi(a)\varphi(c),q-1)=2$ and $q$ is a generator mod $p^2$ and $g(q)=0$. We can set $cn+d=q^t, p\mid an+b$ for some $t$ by CRT so we win. Similarly $g(p)=1$ for all $p$ large so ii) is true.

Mr.C wrote: There exist $4$ positive integers $a,b,c,d$ such that $abcd \neq 1$ and each pair of them have a GCD of $1$. Two functions $f,g : \mathbb{N} \rightarrow \{0,1\}$ are multiplicative functions such that for each positive integer $n$ we have : $$f(an+b)=g(cn+d)$$Prove that at least one of the followings hold. $i)$ for each positive integer $n$ we have $f(an+b)=g(cn+d)=0$ $ii)$ There exists a positive integer $k$ such that for all $n$ where $(n,k)=1$ we have $g(n)=f(n)=1$ (Function $f$ is multiplicative if for any natural numbers $a,b$ we have $f(ab)=f(a)f(b)$) Proposed by Navid Safaii Have you a solution for this problem?

Fixed. Please take another look and kindly point out where you're confused. There is a good chance I actually typoed.

Can anyone plz post official or any other solution ??

Assume i) is false. If $bc=da$ then since $(bc,da)=1$ it follows $abcd=(bc)(da)=1$, contradicting $abcd\ne 1$, so $bc\ne da$. Let $n_0$ such that $$f(an_0+b)=g(cn_0+d)=1$$Now we consider a large prime $p>abcd((an_0+b)(cn_0+d))^{1+4ac\varphi(a)\varphi(c)}$ such that $p\equiv 2(mod\ 1+4ac\varphi(a)\varphi(c))$. We will prove that $f(p)=g(p)=1$. Note $$F=\{t|\exists f_t\in Z_+, f_t\equiv b(mod\ a),f_t\equiv g^t(mod\ p),f(f_t)=1\}$$$$G=\{t|\exists g_t\in Z_+, g_t\equiv d(mod\ c),g_t\equiv g^t(mod\ p),g(g_t)=1\}$$where $F$ and $G$ are sets in module $p-1$ and $g$ is a primitive root of $p$. We claim that the elements of $F$ form an arithmetic sequence with a common difference of $d_f|(p-1)$ if $F$ is not empty. Proof: Taking any $t_1,t_2,\cdots ,t_m\in F$ and $e_1,e_2,\cdots ,e_m$ such that $\sum_{i=1}^me_i\equiv 1(mod\ \varphi(a))$, we can easily get that $\sum_{i=1}^mt_ie_i\in F$ referring to Euler's theory and hence the claim is proved by Bezout's theory. We also have the exactly same claim for the set $G$. Let $\sigma_1:F\rightarrow G\cup\{\omega\}$ and $\sigma_2:G\rightarrow F\cup\{\omega\}$ be two mappings. $\sigma_1(t)$ denotes the only integer in module $p-1$ such that $c\cdot\frac{f_t^{1+4ac\varphi(a)\varphi(c)}-b}{a}+d\equiv g^{\sigma_1(t)}(mod\ p)$ if $c\cdot\frac{f_t^{1+4ac\varphi(a)\varphi(c)}-b}{a}+d$ is not a multiple of $p$ and $\sigma_1(t)=\omega$ otherwise. Similarly we define $\sigma_2$. Now we claim that both of the mappings are injection. By the symmetry we only need to prove the case of $\sigma_1$. Assume that $\sigma_1(t_1)\equiv \sigma_1(t_2)(mod\ p-1)$, which implies that $t_1(1+4ac\varphi(a)\varphi(c))\equiv t_2(1+4ac\varphi(a)\varphi(c))(mod\ p-1)$. We get $t_1\equiv t_2(mod\ p-1)$ immediately since $p$ is not a factor of $abcd$ and we have assumed that $p-1\equiv 1(mod\ 1+4ac\varphi(a)\varphi(c))$. By the injection we get $|F|\le|G|+1$ and $|G|\le|F|+1$. Now assume that the statement $f(p)=g(p)=1$ is false. By the symmetry let $f(p)=0$. Which means there are at least two elements $t_1,t_2$ in the set $F$ with $f_{t_1}=an_0+b$ and $f_{t_2}=(an_0+b)^{1+\varphi(a)}$. Hence $F$ and $G$ is not empty. By the first claim we can assume that $F=\{kd_f|0\le k\le \frac{p-1}{d_f}-1\}$ and $G=\{kd_g|0\le k\le \frac{p-1}{d_g}-1\}$. It is clear that the preimage $\sigma_2^{-1}(\omega)$ does not exist, since $f(n)=0$ is true for all $p|n$. We can delete $\omega$ from the range of $\sigma_2$. So the inequality can be improved to $|G|\le|F|$. Hence $|F|\le |G|+1\le |F|+1$. Since all the three numbers are integers, at least one of the inequality sign takes equal, which means that at least one of the two mappings is a bijection. If $\sigma_1$ is a bijection, note $\frac{cf_t}{a}\equiv g^L(mod\ p), \frac{ad-bc}{a}=M$ and $1+4ac\varphi(a)=K$. Consider the polynomial $\prod_{r\in g^{G\cup\{\omega\}}}(x-r)$ in module $p$, where $g^A$ denotes the set $\{r|r\equiv g^a(mod\ p), a\in A\}$ and we note $g^{\omega}=0$ as it is actually what $\omega$ means for us. On one hand $g^{G\cup\{\omega\}}=\{1,g^{d_g},\cdots, g^{p-1-d_g}\}\cup\{0\}$ considering its original definition. On the other hand $g^{G\cup\{\omega\}}=g^{\sigma_1(F)}=\{g^L+M,g^{L+d_gK}+M,\cdots, g^{L+(p-1-d_g)K}+M\}$ considering the bijection. As a conclusion we have $x(x^{\frac{p-1}{d_g}}-1)\equiv ((x-M)\cdot g^{-L})^{\frac{p-1}{d_f}}-1(mod\ p)$ calculating the polynomial by the two different expression of the set $g^{G\cup\{\omega\}}$. Comparing the coefficient of the term highest in degree we get $(g^{-L})^{\frac{p-1}{d_f}}\equiv 1(mod\ p)$, and hence we rewrite the equation as $$x(x^{\frac{p-1}{d_g}}-1)\equiv (x-M)^{\frac{p-1}{d_f}}-1(mod\ p)$$If $\frac{p-1}{d_f}\ge 3$ we compare the coefficient of the term next to the highest in degree and get $\frac{p-1}{d_f}\cdot(-M)\equiv 0(mod\ p)$ which is a contradiction. If $\frac{p-1}{d_f}=2$ we get $x(x-1)\equiv (x-M)^2-1(mod\ p)$ which is also impossible through simple discussion. At last $d_f=p-1$ is also impossible since $|F|$ is at least 2. We can also get contradictions if $\sigma_2$ is a bijection in a similar way. Therefore the assumption contradicts, hence $f(p)=g(p)=1$. Now let $p>abcd((an_0+b)(cn_0+d))^{1+4ac\varphi(a)\varphi(c)}$ be a large prime number. By CRT+Dirichlet there exists a prime number $q$ such that $q\equiv 2(mod\ 1+4ac\varphi(a)\varphi(c)), q\equiv d(mod\ c)$ and $q\equiv \frac{ad-bc}{a}(mod\ p)$. Then we have $g(q)=1$. Let $n=\frac{q-d}{c}$ and then $f(\frac{a}{c}\cdot (q-d)+b)=g(q)=1$. We get $f(p)=1$ since $q\equiv \frac{ad-bc}{a}(mod\ p)$ which implies that $p|(\frac{a}{c}\cdot (q-d)+b)$. Similarly $g(p)=1$ for all large prime number $p$.

Mr.C wrote: There exist $4$ positive integers $a,b,c,d$ such that $abcd \neq 1$ and each pair of them have a GCD of $1$. Two functions $f,g : \mathbb{N} \rightarrow \{0,1\}$ are multiplicative functions such that for each positive integer $n$ we have : $$f(an+b)=g(cn+d)$$Prove that at least one of the followings hold. $i)$ for each positive integer $n$ we have $f(an+b)=g(cn+d)=0$ $ii)$ There exists a positive integer $k$ such that for all $n$ where $(n,k)=1$ we have $g(n)=f(n)=1$ (Function $f$ is multiplicative if for any natural numbers $a,b$ we have $f(ab)=f(a)f(b)$) Proposed by Navid Safaei First we handle the case when part b ) is false and part a ) is true. $\color{red} {\textbf{Claim}} : - $$f(\mathcal{N}) $ is monotonically decreasing. $\color {red} {\textbf{Proof }}:- $ FTSOC , for all $ a < b $ we must have $ f ( a )> f ( b ) $ Then by choosing $ a = bb ' $ we get $$ f ( b ' ) = \frac{ f ( a ) }{ f ( b ) } > 1 $$,contradiction. Now choose \begin{align*} X \equiv 0 \pmod {\mathcal{ N }} \\.\\.\\.\\.\\.\\ X \equiv 0 \pmod {\infty }\end{align*}we get $$ f (\mathcal{ N }) = \frac{ f ( X) } { f (\mathcal{N}+1) ..... ..f (\infty )} < \frac{1}{\infty} = 0 $$,as required.$ \blacksquare $ Now consider the case when part $b )$ is true but part $a )$ isn't. Define $A:=\{an+b|f(an+b)=1\}$ Claim #2.1:-$|A|>1$ Proof:-Let $f_i=an_i+b,f(f_i)=1$.Let $g_i=Xf_i+Y$ where $X,Y$ are to be determined later.Let $c_i=\sum a_i g_i$ where $a_i \equiv b \pmod a$ We claim that $p|c_i$ Notice that \begin{align*}c_i \equiv \sum a_i g_i \\ \equiv \sum (an+b)(Xa_i+Y) \pmod p \end{align*}Since $X,Y$ are arbitrary we can choose them in such a way s.t $c_i \equiv 0 \pmod p$.(Just expand stuff.) Let $c,d$ be natural numbers s.t $cn+d \equiv Xa_i+Y \pmod p$ and $\gcd_{\text{pairwise}}(X,Y,a,b,c,d)=1$(notice that if $c,d$ work so do $c+p,d+p$ and so on).Note that $f(an+b)=f(Xa_n+Y)=g(cn+d)$.Notice that if $an+b|Xa_n+Y$ then $f(Xa_n+Y/an+b)=1$.We can make sure that the first relation holds by CRT now we need to prove that $Xa_n+Y/an+b \in A$ which again can be ensured by CRT.$\blacksquare$ Claim #2.2:-$f(p)=1$ for all primes $p$. Proof:- Construct $c,d$ s.t $\gcd(c,d)=\gcd(c,p-1)=\gcd(d,p-1)=gcd(a,b)=1$ then $1=f(an+b)=g(cn+d)=f(p)$.$\blacksquare$

Firstly , note that since these functions are multiplicative , for each natural number $n=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$ we have : $$f(n)=\prod f(p_i)^{\alpha_i} , g(n)=\prod g(p_i)^{\alpha_i}$$Now suppose that there exist a number $n_0 \in \mathbb{N}$ such that $f(an_0+b)=g(cn_0+d)=1$ and $an_0+b=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$ , so for each index $i$ we have $f(p_i)=1$ and we'll show that for each prime number $p$ that doesn't divide any of the numbers below , we have $f(p)=g(p)=1$ which proves our claim : ( note that while $a , b , c , d$ are pairwise coprime , we have $ad-bc \neq 0$ and suppose $\varphi(a) \ge \varphi(c)$ ) $$a , b , c , d , ad-bc , p_1^{\varphi(a)}-1 , p_1^{2\varphi(a)}-1 , ... , p_1^{\varphi(a)^2}-1 (I)$$Consider the set $S$ consisting of numbers $p_1^{\beta_1}p_2^{\beta_2}...p_k^{\beta_k}$ which $\beta_{i} \equiv \alpha_{i} \pmod {\varphi(a)}$ for each index $i$. Note that for each number $n \in S$ we have $n \equiv b \pmod{a}$ , thus if for a prime number $q$ and a $n \in S$ we have $q | \frac{c}{a}(n-b)+d$ , then one can see that : $$1=\prod f(p_i)^{\beta_i}=f(n)=g(\frac{c}{a}(n-b)+d) \implies g(q)=1$$Now considering a prime number $p$ that satisfies condition $(I)$ , and defining the sets $S_0=\{\frac{c}{a}(n-b)+d | n \in S\}$ and $T_0$ as the set of numbers in the form $cn+d$ which has prime factors dividing at least one element of $S_0$ and $S_1 , S_2 , ...$ , $T_1 , T_2 , ...$ as below , if we can find an index $i$ such that $p$ divides an element of sets $S_i$ and $S_{i+1}$ , thus obviously we can get $f(p)=g(p)=1$ : $$ 2|i \implies S_i=\{\frac{c}{a}(n-b)+d | n \in T_{i-1}\}$$$$ 2|i-1 \implies S_i=\{\frac{a}{c}(n-d)+b | n \in T_{i-1}\}$$Define $h(x)=\frac{c}{a}(x-b)+d$ and $s(x)=\frac{a}{c}(x-d)+b$ and suppose that $r_1 , r_2 , ... , r_k$ are all reminders which elements of a set $T_i$ for an index $i$ produce modulo $p$ which $k$ is the maximum number of reminders that a set $T_j$ can produce modulo $p$. Suppose that $k<p$. Clearly $h(r_1) , h(r_2) , ... , h(r_k)$ are pairwise distinct modulo $p$ too and by the maximality of $k$ , these $k$ numbers are all reminders which elements of $T_{i+1}$ produce modulo $p$. Now note that since numbers $p_1^{\alpha_1} , p_1^{\alpha_1 + \varphi(a)} , ... , p_1^{\alpha_1 + \varphi(a)^2}$ are pairwise distinct modulo $p$ , we have $k>\varphi(a)$ and while the equation $x^{\varphi(a)} \equiv 1 \pmod{p}$ has at most $\varphi(a)$ solutions modulo $p$ , there exist an index $i$ such that $r_i^{\varphi(a)}$ is not equal to $1$ modulo $p$ and since $h(r_{i}^{\varphi(a)}r_1) , h(r_{i}^{\varphi(a)}r_2) , ... , h(r_{i}^{\varphi(a)}r_k)$ are pairwise distinct reminders modulo $p$ for $T_{i+1}$ too , thus one can see that : $$ \sum h(r_j) \equiv \sum h(r_{i}^{\varphi(a)}r_j) \pmod{p} \implies r_{i}^{\varphi(a)}(r_1+r_2+...+r_k) \equiv r_1+r_2+...+r_k \pmod{p}$$$$\implies \sum r_j \equiv 0 \pmod{p}$$Similary $s(h(r_1)) , s(h(r_2)) , ... , s(h(r_k))$ are all reminders of $T_{i+2}$ values modulo $p$ and similary we have : $$ p | \sum h(r_j) \implies p | k(ad-bc)$$which is a contradiction and $k=p$ . Thus for each big enough index $i$ , sets $S_i$ and $T_i$ have an element which is divisible by $p$ and we're done.

MatBoy-123 wrote: Can anyone plz post official or any other solution ?? As I know, Iranian Math Society didn't release the official solutions; specifically for TST. You can find the solutions of 2nd round or even 3rd round. But it's probably impossible to find the official solutions of TST exams. Btw, I thought Shayan's solution is much much close to the official solution, isn't it Shayan?