find all f

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

find all f

G H J

Reveal topic tags

algebra unsolved

L

G H BBookmark kLocked kLocked NReply

Source: Chinese team training 2004

The post below has been deleted. Click to close.

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

606 posts

#1 h Feb 16, 2005, 9:59 AM • 2 Y

Y by Adventure10, Mango247

Find all $f:\mathbb N\rightarrow\mathbb Z$ satisfying both of the following properties:
(1)If a,b are positive integers, then $f(ab)+f(a^2+b^2)=f(a)+f(b)$ .
(2)If a,b are positive integers and a|b, then $f(a)\ge f(b)$ .

Z K Y

The post below has been deleted. Click to close.

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

1160 posts

#2 h Feb 16, 2005, 2:59 PM • 2 Y

Y by Adventure10, Mango247

It is from Mathlinks contest 3rd edition 7th round, and i think the answer is $f$ constant, however I think this is more a number theory problem than algebra.

Z K Y

The post below has been deleted. Click to close.

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

5526 posts

harazi

#3 h Feb 16, 2005, 3:16 PM • 2 Y

Y by Adventure10, Mango247

I created this problem and intended to give in one of our TST. Yet, this was not considered very attractive and Valentin accepted to give it in mathlinks contest. The answer is far more general than the constant function.

Z K Y

The post below has been deleted. Click to close.

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

1160 posts

#4 h Feb 17, 2005, 1:37 AM • 2 Y

Y by Adventure10, Mango247

sorry Harazi, I will think more carefully about it.

Z K Y

The post below has been deleted. Click to close.

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

95 posts

#5 h Feb 17, 2005, 4:42 AM • 2 Y

Y by Adventure10, Mango247

