Let $\mathbb{N}$ be the set of positive integers. Across all function $f:\mathbb{N}\to\mathbb{N}$ such that $$mn+1\text{ divides } f(m)f(n)+1$$for all positive integers $m$ and $n$, determine all possible values of $f(101).$
Problem
Source: 2022 Thailand Online MO P3
Tags: function, functional equation, number theory
04.04.2022 14:46
Let $P(m,n)$ be assertion $mn+1\mid f(m)f(n)+1$ for every positive integers $m,n$. Assume for the sake of contradiction that there exists prime number $p\neq 101$ such that $p\mid f(101)$. Since $\gcd(101,p)=1$, there exists a positive integer $a$ such that $a\equiv \frac{-1}{101}\pmod{p}$. $P(a,101)\implies 101a+1\mid f(a)f(101)+1\implies p\mid f(a)f(101)+1$. But since $p\mid f(101)$, $p\mid (f(a)f(101)+1)-f(a)f(101)=1$ which is absurd. Thus, either $f(101)$ has no prime divisors, which mean that it must be $1$, or $f(101)=101^k$ where $k\in\mathbb{N}$. $P(101,101)\implies 101^2+1\mid 101^{2k}+1$ where $k\in\mathbb{Z}_{\geq 0}$. We have $$101^{2k}+1\equiv \left(101^2\right)^k+1\equiv (-1)^k+1\pmod{101^2+1}.$$Hence, $k$ must be odd. Clearly, $f(x)=x^k \ \forall x\in\mathbb{N}$ where $k$ are odd positive integers satisfy the condition. $\boxed{f(101)=101^k\text{ for every odd positive integers }k.}$
05.04.2022 01:40
Quidditch wrote: Let $\mathbb{N}$ be the set of positive integers. Across all function $f:\mathbb{N}\to\mathbb{N}$ such that $$mn+1\text{ divides } f(m)f(n)+1$$for all positive integers $m$ and $n$, determine all possible values of $f(101).$ We claim that $f(101)=101^k$ for $k$ odd are all the possible values. Let $P(m,n)$ the assertionnof the F.E. The trick is in deleting any prime factor that its not $101$ so if $p \mid f(101)$ and $p \ne 101$ then by bezout's lemma there exists $b$ positive integer such that $p \mid 101b+1$ so now by $P(101,b)$ $$p \mid 101b+1 \mid f(101)f(b)+1 \implies p \mid 1 \; \text{contradiction!!}$$So $f(101)=101^k$ for some positive integer $k$. Now it remains to see which $k$'s work, now assume that $k=2k_0$ then by $P(101,101)$ $$101^2+1 \mid 101^{4k_0}+1 \implies 101^2+1 \mid 2 \; \text{contradiction!!}$$Hence $k$ is odd so $f(101)=101^k$ for $k$ odd indeed works, so we are done