Turkey 2016 TST

Idea_lover wrote: Turkey 2016 TST Oh no. Again. Why??

Hi .......I used the first part to prove that f (n)=n^k is a solution. And the 2nd part to show that k is odd.....How many would i get

Hemank wrote: Hi .......I used the first part to prove that f (n)=n^k is a solution This is not true.

Isn't it the catchy equation

*cauchy*..

The in the proof we set $f(e^x)=g(x)$ to get $g(x)+g(y)=g(x+y) \implies g(x)=cx$. $e^x \in \mathbb{N} \iff x \in \log_e{\mathbb{N}}$ Without bound or continuity we can't say if $f(x)=cx \forall x, y \in \log_e{\mathbb{N}}$.

That's the proof of cauchy equation......I didn't state that because it is a famous equation...will they cut marks.... I just wrote it is the catchy equation defined over natural no.s.....and it's solution is n^k

Because sgnx.|x|^c and f (x)=0 is not defined over natural no.s

As I said, the solution of \[f:\mathbb{N} \to \mathbb{N}\]\[f(m)f(n) = f(mn) \ \forall m,n \in \mathbb{N} \]is not $f(n)=n^k$. Unless some extra condition is given which was $m+n | f(m) + f(n)$ in this case.

First, $f(1)=1$ and $f(p_1^{a_1}\dots p_k^{a_k})=f(p_1)^{a_1}\dots f(p_k)^{a_k}$ So enough to show $f(p)=p^k$ where $k$ is odd. Next, $m+m\mid f(m)+f(m)$ gives $ m\mid f(m)$ for all $m\ge 1.$ Now I am stuck. ( I think we need to somehow relate $m\mid f(m), n\mid f(n)$ with $m+n\mid f(m)+f(n).$)

First $f(1)=1$. Next take $m=p^{q-1}(q-1),n=1$ where both p q distinct primes. This proves $f(p)=p^{a_p}$. Now easy to get for all $i$ $a_i=k$ for some odd $k$.

https://artofproblemsolving.com/community/c6h1285693p6777692 https://artofproblemsolving.com/community/c6h1222955p6127369

$f(mn)=f(m)f(n)$ m+n\f(m)+f(n) From eq 1 we could specify that we need to deal with primes only & also f(1)=1 Now from eq2 we get m\f(m) So now let $f(2)=2^at$, where t is an odd no. Initially consider $t\geq3$ Now from eq 2 we have m+1\ f(m)+1 Now substitute m=t-1 which is a even no. So f(2)\f(t-1) so t\f(t-1)+1 Let f(t-1)=f(2)×f(k) So t\f(2)f(k)+1 now t divides f(2) so t\1 So we got a contradiction therefore t=1 So $f(2)=2^a $ 3\f(2)+1 3$2^a$+1 So a must be odd Now from eq 2 we get m+$2^k$\f(m)+$2^ak$ So we could say m+$2^k$\f(m)-$m^a$ Now fix m & vary k this implies that $f(m) - m^a =0$ So $f(m)=m^a$ where a is an odd natural no.

I think this question wasn't the FE question it was mostly a NT question

narel wrote: $f(mn)=f(m)f(n)$ $m+n|f(m)+f(n)$ From eq 1 we could specify that we need to deal with primes only & also f(1)=1 Now from eq2 we get $m|f(m)$ So now let $f(2)=2^at$, where t is an odd no. Initially consider $t\geq3$ Now from eq 2 we have $m+1|f(m)+1$ Now substitute $m=t-1$ which is a even no. So $f(2)|f(t-1)$ so $t|f(t-1)+1$ Let $f(t-1)=f(2)\times f(k)$ So $t|f(2)f(k)+1$ now $t | f(2)$ so $t|1$ So we got a contradiction therefore $t=1$ So $f(2)=2^a$, $3|f(2)+1$, $3|2^a+1$ So a must be odd. Now from eq 2 we get $m+2^k|f(m)+2^ak$ So we could say $m+2^k|f(m)-m^a$ Now fix $m$ & vary $k$ this implies that $f(m) - m^a =0$ So $f(m)=m^a$ where a is an odd natural no.

