Iran TST 2011 D4 P3

For discussing Olympiad Level Number Theory problems
User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:
Iran TST 2011 D4 P3

Unread post by Phlembac Adib Hasan » Wed Feb 11, 2015 1:22 pm

Find all functions $f : \mathbb{N} \rightarrow \mathbb{N}$ such that \[af(a)+bf(b)+2ab\in \square \forall (a,b)\in \mathbb N^2\]Here $\square =\{a^2:a\in \mathbb N\}$
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
Fm Jakaria
Posts:79
Joined:Thu Feb 28, 2013 11:49 pm

Re: Iran TST 2011 D4 P3

Unread post by Fm Jakaria » Sat Feb 14, 2015 6:31 am

My Solution:
For any odd prime $p$, we give the legendre symbol $(\dfrac{1/2}{p})$ the usual values $1$ and $-1$, respectively whether there exists an integer $x$ with $2x^2 \equiv 1$ (mod $p$) or do not exist such $x$.
We define $T = ${$p \in P-${$2$}$: (\dfrac{1/2}{p}) = -1$}. Here $P$ is the set of all primes.
Note: $|T| = \infty$.
Proof: Let us set $Q = P \cap ${$8k+5: k \in N_0$}. By Dirichlet's theorem, $|Q| = \infty$.
Fix any $s\in Q$. Let $(\dfrac{1/2}{s}) = 1$. Then for some integer $x$,
$2x^2 \equiv 1$(mod $s$). Then
$1 = (\dfrac{1}{s}) = (\dfrac{2x^2}{s}) = (\dfrac{2}{s})(\dfrac{x^2}{s}) = -1$, impossible.
So $Q$ is a subset of $T$, and we are done. $ \square$

Main problem: The set of positive perfect squares is $S$; and $(M)$ is the given condition.

Lemma: For arbitrary $q \in P$ and $m\in N : q || m$ ; we have $q | f(m)$.
proof: Set $m = qn$ with $(q,n) = 1$.
$(M)(qn,q^2)$ gives $q | k = q(nf(m) + qf(q^2) + 2mq) \in S$
$\Rightarrow q^2 | k \Rightarrow q | f(m)$. $\square$

For $t \in P-${$2$} ,
$(M)(t,t)$ gives $2t(t+f(t)) \in S \Rightarrow f(t) = t(2g_t^2 -1)$........(E) for some $g_t \in N$.

Claim: For any $p \in T; 2g_p^2-1 = 1$, and hence $f(p) = p$.
Proof: For contradiction, let for some $p \in T$; there exists a $p_1 \in P$ with $p_1 | (2g_p^2 -1)$.
Then $p_1$ is odd. Now as $p \in T, p_1 \neq p$.
Here mod $3$, $2g_p^2-1$ is $\pm 1$, so also $p_1 \neq 3$.
Apply $(M)(p,p_1)$ to get
$p_1 | h = p^2(2g_p^2-1) + p_1^2(2g_{p_1}^2-1)+2pp_1 \in S \Rightarrow p_1^2 | h$.
$\Rightarrow p_1 | 2 + p \dfrac{2g_{p}^2-1}{p_1} \Rightarrow p_1 || 2g_{p}^2-1$.
By (E), $p_1 || f(p)$. We apply the lemma with $q = p_1$ and $m = f(p)$ to get, $p_1 | f^2(p)$.
These last two divisibility facts are now applied next.
$(M)(p,f(p)) \Rightarrow p_1 | L = f(p)(3p + f^2(p)) \in S \Rightarrow p_1^2 | L$
$\Rightarrow p_1 | 3p$. The last is impossible since $p_1 \neq 3,p$. $\square$

We fix arbitrary $a \in N$. Let $r$ vary over $T$. We consider
$(M) (a,r)$; giving $af(a) + 2ar + r^2 = (a+r)^2 + a(f(a)-a) = M_r^2$ for some $M_r \in N$.
The last gives $(M_r + a + r) | a(f(a) - a)$, for all such $r$.
By the Note, we may take $r$ $\rightarrow \infty$, giving $M_r + a + r \rightarrow \infty$. So $f(a) = a$.
Then our only solution is $f(a) = a$ for all positive integers $a$, which indeed works. :mrgreen:
You cannot say if I fail to recite-
the umpteenth digit of PI,
Whether I'll live - or
whether I may, drown in tub and die.

Post Reply