The answer is: f(a^a'*b^b'*...d^d'*p^p'*...r^r')
=[f(p)-f(1)]+...+[f(r)-f(1)]+f(1)
where a,b,...,dare primes which are not of form 4k+3,k's integer

and p,...,r are primes which congruent to 3 (mod4)

and a',b',...,r' are positive inegers.

Z K Y

The post below has been deleted. Click to close.

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

8 posts

#6 h Feb 17, 2005, 4:47 AM • 2 Y

Y by Adventure10, Mango247

hi, well, this is my first reply

for prime p=2 and p=1(mod 4), it must satisfy f(p)=f(1) and

for prime p=3 (mod 4), it must satisfy f(p)<=f(1) (i.e. it can have any integers satisfying f(p)<=f(1) independently)

for n=p_1^e_1....p_m^e_m

define f(n)=f(p_1)+f(p_2)+...+f(p_m)-(m-1)f(1)

this function satisfies the condition which is stated in the problem.

Actually, I want to post my solution ,but I don't have any idea using LAtex.

sorry

Z K Y

The post below has been deleted. Click to close.

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

8 posts

#7 h Feb 17, 2005, 4:48 AM • 2 Y

Y by Adventure10, Mango247

it was close!

Z K Y

The post below has been deleted. Click to close.

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

1862 posts

#8 h Apr 12, 2024, 4:35 PM

Y by

I was given the version where $f(a)\le f(b)$ , which is basically the same problem.

Choose an integer $C$ then choose values of $f(p)\ge C$ for each prime $p\equiv 3\pmod 4$ . Then if the (distinct) $3$ mod $4$ prime divisors of $n$ are $p_1,p_2,\dots,p_m$ , let
$f(n)=C+\sum_{k=1}^{m}(f(p_k)-C).$ In particular, if $m=0$ , this expression gives $f(n)=C$ .

We will show that these work. Note that $f(n)=f(\operatorname{rad} n)\;\forall n$ . Let $\gcd(a,b)=d$ and $a=dm,b=dn$ . Then
$f(a^2+b^2)=f(d^2(m^2+n^2))=f(d^2)=f(d).$ Thus we may assume WLOG that $m,n,d$ are products of distinct $3$ mod $4$ primes, which will imply the desired equation.

Define $C=f(1)$ and let $S$ be the set of positive integers $n$ such that $f(n)=C$ . Note that $C$ is the minimum value of $f$ as $C=f(1)\le f(n)\;\forall n$ .
$P(a,ak)$ gives
$f(a^2k)+f(a^2(1+k^2))=f(a)+f(ak).$ Note that $f(a^2k)\ge f(ak)$ and $f(a^2(1+k^2))\ge f(a)$ , so both of these must achieve equality, meaning that $f(a^2k)=f(ak)$ . Thus $f(n)=f(\operatorname{rad} n)$ , so
$\operatorname{rad} a=\operatorname{rad} b\Longrightarrow f(a)=f(b).$ Also, $f(a^2(1+k^2))=f(a(1+k^2))$ . Setting $a=1$ gives $k^2+1\in S$ . In particular, $2\in S$ .

Consider any $s\in S$ . $P(a,s)$ gives
$f(as)+f(a^2+s^2)=f(a)+f(s)=f(a)+f(1).$ Since $f(as)\ge f(a)$ and $f(a^2+s^2)\ge f(1)$ , both of these must achieve equality. Therefore,
$s\in S\Longrightarrow f(as)=f(a)\;\forall a.$ Also, $f(a^2+s^2)=f(1)=C$ , so
$s\in S\Longrightarrow a^2+s^2\in S\;\forall a.$
We claim that
$m,n\in S\Longleftrightarrow mn\in S.$ The right obviously implies the left(due to the second condition). For the other direction, $P(m,n)$ gives
$f(mn)+f(m^2+n^2)=2C\Longrightarrow mn,m^2+n^2\in S.$
We claim that if $p$ is a $1$ mod $4$ prime, then $p\in S$ . Indeed, let $m$ be a primitive $4$ th root of unity mod $p$ . Then $p\mid m^2+1^2$ . Since $m^2+1^2\in S$ , $p\in S$ .

Let $m,n$ be two relatively prime positive integers. Then $P(m,n)$ gives
$f(mn)+f(m^2+n^2)=f(m)+f(n).$ Since $m^2+n^2$ is not divisible by any $3$ mod $4$ prime(by Fermat's Christmas Theorem), $f(m^2+n^2)=C$ . Thus
$f(mn)=f(m)+f(n)-C.$ This completes the proof that our claimed solutions are indeed the only ones. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

8847 posts

#9 h Yesterday at 7:31 PM

Y by

Notice that if $f(x)$ is a solution, then $f(x) + c$ is a solution for all integers $c$ . Henceforth we may assume that $f(1) = 0$ , so that the codomain of $f$ is the set of nonnegative integers $\mathbb N_0$ .

Claim: Let $n$ be the product of $1$ mod $4$ primes. Then $f(n) = 0$ .

Proof: Let $S = f^{-1}(0)$ denote the preimage of $0$ . Notice that by setting $a = 1$ , we get $f\left(b^2+1\right) = f(1) = 0$ , so $b^2+1 \in S$ for all positive integers $b$ .

In particular, notice that if $a \mid b$ and $b \in S$ , then $a \in S$ by the second condition. Furthermore, if $a$ and $b$ are in $S$ , then $f(ab) + f\left(a^2+b^2\right) = 0$ , i.e. $ab$ and $a^2+b^2$ must also both be in $S$ . It follows that

Since every $1$ mod $4$ prime $p$ divides $b^2+1$ for some positive integer $b$ , follows $f(p) = 0$ ;
Any product of $1$ mod $4$ primes $p$ will be in $S$ .

This implies the result. $\blacksquare$

In fact, we also have $f(2) = 0$ and $f(4) + f(8) = 2f(2) = 0$ . So $f(4) = 0$ and follows that $S$ contains all integers $n$ whose prime factorization contains only $1$ mod $4$ primes and $2$ .

Claim: Let $p$ be a $3$ mod $4$ prime. Then for any $a \in S$ and positive integer $n$ , $f(ap) = f(p) = f\left(p^n\right)$ .

Proof: The first equality follows by observing $a^2+p^2 \in S$ by Fermat Christmas as $\gcd(a, p) = 1$ . We will prove the second equality by induction on $n$ , with base case clear.

For the inductive step, let $n \geq 2$ and write $2f(p) = f(p) + f\left(p^{n-1}\right) = f\left(p^n\right) + f\left(p^2\left(p^{2n-4}+1\right)\right) = f\left(p^n\right) + f\left(p^2\right)$ as $p^{2n-4} + 1 \in S$ . If $n = 2$ , we get $f\left(p^2\right) = f(p)$ ; for $n>3$ , the result follows immediately. $\blacksquare$

Finally, if $m$ and $n$ are relatively prime positive integers, $m^2+n^2 \in S$ , so $f(mn) = f(m) + f(n)$ . Thus, we can determine $f$ uniquely by inputs $f(q_i) = r_i \geq 0$ for every $3$ mod $4$ prime $q_i$ by letting $f(n)$ denote the sum of $r_i$ over all $3$ mod $4$ primes $q_i$ dividing $n$ , without multiplicity. These functions clearly all work, which completes the proof.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a