INMO 2018 -- Problem 6 wrote: Let $\mathbb N$ denote set of all natural numbers and let $f:\mathbb{N}\to\mathbb{N}$ be a function such that $\text{(a)} f(mn)=f(m).f(n)$ for all $m,n \in\mathbb{N}$; $\text{(b)} m+n$ divides $f(m)+f(n)$ for all $m,n\in \mathbb N$. Prove that, there exists an odd natural number $k$ such that $f(n)= n^k$ for all $n$ in $\mathbb{N}$. Solution. Let the assertion $m+n\mid f(m)+f(n)$ be denoted by $Q(m,n).$ Claim 1. $m-1\mid f(m)-1$ Proof. From the first condition we have $f(1)=1.$ Now, $Q(m-1,1)\implies m\mid f(m-1)+1$ and \[Q(m^2-1,1)\implies m^2\mid f(m^2-1)+1=f(m-1)f(m+1)+1\]but we have $f(m-1)\equiv -1\pmod{m},$ hence $m\mid -f(m+1)+1\implies m\mid f(m+1)-1\implies m-1\mid f(m)-1.\qquad\square$ Claim 2. $\text{rad}(f(m))=\text{rad}(m)$ Proof. Note that $Q(m,m)\implies m\mid f(m).$ Now assume the contrary that there exists a prime $q$ such that $q\mid f(m)$ but $q\not| m.$ Putting $m\longrightarrow m^{q-1}$ in Claim 1, we obtain \[m^{q-1}-1\mid f(m)^{q-1}-1\]But by Fermat's Little Theorem, $q\mid m^{q-1}-1$ and obviously $q\not | f(m)^{q-1}-1$ since $q\mid f(m),$ which is a contradiction to our assumption. Hence the claim.$\qquad\square$ Coming back to the original problem, Let $p$ be a prime. By Claim 2, we have $f(p)=p^k$ for some natural $k$ . We know $Q(p,1)\implies p+1\mid p^{k}+1\implies p+1\mid (-1)^k+1,$ hence $k$ is odd. Now, let $q$ be an arbitrary prime not equal to $p.$ And let $f(q)=q^{\ell}$ (again here $\ell$ is odd). Then $Q(p,q)$ gives \[p+q\mid p^k+q^{\ell}\implies p+q\mid p^k+(-p)^{\ell}=p^k-p^{\ell}\implies p^k+q^{\ell}\mid p^{|k-\ell|}-1\]Taking $q$ sufficiently large, we get $k=\ell.$ Therefore, $f(p)=p^k$ for all primes $p$ where $k$ is a fixed odd number. Now, by multiplicity we get $f(n)=n^k$ for all $n\in\mathbb N.$ It is trivial to check that it works. And we are done. $\blacksquare$

$\mathbf{solution}$. claim (1). For all primes $p_i$and non negative integers $a_i$ ,$f(\prod p_i^{a_i})= \prod f(p_i)^{a_i}$. proof . For any natural $x$ and nonnegetive integer $r$ ,$f(x^r)= f(x)f(x^{r-1})$ and inductively we get,$f(x^r)=f(x)^r$. Now,since $f$ is multiplicative , hence our proof is trivial. claim(2). For any prime $p$ ,$f(p)= p^k$ ,for odd $k$. proof. For contrary let there is a prime $q$ other than $p$ such that $q|f(p)$. so, it is obvious that $q|f(pr)$ ,for natural $r$. We , must get a prime $q$ such that $q|pr+1$ . since,$ pr+1|f(pr)+1$.it implies $ q|f(1)$ . contradiction!!. So ,$f(p)$ consist only $p$. So,$f(p)=p^k$. $\gcd(p,p+1)=1$. and $p^k+1\equiv 0 \pmod{p+1}$. So,$(-1)^k+1 \equiv 0 \pmod {p+1}$. So, k is odd. Hence, for any prime $p_1$ ,we have $f(p_1)=p_1^{\ell}$. $\ell \in \mathbb{N}$. claim (3) .this $\ell$ and previous k are exactly same. proof.. We are given,$p+p_1|p^k +p_1^{\ell}$. Since $\gcd (p,p_1+p)=\gcd (p_1,p_1+p)=1$. So,$p^k +p_1^{\ell}\equiv 0 \pmod{p+p_1}$. $\implies p^k +(-p)^{\ell}\equiv 0\pmod{p+p_1}$. So,$\implies \ell= k$. From fundamental theorem of arithmetic we have $n=\prod p_i ^{a_i}$. For all nonnegetive integer $a_i$ and primes $p_i$ ,$\forall n \in \mathbb{N}$. So,all above statement follow that $f(n)=n^k$ , for odd $k$. Our proof is complete.

