Divisibility NT FE

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Divisibility NT FE

G H J

Reveal topic tags

functional equation

L

G H BBookmark kLocked kLocked NReply

Source: Own

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

69 posts

#1 h Apr 14, 2025, 7:07 PM • 1 Y

Y by cubres

Find all functions $f$ $N \rightarrow N$ such for any $a,b$ :
$(a+b)|a^{f(b)} + b^{f(a)}$ .

This post has been edited 3 times. Last edited by CHESSR1DER, Apr 15, 2025, 6:45 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

69 posts

#2 h Apr 15, 2025, 10:46 AM

Y by

Bump......

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

99 posts

#3 h Apr 15, 2025, 12:15 PM • 2 Y

Y by TunarHasanzade, TDVOLIMPTEAM

Taking $a=1$ gives:

$b+1|b^{f(a)}$ .Since $gcd(b,b+1)$ ,I don't think there is a solution in $N \rightarrow N$

You said any $a,b$ ,however function takes from natural to natural so, $a$ and $b$ must be natural as well

This post has been edited 1 time. Last edited by Nuran2010, Apr 15, 2025, 12:16 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

85 posts

#4 h Apr 15, 2025, 12:21 PM

Y by

Isn't taking $a=1$ gives $b+1|b^{f(1)}+1$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

99 posts

#5 h Apr 15, 2025, 12:28 PM • 2 Y

Y by TunarHasanzade, TDVOLIMPTEAM

Sadece_Threv wrote:

Isn't taking $a=1$ gives $b+1|b^{f(1)}+1$

Yes,sorry

:oops_sign:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

85 posts

#6 h Apr 15, 2025, 12:45 PM

Y by

$a+b|a^c+b^d$ where $c$ and $d$ are odd natural numbers. I think we can show that why $f(x)$ can't be even.

Let's assume for all natural numbers $a,b$ $a+b|a^{2c}+b^{2d}$ for some natural numbers $c,d$ .
$a\equiv -b (\mod a+b)$ $b^{2c}+b^{2^d} \equiv 0(\mod a+b)$ There is a counter example to our assumption when $a=1$ and $b=2$ . Therefore $f(a)$ and $f(b)$ can't be even at the same time for all natural numbers $a,b$ .

Then all functions which satisfy $f(x)\equiv 1\pmod 2$ for all natural numbers $x$ is a solution

This post has been edited 5 times. Last edited by Sadece_Threv, Apr 15, 2025, 12:47 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

85 posts

#7 h Apr 15, 2025, 12:49 PM

Y by

Wait I made a mistake

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

69 posts

#9 h Apr 15, 2025, 2:52 PM

Y by

Sadece_Threv wrote:

Then all functions which satisfy $f(x)\equiv 1\pmod 2$ for all natural numbers $x$ is a solution

What if $f(2) = 1, f(3) = 3$ ? $3+8 = 11$ isn't divisible by $3+2=5$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

11395 posts

#10 h Apr 15, 2025, 5:00 PM

Y by

CHESSR1DER wrote:

Find all functions $f$ $N \iff N$ such for any $a,b$ :
$(a+b)|a^{f(b)} + b^{f(a)}$ .

$f:\mathbb N\Leftrightarrow\mathbb N$ means $f$ is bijective, right?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

69 posts

#11 h Apr 15, 2025, 6:44 PM

Y by

CHESSR1DER wrote:

Find all functions $f$ $N \rightarrow N$ such for any $a,b$ :
$(a+b)|a^{f(b)} + b^{f(a)}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

69 posts

#12 h Apr 15, 2025, 6:45 PM

Y by

jasperE3 wrote:

CHESSR1DER wrote:

Find all functions $f$ $N \iff N$ such for any $a,b$ :
$(a+b)|a^{f(b)} + b^{f(a)}$ .

$f:\mathbb N\Leftrightarrow\mathbb N$ means $f$ is bijective, right?

No, my mistake.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

20 posts

#13 h Apr 16, 2025, 1:17 AM • 3 Y

Y by Nuran2010, MuradSafarli, Sadigly

Nuran2010 wrote:

Sadece_Threv wrote:

Isn't taking $a=1$ gives $b+1|b^{f(1)}+1$

Yes,sorry

:oops_sign:

My lil bro stop doing mistakes anymore...This is a official site pls know it man... :spam:

:spam:

This post has been edited 1 time. Last edited by Frd_19_Hsnzde, Apr 16, 2025, 1:20 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

internationalnick123456

135 posts

internationalnick123456

#14 h Apr 16, 2025, 3:09 PM • 2 Y

Y by MS_asdfgzxcvb, CHESSR1DER

Claim 1. $f(n)$ is odd for all $n\in\mathbb N$ .
Proof. Assume there exists $n\in\mathbb N$ such that $f(n)$ is even.
By hypothesis, $a+n\mid a^{f(n)} + n^{f(a)},\forall a\in\mathbb N\Rightarrow a+n\mid n^{f(n)} + n^{f(a)},\forall a\in\mathbb N$ .
Let $p$ be a prime such that $\text{ord}_pn$ is odd and $p>n$ ; that is, a prime divisor of $n^q-1$ which does not divide $n-1$ , for some sufficiently large prime $q$ . Setting $a=p-n$ , we get $p\mid n^{h} + 1$ for some $h\in\mathbb N$ , which is a contradiction.
Corollary 1. $a+b\mid b^{f(a)} - b^{f(b)},\forall a,b\in\mathbb N$ .
Claim 2. For all $u,v\in\mathbb N\setminus\{1\}$ with $(u,v)=1$ , we have $f(u)=f(v)$ .
Proof. By CRT, there exists some $k\in\mathbb N$ such that $\begin{cases}k+u\equiv 0\pmod {u^{f(u) + 1}} \\k+v\equiv 0\pmod {v^{f(v) + 1}}\end{cases}$ Since $k+u\mid u^{f(k)} - u^{f(u)}$ , it follows that $u^{f(u) + 1}\mid u^{f(k)} - u^{f(u)}$ $\Rightarrow f(k) = f(u)$ . Similarly, we deduce that $f(k) = f(v)$ . Hence, $f(k)=f(u)=f(v)$ .

Returning to the problem, by Claim 1 and Claim 2, the function $f$ is constant on $\mathbb{N} \setminus \{1\}$ .
Moreover, we observe that $f(1)$ can be any arbitrary odd value.
Therefore, all functions satisfying the given conditions are of the form:
$f(1) = \lambda, \quad f(n) = \gamma,\forall n\geq 2$ for some odd constants $\lambda, \gamma$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a