ftheftics wrote: $p^k +(-p)^{\ell}\equiv 0\pmod{p+p_1}$. $\implies \ell= k$. This is not true, what if $p=2,p_1=3,k=1,l=5$?

I have a question is my claim wrong ???or proof ??

integrated_JRC wrote: Let $\mathbb N$ denote set of all natural numbers and let $f:\mathbb{N}\to\mathbb{N}$ be a function such that $\text{(a)} f(mn)=f(m).f(n)$ for all $m,n \in\mathbb{N}$; $\text{(b)} m+n$ divides $f(m)+f(n)$ for all $m,n\in \mathbb N$. Prove that, there exists an odd natural number $k$ such that $f(n)= n^k$ for all $n$ in $\mathbb{N}$. The first condition is enough to deduce that $f(1)=1$. Thus we have $m+1\mid f(m+1)+1$ for all $m\in\mathbb{N}$. Claim: $f(2)=2^k$, where $k$ is an odd positive integer. Proof: Suppose $p\mid f(2)$ where $p$ is an odd prime. But we also have $p\mid f(p-1)+1=f(\tfrac{p-1}{2})f(2)+1\implies p=1$, a contradiction. Thus $f(2)=2^k$. But we also know that $3\mid f(2)+1=2^k+1\implies k$ is odd. $\square$ This claim combined with (a) directly implies that $f(2^t)=2^{tk}$. Now observe that we have $m+2^t\mid f(m)+2^{tk}$ for any $m\in \mathbb{N}$. But we also have $m+2^t\mid m^k+2^{tk}$. Hence we must have $m+2^t\mid f(m)-m^k$. Now taking $t$ to be large enough we have $f(m)=m^k$.

a little 1

integrated_JRC wrote: Let $\mathbb N$ denote set of all natural numbers and let $f:\mathbb{N}\to\mathbb{N}$ be a function such that $\text{(a)} f(mn)=f(m).f(n)$ for all $m,n \in\mathbb{N}$; $\text{(b)} m+n$ divides $f(m)+f(n)$ for all $m,n\in \mathbb N$. Prove that, there exists an odd natural number $k$ such that $f(n)= n^k$ for all $n$ in $\mathbb{N}$. Isn't it enough to show that $f(n)=n$ works ($k=1$ is odd here) as we are asked to prove that there exists an odd natural number $k$ such that $f(n)= n^k$ for all $n$ in $\mathbb{N}$? Please let me know if I'm wrong or something.

Anyone regarding my confusion???

Dragunov wrote: Anyone regarding my confusion??? The problem doesn’t ask for the existence of a function, it asks for the existence of $k$ given $f$.

Well, this topic is up, so I'll post my solution to this. It is trivial to see that $f(1)=1$. The hard part of the problem is proving that $f(2)$ is equal to $2$ to an odd power. Claim: It must be the case that $$(a-1)|(f(a)-1) (\heartsuit)$$for all positive integer $a$. Proof. In the second condition, plug $m=1, n=a^2-1$ to get that $a^2$ divides $1+f(a^2-1)$, or $$1+f(a^2-1)\equiv 1+f(a+1)f(a-1)\equiv 0 \pmod {a^2} \Rightarrow f(a+1)f(a-1)\equiv -1 \pmod {a^2}.$$A weaker condition is $f(a+1)f(a-1)\equiv -1 \pmod a$. However, by plugging in $m=1,n=a-1$ into the second equation we get $a|(1+f(a-1))\Rightarrow f(a-1)\equiv -1 \pmod a$. Combining this with $f(a+1)f(a-1)\equiv -1 \pmod a$ gives us $f(a+1)\equiv 1\pmod a\Rightarrow a|(f(a+1)-1)$. Then simply shift over. $\blacksquare$ Claim: $f(2)$ is equal to $2^k$ for some odd $k$. Plugging in $2^x$ into $\heartsuit$, as $f(2^x)=f(2)^x$ for all positive integer $x$, we have $$(2^x-1)|(f(2)^x-1).$$for all positive integer $x$. First, we prove $f(2)$ must be a power of $2$. Suppose for contradiction that $f(2)$ had any prime factor $p$ other than $2$. Then set $x=p-1$ to get that $p$ divides $2^x-1$ (by FLT) and $p$ doesn't divide $f(2)^x-1$ (as $f(2)$ is a multiple of $p$), contradiction. Now simply putting $m=1, n=2$ gives that $3|(1+f(2))\Rightarrow f(2)\equiv 2 \pmod 3$. As $f(2)$ is a power of $2$, this forces it to be $2^k$ for odd $k$. $\blacksquare$ Given $f(2)=2^k$ for an odd $k$, it suffices to prove that $f(q)=q^k$ for all primes $q$ as the function is multiplicative. Plug $m=2^y$ and $n=q$ into the second condition to get $$(2^y+q)|(2^{ky}+f(q))$$for all positive $y$, and thus $f(q)$ has one possible residue mod $2^y+q$. As $f(q)=q^k$ works, we must have $f(q)\equiv q^k \pmod {2^y+q}$. In particular, $y$ can be as large as possible, implying that $f(q)\equiv q^k$ modulo arbitrarily large numbers. Hence, the only possible value for $f(q)$ is $q^k$, and the proof is complete.

Claim:$f(p)=p^k$ $k$ is odd number.($p$ -is prime number.) Proof:If exist $q$ prime number such that $q|f(p)$ and $(p,q)=1$ $f(pk) =f(p)f(k)\implies q|f(pk)$ Exist $k \implies q|pk+1 \implies q|pk+1|f(pk)+ 1 \implies q|1$ Contradiction. $f(p)=p^k \implies f(p^m)=p^{km}$ any positive integer $m$ Remaining easy.$\blacksquare$.

Cool Problem Note that $f(1)=1$ is a trivial solution, now we show $f(2)=2^k$ where $k$ is odd. FTSOC assume a prime $p\mid f(2)$, so $f(p)\mid p-1$, for $(m,n)=(p-1,1)$ we have $p-1+1\mid f(p-1)+f(1)\implies p\mid f(p-1)+1$ which is a contradiction and $k$ is odd because $m+n\mid m^k+n^k$. We show that $f(p)=p^k$ for $k$ odd, for this we take a prime $q\neq p$ such that $q\mid f(p)\implies q\mid f(ps)$, also due to bezout's theorem we have $ps+qr=1$, $\gcd(s,r)=1$ so $q\mid ps+1\mid f(ps)+1 $ so $q\mid 1$ which is a contradiction so $f(p)=p^k$. Note that $f$ is multiplicative or $f(p_1^{a_1}\cdots p_k^{a^k})=f(p_1^{a_1})\cdots f(p_k^{a_k})$ but we are not done yet, we still have to show existence, which can be done by taking $m=p^a$ and the second condition gives us $p^a+n\mid f(p^a)+f(n)=p^{ak}+f(n)$, for odd $ak$, so $p^{ka}+n\mid f(n)-n^k$ and we are done if $n$ becomes arbitrarily large we are done as $f(n)-n^k=0\implies \boxed{f(n)=n^k}$

I wrote up this solution a while ago.. I can't tell if it is bogus or not...