$p|f(m+n) \iff p|f(m) + f(n)$ (IMO Shortlist 2007, N5)

The post below has been deleted. Click to close.

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

orl

3647 posts

orl

#1 h Jul 13, 2008, 1:56 PM • 9 Y

Y by narutomath96, Davi-8191, tenplusten, nguyendangkhoa17112003, Adventure10, HWenslawski, Mango247, and 2 other users

Find all surjective functions $f: \mathbb{N} \to \mathbb{N}$ such that for every $m,n \in \mathbb{N}$ and every prime $p,$ the number $f(m + n)$ is divisible by $p$ if and only if $f(m) + f(n)$ is divisible by $p$ .

Author: Mohsen Jamaali and Nima Ahmadi Pour Anari, Iran

This post has been edited 6 times. Last edited by darij grinberg, Apr 29, 2016, 1:00 AM
Reason: \mapsto should be \to

Z K Y

The post below has been deleted. Click to close.

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

t0rajir0u

12167 posts

t0rajir0u

#2 h Jul 13, 2008, 6:08 PM • 6 Y

Y by narutomath96, arandomperson123, nguyendangkhoa17112003, Adventure10, Mango247, and 1 other user

All congruences below are taken $\bmod p$ .

Let $a$ be the smallest integer such that $f(a) = 0$ . Then $f(ka) = 0 \forall k \in \mathbb{N}$ . If $b$ exists not of this form such that $f(b) = 0$ , then $f(a) \equiv 0 \Leftrightarrow f(b) + f(a - b) \equiv 0 \Leftrightarrow f(a - b) \equiv 0$ (in other words, we can apply the Euclidean algorithm (or in other other words, $\mathbb{Z}$ is a PID); contradiction. Hence $f(n) \equiv 0 \Leftrightarrow \exists k \in \mathbb{N} : n = ka$ . On the other hand, clearly $f(kp) = 0 \forall k \in \mathbb{N}$ . It follows that $a | p$ . If $a = 1$ then $f$ can't be surjective, so $a = p$ .

It now follows that if $m \equiv - n$ then $f(m) \equiv - f(pk + n) \forall k \in \mathbb{N} \implies f(m) \equiv f(pk + m) \forall k \in \mathbb{N}$ . The residues $f(m), m = 1, 2, 3, ... \frac {p - 1}{2}$ (for odd $p$ ) determine all the others. In order for $f$ to be surjective, the residues $f(n), n = 1, 2, 3, ... p - 1$ must be precisely the nonzero residues $\bmod p$ , so the residues $f(m), m = 1, 2, 3, ... \frac {p - 1}{2}$ are any subset of those residues with no additive inverses (in other words, we pair up each residue with its additive inverse and take only one element of each pair), so there are $2^{\frac {p - 1}{2} }$ ways of assigning these pairs (for odd $p$ ). When $p = 2$ , $f(m) \equiv m$ .

This and the surjective condition are the only conditions on $f$ . In other words, the values of $f$ in a particular residue class are an arbitrary permutation of the natural numbers in that residues class. For example, when $p = 2$ the odd values of $f$ are a permutation of the odd naturals and the even values of $f$ are a permutation of the even naturals.

Edit: My apologies. I thought $p$ was fixed.

Z K Y

The post below has been deleted. Click to close.

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

mohsen

13 posts

mohsen

#3 h Jul 19, 2008, 3:02 PM • 9 Y

Y by AlastorMoody, Aryan-23, OlympusHero, Lol_man000, megarnie, Adventure10, and 3 other users

Thank you for notification of my name, but My exact name is : Mohsen Jamaali!

Z K Y

The post below has been deleted. Click to close.

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

aviateurpilot

773 posts

aviateurpilot

#4 h Jul 20, 2008, 4:48 PM • 5 Y

Y by narutomath96, xdiegolazarox, Adventure10, Mango247, and 1 other user

orl wrote:

Find all surjective functions $f: \mathbb{N} \mapsto \mathbb{N}$ such that for every $m,n \in \mathbb{N}$ and every prime $p,$ the number $f(m + n)$ is divisible by $p$ if and only if $f(m) + f(n)$ is divisible by $p.$

Author: Mohsen Jamaali and Nima Ahmadi Pour Anari, Iran

we suppose that $\boxed{n>m,f(n)=f(m)}$
$\forall x\in\mathbb{N}: \ p|f(x+n)\iff p|f(x)+f(n)\iff p|f(x)+f(m)\iff p|f(x+m)$
then $f(x+m)$ and $f(x+n)$ have same pimes divisor
then $\forall X\ge max(n,m): \ X\equiv r(mod\ n-m),r\in\{1,...,n-m\}$ : $f(X),f(r)$ have same primes divisors.
$f$ surjective ===> $\exists M\ge max(n,m): \ f(M)$ is a prime $>max(f(1),f(2),....,f(n-m))$
but $f(M)$ have same primes divisor of an element of $\{f(1),f(2),...,f(n-m)\}$ (impossible)
then we must have $\boxed{n=m}$
$f$ is bijective.so we can take $g=f^{-1}$
NOW we have $p|n+m\iff p|f(g(n)+g(m))$
i continue after

Z K Y

The post below has been deleted. Click to close.

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

The QuattoMaster 6000

1184 posts

The QuattoMaster 6000

#5 h Dec 21, 2008, 11:48 PM • 4 Y

Y by narutomath96, Adventure10, Mango247, and 1 other user

Hopefully, the following works:
Solution

Z K Y

The post below has been deleted. Click to close.

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

lasha

204 posts

lasha

#6 h Aug 7, 2009, 5:38 PM • 5 Y

Y by narutomath96, huricane, Adventure10, Mango247, and 1 other user

First let's prove that $f(1) = 1$ . Assume there exists such prime $p$ that $p|f(1)$ . Using induction and condition it follows that $p|f(n)$ , for any $n$ , contradicting the fact that that $f$ is surjective. So, $f(1) = 1$ .
Take any prime $p$ . If $a$ is minimal such that $p|f(a)$ , than if $p|f(b)$ , we have $a|b$ , because otherwise $p|f(b - a),f(b - 2a),...,f(b - ka)$ , where $ka < b < (k + 1)a$ and $b - ka < a$ , contradicting the assumption. If the numbers $f(a + 1)$ and $f(a)$ have same prime divisor $p$ , than taking the smallest $m$ for which $p|f(m)$ we get $m|a,(a + 1)$ , implying $m = 1$ , but $p$ can't divide number $f(1) = 1$ . Hence, for any positive integer $a$ , $g.c.d.(f(a),f(a + 1)) = 1$ . $(1)$
Let's prove that $|f(a + 1) - f(a)| = 1$ , for all positive integers $a$ . Assume contrary that there exist $a$ and prime $p$ with $p|(f(a + 1) - f(a))$ . Take $b$ such that $f(a) + f(b)$ is divisible by $p$ (Such a number $b$ exists because of the surjectivity of $f$ .). Than, $f(a + 1) + f(b)$ is also divisible by $p$ and using the condition of the problem, we deduce: $p|f(a + b + 1),f(a + b)$ , which is obviously contradiction. (Because of $(1)$ .) So, $|f(a + 1) - f(a)| = 1$ (2)
As $f(1) = 1$ , we have $f(2) = 2$ . So, $3|((f(1) + f(2))$ , which means that $3|f(3)$ , but $f(3) = 1$ or $f(3) = 3$ . So, $f(3) = 3$ .
$f(1) + f(4) = 5$ is divisible by $5$ , so $5|f(5)$ , but $f(5)\leq f(4) + 1 \leq f(3) + 2 = 5$ . So, $f(5) = 5$ and $f(4) = 4$ . Now use induction to prove that $f(n) = n$ holds for any $n$ . Assume it's true for all $k \leq n$ (Where $n \geq 5$ ). Assume contrary that $f(n + 1) = n - 1 = f(n - 1)$ . Than, if $p|n - 1$ , there exists $a > 1$ with $a|(n - 1),(n + 1)$ . So, $a = 2$ . It means $p|f(2) = 2$ , implying $n - 1 = 2^{k}$ , for some positive integer $k$ . Than, $f(n + 2) = n - 2 = f(n - 2)$ or $f(n + 2) = n = f(n)$ . if $f(n + 2) = n - 2 = f(n - 2)$ , than for any prime divisor $p$ of $n - 2$ ,
there exist $a > 1$ with $a|(n - 2),(n + 2)$ , implying $a = 1,2 or 4$ . It means again $p = 2$ and $2^{k} - 1 = n - 2 = 2^{m}$ , which is clearly impossible. For the second case, we analogously deduce $n = 2^{m}$ , but $n = 2^{k} - 1$ . This contradiction shows that $f(n + 1) = n + 1$ , which means $f(n) = n$ , for all $n$ , which is clearly solution. Lasha Lakirbaia

Z K Y

The post below has been deleted. Click to close.

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

Zhero

2043 posts

Zhero

#7 h Dec 30, 2009, 8:17 PM • 12 Y

Y by narutomath96, AnonymousBunny, danepale, AlastorMoody, rayfish, future_gold_in_IMO, Adventure10, Mango247, and 4 other users

If this solution is correct, then the condition that $f$ is surjective can in fact be replaced with $f(1) = 1$ .

Solution

Z K Y

The post below has been deleted. Click to close.

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

timwu

973 posts

timwu

#8 h Jan 1, 2010, 9:17 PM • 9 Y

Y by narutomath96, a00012025, SupermemberVN, Phie11, A_Math_Lover, AlastorMoody, Adventure10, Mango247, and 1 other user

Solution

Alternately

Z K Y

The post below has been deleted. Click to close.

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

gold1

7 posts

gold1

#9 h Sep 14, 2013, 1:30 PM • 2 Y

Y by narutomath96, Adventure10

Z K Y

The post below has been deleted. Click to close.

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

Particle

179 posts

Particle

#10 h May 31, 2014, 5:04 AM • 2 Y

Y by Adventure10, Mango247

(Due to me & mahi)
Solution

Z K Y

The post below has been deleted. Click to close.

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

AnonymousBunny

339 posts

AnonymousBunny

#11 h Jun 1, 2014, 8:14 PM • 1 Y

Y by Adventure10

Click to reveal hidden text

This post has been edited 2 times. Last edited by AnonymousBunny, Jun 13, 2014, 5:20 PM

Z K Y

The post below has been deleted. Click to close.

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

mad

59 posts

mad

#12 h Jun 3, 2014, 4:58 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

Easy to prove that $f(1)=1$ .
Let $k$ be the smalles t integer s.t $p$ divides $f(k)$
It's easy to prove by induction tha if $p$ divides $f(a)$ ,then $p$ divides $f(ma)$
So $p$ divides $f(kx)$ for all $x$
Let $p$ divides $f(y)$ and $y=kq+r$ where $r<p$
Then $p$ divides $f(kq)+f(r)$
so $p$ divides $f(r)$ .But $r<p$ .So $r=0$ and $pk$ divides $y$

So $p$ divides $f(y)$ iff $k$ divides $y$

Let $x\equiv s (mod k)$ and $x=kq+s$
Then $p$ divides $f(s)+f(k-s)$ .As $k$ divides $x+k-s$ , $p$ divides $f(x+k-s)$ .
So $p$ divides $f(x)+f(k-s)$ .this implies $p$ divides $f(x)-f(s)$

Let $p$ divides $f(x)-f(y)$ for some $x,y$ and $y\equiv s$ (mod $k$ ).Then $f(y)\equiv -f(k-s)$ (mod $p$ )
So $p$ divides $f(x)+f(k-s)$ .this implies $p$ divides $f(x+k-s)$
So $k$ divides $x+k-s$
$p$ divides $x-y$
So $p$ divides $f(x)-f(y)$
Simillarly we can prove if $p$ divides $f(x-y)$ then $p$ divides $f(x)-f(y)$
So $f(x-y)$ and $f(x)-f(y)$ have the same prime divisors .
Let $x=y+1$ .Then $f(1)$ and $f(y+1)-f(y)$ have the same prime divisors
But $f(1)=1$ .So we must have $f(y+1)-f(y)=1$
This implies $f(x)=x$ for all $x$ .

Z K Y

The post below has been deleted. Click to close.

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

sayantanchakraborty

505 posts

sayantanchakraborty

#13 h Jun 13, 2014, 11:02 AM • 3 Y

Y by AnonymousBunny, Adventure10, Mango247

AnonymousBunny wrote:

Click to reveal hidden text
Claim 2: $f(x) = f(y) \iff x=y$

Proof: The if direction is trivial. We shall show the only if direction. Suppose $f(x)=f(y)$ for some $x \neq y.$ WLOG $y>x.$ Note that $p \mid f(y) \iff p \mid f(x) + f(y-x),$ so $p \mid f(y-x).$ Then, $p \mid f(y-x),$ so $p \mid f(k(y-x))$ for all $k \in \mathbb{N}.$ Now, for all $n,$ there exists a $q$ and $r$ such that $n= q(y-x)+r,$ where $r \leq y-x.$ It follows that $p \mid f(n) \iff p \mid f(r).$ Thus, the set of all prime divisors of $f(n)$ is equal to the set of all prime divisors of $\{f(1), f(2), \cdots , f(y-x)\},$ which contradicts the surjectivity of $x.$ $\blacksquare$

Click to reveal hidden text

Your proof of Claim 2 is wrong.You have proved that $f(x)=f(y) \Rightarrow x=y$ for only those $x$ and $y$ for which we know that $f(x)$ is divisible by $p$ ,which is a strong assumption.

Otherwise I think the proof is fine.

Z K Y

The post below has been deleted. Click to close.

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

AnonymousBunny

339 posts

AnonymousBunny

#14 h Jun 13, 2014, 11:13 AM • 2 Y

Y by Adventure10, Mango247

Yes I see. That's not how I was thinking though, I completely messed up while writing the solution. I hope it's correct now. Thanks for pointing it out!

Z K Y

The post below has been deleted. Click to close.

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

sayantanchakraborty

505 posts

sayantanchakraborty

#15 h Jan 14, 2015, 11:09 AM • 2 Y

Y by Adventure10, Mango247

My solution may be similar to others:

Exactly as the above argument show that $f(1)=1$ .Now suppose $f(x)=f(y)$ for some $x>y$ .Fix a prime $p$ .By surjectivity there exists $m$ such that $p|f(x+m)$ .Then $p|f(x)+f(m)=f(y)+f(m) \implies p|f(y+m)$ .We also have $p|f(x+m) \implies p|f(x-y)+f(y+m) \implies p|f(x-y)$ .This happens for infinitely many primes $p$ ,forcing $f(x-y)=0$ which is an impossibility.Thus the function $f$ is one-one,and consequently with the problem statement,bijective on $\mathbb{N}$ .

Lemma:If $d$ is the minimal positive integer such that $p|f(d)$ ,then $p|f(m) \Leftrightarrow d|m$ .Further $f(x) \equiv f(y) \pmod{p} \Leftrightarrow x \equiv y\pmod{d}$ .

Proof:Let $m=dk+r$ where $0 \le r <d$ .Then $p|f(d) \implies p|f(dk)$ by easy induction.Thus $p|f(m) \implies p|f(dk+r) \implies p|f(kd)+f(r) \implies p|f(r)$ ,This is a contradiction unless $r=0$ by the choice of $d$ .Proving the other side is trivial.

For the second claim let $x>y$ .Then $p|f(x)-f(y) \implies p|f(x-y) \implies d|x-y$ as desired,Once again the other side is trivial to see.

Thus $f(1),f(2),\cdots,f(d)$ are incongruent modulo $d$ ,which means $d \le p$ .If $d<p$ then some integer modulo $d$ will not occur in the range of $f$ ,contradicting bijectivity.Thus $d=p$ .This together with the lemma yeilds that $f(x) \equiv f(y)\pmod{p} \Leftrightarrow x \equiv y\pmod{p}$ .

Now lets induct to show that $f(n)=n \forall n \in \mathbb{N}$ .The base case is already settled.Let this be true for all integers upto $n$ .If any prime $p$ divides $f(n+1)-n$ then we would have $p|f(n+1)-f(n) \implies p|1$ by the lemma,which is absurd.We also see that $f(n+1) \ge n+1$ due to bijectivity.Thus $f(n+1)-n=1$ or $f(n+1)=n+1$ ,completing the induction step and the proof.

Z K Y

The post below has been deleted. Click to close.

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

ZETA_in_olympiad

2211 posts

ZETA_in_olympiad

#37 h May 29, 2022, 12:53 PM

Y by

For any prime $p$ exists $k: p\mid f(k).$ By induction $p\mid f(ak).$ Consequently $f(1)=1$ by surjectivity. All are modulo p.

Claim 1: $p\mid f(x)\iff k\mid x.$
Proof. If $p\mid f(x)$ but $k\nmid x$ then let $x=ab+c.$ So $f(ab)+f(c)\equiv f(c),$ absurd. The other direction is trivial. $\blacksquare$

Claim 2: $k=p.$
Proof. Note that $f(x)\equiv f(x+k).$ It is not hard to follow that $k\geq p.$ If $f(x)\equiv f(y),$ then $f(ak-x)\equiv f(ak-y).$ So $f(ak+x-y)\equiv 0.$ Thus $k\mid x-y.$ So the claim. $\blacksquare$

Claim 3: $f(x)\equiv f(y)\iff x\equiv y.$
Proof. The first direction gives ( $a$ is constant) $f(x)+f(akx-x)\equiv f(y)+f(akx-x)\equiv f(y+akx-x).$ So $x\equiv y.$ The second direction gives $y-x+akx\equiv 0.$ So $f(y-x+akx)\equiv f(y)+f(akx-x)\equiv 0.$ Clearly $f(x)+f(akx-x)\equiv 0,$ so the claim. $\blacksquare$

Claim 4: $f(x)=x.$
Proof. If $f(x)>x,$ then $p\mid f(x)-x+1\geq 2.$ It gives $x\equiv x-1,$ absurd. If $f(x)<x,$ then $p\mid x-f(x)+1\geq 2.$ It gives $f(x)\equiv f(x)-1,$ absurd. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

ZETA_in_olympiad

2211 posts

ZETA_in_olympiad

#38 h May 29, 2022, 12:58 PM • 1 Y

Y by Mango247

Physicsknight wrote:

Answer
$f (n)=n\forall n\in\mathbb N$

Solution

Claim 1- $f (n)=n$
Proof- $\frac {p}{f (n)+f (m)}\implies \frac {p}{f (m+n)}$ . There exists an integer such that $a(f (n))+f (m))=f (n)+f (m)$ . If we show that $f (0)=0, a=1$ , and $f (1)=1$ . Then $f (n+1)=f (n)+1$ so $f (n)=n\forall n\in\mathbb N$ .

Claim 2- $f (0)=0$

Proof- $f (0)=2af (0)$ for $n=m=0$ . If $f\ne 0$ then $a=\tfrac 12$ . Since $a$ is an integer, $f (0)=0$ .
Claim 3- $f (n+m)=a(f (n)+f (m))$ .

Proof- Decompose $f (m+n)$ into a prime number, and $f (n)+f (m)$ . Since $p$ divides $f (n)+f (m)\implies \frac {p}{f (n+m)}$ . There are common prime factors this $\implies a$ exists.

This is wrong, there's nothing f(0).

Z K Y

The post below has been deleted. Click to close.

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

megarnie

5560 posts

megarnie

#39 h Aug 9, 2022, 2:48 PM

Y by

The only solution is $\boxed{f(n) = n}$ , which works. We now prove it's the only solution.

Let $x\sim y$ denote that for all primes $p$ , $p\mid x \iff p\mid y$ .

So we have the assertion $P(m,n)$ that $f(m+n) \sim f(m) + f(n)$ Claim: $f(1) = 1$ .
Proof: Note that there exists a positive integer $k$ such that $f(k) = 1$ .

If $k>1$ , then $f(k) =1 \sim f(1) + f(k-1)$ , contradiction as $f(1) + f(k-1) > 1$ .

So $k=1$ . $\square$

Claim: For any prime $p$ and positive integers $a>b$ , if $p\mid f(a) - f(b)$ , then $p\mid f(a-b)$ .
Proof: By surjectivity, let $k$ be a positive integer for which $p\mid f(a) + f(k)$ and $p\mid f(b) + f(k)$ .

$P(a,k)$ implies $p\mid f(a+k)$

$P(b,k)$ implies $p\mid f(b+k)$ .

$P(b+k, a-b): f(a+k) \sim f(b+k) + f(a-b)$ . So $p\mid f(b+k) + f(a-b) \implies p\mid f(a-b)$ . $\square$

So $f$ is injective and $|f(m+1) - f(m)| = 1$ for all positive integers $m$ .

We now show $f(n) = n\forall n$ by induction (base case $f(1) = 1$ ).

Suppose $f(m) = m$ for all $m<x$ , where $x>1$ .

We have $|f(x) - f(x-1)| = 1$ , so $f(x) = x-2$ or $f(x) = x$ . If $f(x) = x-2$ , then $f(x) = f(x-2)$ , contradicting injectivity. So $f(x) = x$ , which completes the induction.

Z K Y

The post below has been deleted. Click to close.

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

Shayan-TayefehIR

104 posts

Shayan-TayefehIR

#40 h Sep 8, 2022, 2:37 PM

Y by

Firstly , we'll show that $f(1)=1$ . By surjectivity of $f$ , we know that there exist a number $n \in \mathbb{N}$ , such that $f(n)=1$ , then if $n>1$ , one can see that for each prime number $p$ which $p | f(n-1)+f(1)$ , we have $p|f(n)=1$ , so $f(n-1)+f(1)=1$ which is a contradiction and we get $f(1)=1$ .
Now notice that since for each natural number $m$ , the set of prime factors of numbers $f(m+1)$ and $f(m)+1$ are equal , as the result we have $gcd(f(m) , f(m+1))=1$ . Now define the function $g: \mathbb{N} \to \mathbb{N}$ in such a way that for each natural number $n$ , $g(n)$ be the least number such that $f(g(n))=n$ . ( which always there exist such a $g(n)$ by surjectivity. )
So we'll show that for natural numbers $n,m$ , the numbers $n+f(m)$ and $n+f(m+1)$ are coprime. Suppose not and there exist a prime number $p$ which divides both of these numbers , then one can see that :
$p|n+f(m) \implies p|f(g(n)+m) , p|f(g(n)+m+1) \implies p|gcd(f(g(n)+m) , f(g(n)+m+1))=1$ which is a contradiction. So numbers $f(m+1)-f(m)$ and $n+f(m)$ are coprime which implies $|f(m+1)-f(m)|=1$ (because if there exist a prime number $q$ , such that $q|f(m+1)-f(m)$ , then for a large enough number $k$ and $n=qk-f(m)$ , we have $q|n+f(m)$ which is a contradiction. )
Now since $f(1)=1$ , for each natural $n$ we have $f(n)\le n$ and for proving that $f(n)=n$ , it's enough to show that this equality happens for infinitely many natural numbers $n$ . ( Note that obviously , if for natural numbers $m<t<n$ we have $f(n)=n$ and $f(m)=m$ , one can get $f(t)=t$ )
Consider that $p_1<p_2<p_3<...$ are all prime numbers. By induction on $i$ we'll show that $f(p_i)=p_i$ . So obviously $f(2)=2$ and by Chebyshev's theorem for each $i$ we have $p_{i+1}<2p_{i}$ , so by induction case on $i$ one can see that :
$f(p_{i+1}-p_{i})=p_{i+1}-p_{i} , f(p_i)=p_i \implies p_{i+1}|f(p_{i+1}) , f(p_{i+1}) \le p_{i+1} \implies f(p_{i+1})=p_{i+1}$ So we're done.

This post has been edited 1 time. Last edited by Shayan-TayefehIR, Sep 8, 2022, 7:02 PM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

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

VicKmath7

1388 posts

VicKmath7

#41 h Mar 13, 2023, 4:40 PM

Y by

Solution

This post has been edited 2 times. Last edited by VicKmath7, Mar 13, 2023, 4:44 PM

Z K Y

The post below has been deleted. Click to close.

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

HamstPan38825

8857 posts

HamstPan38825

#42 h Apr 9, 2023, 2:52 AM

Y by

$f$ surjective implies $f(1)=1$ , so we restate the problem as such.

The answer is $f(n) = n$ only. Call a positive integer $n$ $g(a)$ if $n$ contains only prime factors in $a$ and all prime factors in $a$ .

Notice that $f(2) = 2$ clearly. Now we induct from $f$ on $[1, 2^n]$ to $(2^n, 2^{n+1}]$ . Observe that $f(2^{n+1} - 1) = g(2^{n+1} - 1)$ by the constraint. Thus, for $k \in (2^n, 2^{n+1}] = 2^{n+1} - a$ , we have $g(2^{n+1} - 1) = f(k) + f(a) = f(k) + a = f(k)+f(a+1) - 1 = 2^k - 1.$ In particular, by Zsigmondy we must have $n+1 = k$ precisely, so $f(k) = 2^{n+1} - a = k,$ as needed.

This post has been edited 2 times. Last edited by HamstPan38825, Apr 9, 2023, 2:53 AM

Z K Y

The post below has been deleted. Click to close.

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

awesomeming327.

1692 posts

awesomeming327.

#43 h Apr 10, 2023, 10:10 PM

Y by

Suppose $p\mid f(a)$ . If $p\mid f((k-1)a)$ then $p\mid f((k-1)a)+f(a)\implies p\mid f(ka)$ . By induction, $p\mid f(ka)$ for all positive integers $k$ . Suppose $p\mid f(b)$ , then $p\mid f(b) \implies p\mid f(\text{min}(a,b))+f(|a-b|)$ so $p\mid f(|a-b|)$ . By the Euclidean Algorithm, $p\mid f(\text{gcd}(a,b))$ .

If $f(1)>1$ then let $q\mid f(1)$ . We have $q\mid f(k)$ for all $k$ , violating surjectivity. Thus, $f(1)=1$ . If $p\mid f(a)$ and $p\mid f(a+1)$ then $p\mid f(1)$ , impossible, so $f(a)$ and $f(a+1)$ are coprime. Suppose $p\mid f(a+1)-f(a)$ then pick $b$ such that $p\mid f(a)+f(b)$ , so $p\mid f(a+1)+f(b)$ . This means that $p\mid f(a+b)$ and $p\mid f(a+b+1)$ , contradiction. Thus, $f(a+1)-f(a)$ is $1$ or $-1$ .

Let $f(a+1)=f(a)-1$ , then $f(a)=f(a+1)+f(1)$ , so $p\mid f(a)\iff p\mid f(a+2)$ . If $f(a)\neq f(a+2)$ their positive difference is two, so for every prime $q>2$ , if it is divisible by one of those it cannot be divisible by the other. Thus, either $f(a)=f(a+2)$ or $f(a)=4$ , $f(a+2)=2$ . However, in the second case we can apply the same reasoning to $f(a+1)=f(a+2)+f(1)=3$ which can't happen because $f(a+1)=3$ has no corresponding $f(a+3)$ that works.

Therefore, $f(a)=f(a+2)=x$ and $f(a+1)=x-1$ . Call $a$ sus if if satisfies this. Furthermore, call $a$ imposter if $f(a+3)=x+1$ and crewmate if $f(a+3)=x-1$ . We are under the assumption that at least one sus number exists. If $a$ is a crewmate, then $a+2$ must also be sus.

By surjection, there must exist at least one imposter. WLOG just let that imposter be $a$ . Then, $f(a+3)=f(a)+1$ so $p\mid f(a+3)\iff p\mid f(a+1)$ . Since $f(a+1)\neq f(a+3)$ , $f(a+1)=2$ and $f(a+3)=4$ . Thus, $x=3$ . Therefore $a$ is sus only if $f(a)=3$ .

If $a$ is not sus and $f(a)\ge 4$ then for all $b>a$ , $b$ is not sus. We have deduced that our sus numbers are a set of consecutive odd numbers with the smallest element, if there are elements at all, of $3$ .

Suppose there is at least one sus number, then $f(3)+f(5)=6$ , so $6\mid f(8)$ . If there are at least three sus numbers, then $f(8)=2$ . IF there are two, $f(8)=4$ . If there is one, $f(8)=6$ . But then $f(2)+f(3)=5$ and so $5\mid f(5)=3$ which is impossible. Thus, there are no sus numbers, so $f$ is always strictly increasing. Thus, $f(x)=x$ for all $x$ .

Z K Y

The post below has been deleted. Click to close.

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

IAmTheHazard

5001 posts

IAmTheHazard

#44 h Aug 18, 2023, 1:15 AM • 1 Y

Y by centslordm

Throughout this solution "power of $k$ " means that it's of the form $k^m$ where $m \geq 1$ , i.e. $1$ is not a power of $k$ unless otherwise stated.

The answer is $f(n)=n$ only, which clearly works. If $f(a)=1$ , then $a=1$ , else $f(a-1)+f(1)>1$ has no prime divisors: absurd. Henceforth ignore surjectivity.

Clearly $f$ sends powers of two to powers of two. Now given that $f$ is the identity on $1,\ldots,2^k$ , for some $k \geq 1$ , we prove that it is the identity on $2^k+1,\ldots,2^{k+1}$ . Note that the base case of $k=1$ is done already, and that for the inductive step we have $\mathrm{rad}(f(n))=\mathrm{rad}(n)$ for all $n \in (2^k,2^{k+1}]$ .

Now, let $x \in (2^k,2^{k+1}]$ and suppose that $2^{k+1}-2^{l+1}<x\leq 2^{k+1}-2^l$ for some uniquely determined $0 \leq l \leq k-1$ , so $x>2^k+1$ (we will deal with the case of $x=2^{k+1}$ last). Then we have
$\mathrm{rad}(f(x)+f(2^{k+1}-x)=2 \implies f(x)+(2^{k+1}-x)=2^a$ for some $a \geq 1$ . Also, let the odd prime divisors of $2^{k+1}-2^l$ are $p_1,\ldots,p_r$ . Then if $x \neq 2^{k+1}-2^l$ , so $l \geq 1$ and thus $2 \mid 2^{k+1}-2^l$ , we have
$\mathrm{rad}(f(x)+f(2^{k+1}-2^l-x))=2p_1\ldots p_r \implies f(x)+(2^{k+1}-2^l-x)=2^bp_1^{e_1}\ldots p_r^{e_r}$ for some $b,e_1,\ldots,e_r \geq 1$ . If $x=2^{k+1}-2^l$ , then this holds as well since $\mathrm{rad}(f(x))=\mathrm{rad}(x)$ , except in the case of $l=0$ we must allow $b=0$ . Subtracting these two equations yields
$2^l=2^a-2^bp_1^{e_1}\ldots p_r^{e_r}.$ Obviously we need $a>b$ , hence $b=l$ , so rearranging the equation yields $p_1^{e_1}\ldots p_r^{e_r}=2^{a-l}-1$ . On the other hand, for Zsigmondy reasons $\mathrm{rad}(2^x-1)$ uniquely determines $x \geq 0$ , hence it follows that $a-l=k+1-l \implies a=k+1$ , hence $f(x)=x$ as desired.

It remains to deal with $f(2^{k+1})$ , which is a power of $2$ . First suppose that $k \geq 1$ . Since we know $f(2^k)=2^k$ and $f(2^k+1)=2^k+1$ , it follows that $\mathrm{rad}(f(2^{k+1})+1)=\mathrm{rad}(f(2^{k+1}+1))=\mathrm{rad}(2^{k+1}+1)$ . Then for Zsigmondy reasons, we should be able to guarantee $f(2^{k+1})=2^{k+1}$ most of the time; the exception is when $\{f(2^{k+1}),2^{k+1}\}=\{2,8\}$ , which would imply $k=2$ and $f(8)=2$ . But then we should have $\mathrm{rad}(f(10))=\mathrm{rad}(f(8)+f(2))=\mathrm{rad}(4)$ , but also $\mathrm{rad}(f(10))=\mathrm{rad}(2f(5))=\mathrm{rad}(10)$ : contradiction.

It remains to deal with $k=0$ , i.e. finding the value of $f(2)$ , where literally everything goes wrong. So we will need to do a bit of bashing.

Suppose that $f(2)=2^a$ where $a \neq 1$ , and $f(4)=2^b$ . Then $\mathrm{rad}(f(3))=\mathrm{rad}(2^a+1)$ , and thus $\mathrm{rad}(f(6))=\mathrm{rad}(2(2^a+1))$ . But we should also have $\mathrm{rad}(f(6))=\mathrm{rad}(2^a+2^b)$ , implying $\mathrm{rad}(2^{|a-b|}+1)=\mathrm{rad}(2^a+1)$ . Thus either $b=2a$ or $a=3$ and $b=2,4$ . If the latter case applies, then $f(3)$ is a power of a $3$ , say $3^c$ . Then $\mathrm{rad}(f(5))=\mathrm{rad}(2^b+1) \in \{5,17\}$ , but it should also equal $\mathrm{rad}(3^c+8)$ .

If $d=2$ , it follows that we should have $3^c+8=5^d$ for some $d$ , by taking mod $4$ it follows that $c$ is even, and then by taking mod $8$ it follows that $d$ is even, so we can write $c=2c'$ and $d=2d'$ and rewrite the equation as $(5^{d'}+3^{c'})(5^{d'}-3^{c'})=8$ , which is clearly impossible (since $c',d' \geq 1$ , so we get a size contradiction).

In the latter case, because $f(5)+1$ should have the same prime divisors as $2f(3)$ , which is twice a power of $3$ , it follows by Zsigmondy that $f(5)=17$ . Then $\mathrm{rad}(f(5)+f(3))=\mathrm{rad}(f(8))=2$ , hence $3^c+17$ is a power of $2$ , but also $\mathrm{rad}(f(5)+f(2))=\mathrm{rad}(f(3)+f(4))$ , so $3^c+16$ is a power of $5$ . By checking small cases and then applying Mihailescu it follows that $c=1$ , but this contradicts the fact that $3^c+8$ should be a power of $17$ .

Otherwise, if $b=2a$ , then $f(3)+1$ should be a power of $2$ , say $2^c$ . Then we should have $\mathrm{rad}(2^c-1)=\mathrm{rad}(f(3))=\mathrm{rad}(2^a+1)$ . Thus for any $p \mid 2^c-1$ , we should have $p \mid 2^{2a}-1$ , hence $p \mid 2^{\gcd(c,2a)}-1$ , but also if $p \mid 2^{\gcd(c,2a)}-1$ then it should divide $2^c-1$ as well. For Zsigmondy reasons, this means that $\gcd(c,2a)=c \implies c \mid 2a$ . If $c$ is even, then write $2^c-1=(2^{c/2}-1)(2^{c/2}+1)$ , which should have the same prime factors as $2^a+1$ . However, since $c/2 \mid a$ , if $p$ is an (odd) prime dividing $2^{c/2}-1$ , then we should have $p \mid 2^a-1$ as well, so it can't divide $2^a+1$ as well, hence $c/2=1$ , so $2^c-1=3$ and thus $a=3$ , so $f(2)=8$ and $f(4)=16$ , hence $\mathrm{rad}(f(5))$ equals both $11$ and $17$ : contradiction. Otherwise, if $c$ is odd, we have $c \mid a$ , so again any (odd) prime dividing $2^c-1$ divides $2^a-1$ and therefore can't divide $2^a+1$ , hence $c=1$ and $f(3)=1$ , which is forbidden.

It therefore follows that $f(2)=2$ , so we can actually finish the induction. :stretcher:

Remark: original proof was a bit off, fixed now

This post has been edited 2 times. Last edited by IAmTheHazard, Aug 18, 2023, 6:46 PM

Z K Y

The post below has been deleted. Click to close.

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

huashiliao2020

1292 posts

huashiliao2020

#46 h Sep 3, 2023, 5:29 AM

Y by

Here's a short and cool solution

took me 3.5 hours wtf im on vacation tho so its okay

It's obvious that f(1)=1, else p|f(1) by building means p|f(n), which contradicts surjectivity. Suppose $\exists m>n:f(m)=f(n)$ ; take some prime $p$ s.t. (exists by surjectivity) $p \mid f(n)+f(k)=f(m)+f(k)\implies p \mid f(n+k),f(m+k)=f(m-n)+f(n+k)\implies p\mid f(m-n)$ , contradiction for sufficiently large $p$ , whence f is injective. Now, $p\mid f(n+1)-f(n)\implies p\mid f(n+1-n)=1$ , contradiction unless |f(n+1)-f(n)|=1. Since f is bijective f is either strictly increasing or decreasing, the latter is impossible, whence f(n)=n. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

lelouchvigeo

177 posts

lelouchvigeo

#47 h Jan 30, 2024, 4:34 PM

Y by

My first N5

Incomplete, Badly written
remarks
Basically a bit of casework solves this problem

Z K Y

The post below has been deleted. Click to close.

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

joshualiu315

2513 posts

joshualiu315

#48 h Feb 12, 2024, 8:23 PM

Y by

The answer is $\boxed{f(x)=x}$ , which evidently works.

Notice that $f$ is surjective if and only if $f(1)=1$ , so we will use these two properties interchangeably. Denote $\operatorname{rad}(x)$ as the product of the distinct prime factors of $x$ . Finally, let the given assertion be $P(m,n)$ .

Claim 1: $\operatorname{rad}(f(2^e)) = 2$ for all integers $e \ge 1$ .

Proof: Take $P(2^{e-1}, 2^{e-1})$ . This means that if $\operatorname{rad} (f(2^{e-1}))=2$ , we also have $\operatorname{rad} (f(2^e)) = 2$ , so induction finishes. $\square$

Claim 2: We have $f(x)=x$ for $x \le 4$ .

Proof: $f(1)=1$ is given, so we just need to show the claim for $2 \le x \le 4$ .

First, $P(3,1)$ gives $f(3)=2^y-1$ for some $y$ , and we already established that $f(2)=2^x$ for some $x$ . Then, $P(2,1)$ gives

$\operatorname{rad}(2^x+1) = \operatorname{rad}(2^y-1).$
We will use casework now:

If $x=3$ , we must have $\operatorname{rad}(2^x+1) = \operatorname{rad}(2^y-1)=3$ , which gives

$2^y-1 = 3^z.$
Setting $y=2$ and applying Zsigmondy makes it the only solution for this equation.

Hence, $f(2)=8$ and $f(3)=3$ . Then, $P(3,2)$ gives

$\operatorname{rad}(f(2)+f(3)) = \operatorname{rad}(f(5)) = \operatorname{rad}(f(1)+f(4)) = 11$ $\implies 2^a+1=11^b.$
Plugging in $a=5$ makes the LHS contain a factor of $11$ , so by Zsigmondy, we just manually test $a \le 5$ to see that this equation has no solutions.
Otherwise, denote $p$ as a primitive prime factor of $2^{2x}-1$ , which exists by Zsigmondy. Since it does not divide $2^x-1$ , it must divide $2^x+1$ and $2^y-1$ . Thus, $2x \mid y$ , and $2^{2x}-1 \mid 2^y-1$ . This fixes $x=1$ and Zsigmondy fixes $y=2$ .

Hence, $f(2)=2$ and $f(3)=3$ . Then, $P(3,2)$ gives

$\operatorname{rad}(f(2)+f(3)) = \operatorname{rad}(f(5)) = \operatorname{rad}(f(1)+f(4)) = 5$ $\implies 2^a+1=5^b.$
Zsigmondy shows that $a \le 2$ , which gives $f(4)=4$ as the only solution. $\square$

Claim 3: If $\operatorname{rad} (2^x-1) = \operatorname{rad} (2^y-1)$ or $\operatorname{rad} (2^x+1) = \operatorname{rad} (2^y+1)$

Proof: This is a simple consequence of Zsigmondy. $\square$

We will prove that $f(n)=n$ by strong induction up to $2^k$ . The base case already holds, so suppose the inductive hypothesis holds up to $2^k$ .

Notice that

$2 = \operatorname{rad}(f(2^{k+1})) = \operatorname{rad}(f(2^{k+1}-1)+f(1)) = \operatorname{rad}(f(2^{k+1}-1)+1),$
so $f(2^{k+1}-1)=2^t-1$ for some $t$ . Then,

$\begin{align*} \operatorname{rad}(2^t-1) &= \operatorname{rad}(f(2^{k+1}-1)) \\ &= \operatorname{rad}(f(2^k-1)+f(2^k)) \\ &= \operatorname{rad}((2^k-1)+2^k) \\ &= \operatorname{rad}(2^{k+1}-1). \end{align*}$
This shows that $k+1 = t \implies f(2^{k+1}-1) = 2^{k+1}-1$ .

Next, recall that $f(2^{k+1})=2^t$ for some $t$ :

$\begin{align*} \operatorname{rad}(2^t+1) &= \operatorname{rad}(f(2^{k+1})+1) \\ &= \operatorname{rad}(f(2^{k+1})+f(1)) \\ &= \operatorname{rad}(f(2^{k+1}-1)+f(2)) \\ &= \operatorname{rad}(2^{k+1}+1), \end{align*}$
implying that $t=k+1 \implies f(2^{k+1}) = 2^{k+1}$ .

Finally, suppose that $n \in (2^k, 2^{k+1}-1)$ and let $i=2^{k+1}-n-1$ . We have

$\begin{align*} \operatorname{rad}(f(n)+i) &= \operatorname{rad}(f(n)+f(i)) \\ &= \operatorname{rad}(f(n+i)) \\ &= \operatorname{rad}(f(2^{k+1}-1)) \\ &= \operatorname{rad}(2^{k+1}-1), \end{align*}$
and

$\begin{align*} \operatorname{rad}(f(n)+i+1) &= \operatorname{rad}(f(n)+f(i+1)) \\ &= \operatorname{rad}(f(n+i+1)) \\ &= \operatorname{rad}(f(2^{k+1})) \\ &= \operatorname{rad}(2^{k+1}). \end{align*}$
So, we have an integer $j$ such that

$f(n)+i+1 = 2^j \implies \operatorname{rad}(2^j-1) = \operatorname{rad}(f(n)+i) = \operatorname{rad}(2^{k+1}-1),$
so $j=k+1$ , which means $f(n)=n$ .

The induction is complete, and the problem is solved.

Z K Y

The post below has been deleted. Click to close.

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

AlanLG

241 posts

AlanLG

#49 h Feb 15, 2024, 8:39 PM

Y by

We forgot the condition of $f$ being surjective and only use $f(1)=1$
The problem can be rewrited as
$\operatorname{rad}\big(f(x)+f(y)\big) = \operatorname{rad}\big(f(x+y)\big) \hspace{0.2cm}\forall\hspace{0.1cm} x,y\in \mathbb{N}$ Where $\operatorname{rad}(a)$ is the product of distinct primes of $a$

$\textcolor{blue}{\text{Claim. } f(2^\theta) \hspace{0.1cm}\text{is a power of 2}}$
Plugging $(1,1)$
$\operatorname{rad}\big(f(1)+f(1)\big)=\operatorname{rad}\big(f(2)\big)$ so
$\operatorname{rad}\big(f(2)\big)=\operatorname{rad}(2)$ then $f(2)=2^\theta$
And as
$\operatorname{rad}\big(f(2^\alpha)+f(2^\alpha)\big)=\operatorname{rad}\big(f(2^{\alpha+1})\big)$ We conclude by induction
$\textcolor{blue}{\text{We start by finding the frist values of the function}}$
Plugging $(2,1)$
$\operatorname{rad}\big(f(2)+f(1)\big)=\operatorname{rad}\big(f(3)\big)$ But
$\operatorname{rad}\big(f(2)+f(2)\big)=\operatorname{rad}\big(f(3)+1\big)$ so
$f(3)+1=2^\gamma$ then
$\operatorname{rad}\big(2^\gamma-1\big)=\operatorname{rad}\big(2^\theta+1\big)$ Let $p$ be a primite prime of $2^{2\theta}-1$ which by Zsigmondy exists $\left(\operatorname{Ord}_p(2)=2\theta\right)$ , then so
$p\mid 2^{2\theta}-1 \Rightarrow p\mid 2^{\theta}+1 \hspace{0.1cm} \text{as}\hspace{0.1cm} p\mid 2^{\gamma}-1 \Rightarrow 2\theta\mid \gamma$ $\Rightarrow 2^{2\theta}-1\mid 2^{\gamma}-1 \Rightarrow (2^\theta-1)(2^\theta+1)\mid 2^{\gamma}-1$ And as $\gcd(2^\theta-1,2^\theta+1)=1\Rightarrow 2^\theta-1=1\Rightarrow f(2)=2$

so
$\operatorname{rad}\big(f(3)\big)=\operatorname{rad}(3)\Rightarrow f(3)=3^\alpha \Rightarrow 3^\alpha+1=2^\gamma$ by Zsigmondy(or Catalan) $\alpha=1$ and $\gamma=2$
Then we got that
$f(1)=1 \hspace{1cm} f(2)=2 \hspace{1cm} f(3)=3$ Now,
$\operatorname{rad}\big(1+f(4)\big)=\operatorname{rad}\big(f(2)+f(3)\big)=5$ so $1+2^u=5^v$ and again by Zsigmondy $f(4)=4$ and $f(5)=5$
$\textcolor{red}{\text{So we got}\hspace{0.1cm} f(a)=a \hspace{0.1cm} \forall \hspace{0.1cm} 1\leq a \leq 5}$

$\textcolor{blue}{\text{Lemma. if}\hspace{0.1cm} \operatorname{rad}(2^x-1)=\operatorname{rad}(2^y-1) \hspace{0.1cm} \text{then} \hspace{0.1cm} x=y }$
Trivial by Zsigmondy

$\textcolor{blue}{\text{We are going to prove that}\hspace{0.1cm} f(x)=x \hspace{0.1cm} \forall \hspace{0.1cm} x \hspace{0.1cm} \text{by induction}}$
Suppose we have the statement for $x\leq 2^e$ we want to prove the statement for $2^e\leq x \leq 2^{e+1}$
note that
$f(x)+f(2^{e+1}-x+1)=\underbrace{f(x)+f(2^{e+1}-x)}_{2^\theta}-1 \hspace{0.5cm} (1)$ $\operatorname{rad}\big(f(2^{e+1}-1)\big)=\operatorname{rad}\big(2^\theta-1\big)$ as $\operatorname{rad}\big(f(2^{e+1}-1)\big)=\operatorname{rad}\big(f(2^e)+f(2^e-1)\big)=\operatorname{rad}(2^{e+1}-1)$ then
$\operatorname{rad}\big(2^{e+1}-1\big)=\operatorname{rad}\big(2^\theta-1\big)$ so by the lemma $f(2^{e+1})=2^{e+1}$

So in $(1)$ we get
$f(x)+2^{e+1}-x+1=2^{e+1}-1$ then $\boxed{f(x)=x}$

Z K Y

The post below has been deleted. Click to close.

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

shendrew7

793 posts

shendrew7

#50 h Mar 3, 2024, 5:26 AM

Y by

Denote the assertion as $A(m,n)$ and the notation $\operatorname{rad}(m)$ as the product of the distinct prime divisors of $m$ . We first compute special values:

$f(1)=1$ follows from surjectivity. (This will be the only use of surjectivity in this solution.)
$f(2^n)$ is a power of 2 for all $n \in \mathbb{N}$ by inducting on powers of 2.
Determine the values of $f(2)$ and $f(3)$ to be of the form $2^a$ and $2^b-1$ , respectively, using the previous and $A(1,3)$ . Then $A(1,2)$ gives us
$\operatorname{rad}(2^a+1) = \operatorname{rad}(2^b-1).$ Zsigmondy in most cases tells us there exists a primitive prime divisor $p$ with
$p \mid 2^a+1 \mid 2^{2a}-1 \implies 2^{2a}-1 \mid 2^b-1 \implies \operatorname{rad}(2^{2a}-1) = \operatorname{rad}(2^b-1) \implies 2a=b,$ contradiction. Thus $(a,b)=(3,2),(1,2)$ from examining the exceptions, from which we can conclude $f(2)=2$ and $f(3)=3$ is the only possible choice, also inducing $f(4)=4$ .

We finish with folding induction - assuming $f(x)=x$ holds for $1 \leq x \leq 2^k$ , we show it also holds for $2^k+1 \leq x \leq 2^{k+1}$ :

Note that $A(1,2^{k+1}-1)$ tells us $f(2^{k+1}-1)$ is one less than a power of 2 (say $2^{\ell}$ ), and $A(2^k, 2^k-1)$ tells us
$\operatorname{rad}(2^{\ell}-1) = \operatorname{rad}(f(2^{k+1}-1) = \operatorname{rad}(2^{k+1}-1) \implies f(2^{k+1}-1) = 2^{k+1}-1$ by Zsigmondy. (This line of argument is a recurring theme in the remainder of our proof.)
$A(2^{k+1},1)$ and $A(2^{k+1}-1,2)$ , knowing $f(2^{k+1})$ is a power of 2, concludes $f(2^{k+1})=2^{k+1}$ .
$A(x,2^{k+1}-x)$ tells us $f(x)+2^{k+1}-x$ is one less than a power of 2, and hence $A(x,2^{k+1}-x-1)$ concludes $f(x)=x$ . $\blacksquare$

This post has been edited 1 time. Last edited by shendrew7, Mar 3, 2024, 5:29 AM

Z K Y

The post below has been deleted. Click to close.

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

WLOGQED1729

41 posts

WLOGQED1729

#51 h May 31, 2024, 1:39 PM

Y by

Beautiful problem! :10:

Posting for storage.
Denote $\mathbb{N}$ and $\mathbb{P}$ by the sets of positive integers and prime numbers, respectively.
Note that problem condition is $f(m+n) \equiv 0 \pmod{p} \iff f(m)+f(n) \equiv 0 \pmod{p}$ for all $m,n \in \mathbb{N}, p \in \mathbb{P}$
The answer is $\boxed{f(n)=n~~\forall n \in \mathbb{N}}$ which is clearly satisfy the problem condition.
We’ll show that this is the only solution.
Claim 1: $f(1)=1$
Proof FTSOC, suppose $f(1)>1 \implies~~$ There exist $p\in \mathbb{P}$ s.t. $f(1)\equiv 0 \pmod{p}$
It is easy to see that $f(n)\equiv 0 \pmod{p}~~\forall n \in \mathbb{N}$ which contradicts to the facts that $f$ is surjective $~~\square$

Claim 2: If positive integers $a>b$ and prime $p\in \mathbb{P}$ satisfy $f(a) \equiv f(b) \pmod{p}$ , then $f(a-b) \equiv 0 \pmod{p}$
Proof Supoose positive integers $a>b$ and prime $p\in \mathbb{P}$ satisfy $f(a) \equiv f(b) \pmod{p}$
Since $f$ is surjective, we can select $l \in \mathbb{N}$ such that $f(a)+f(l)\equiv 0\pmod{p}\implies f(b)+f(l)\equiv 0 \pmod{p}$
By the problem condition; $f(a+l)\equiv f(b+l)\equiv 0 \pmod{p}$
Using the problem condition again; $f(a+l)\equiv 0 \pmod{p}\implies f(b+l)+f(a-b)\equiv 0 \pmod{p}$
Since $f(b+l)\equiv 0 \pmod{p}$ , it implies that $f(a-b)\equiv 0 \pmod{p}$ , as desired $~~\square$

Claim 3: $f$ is injective
Proof Suppose there exists positive integers $x>y$ such that $f(x)=f(y)$ .
Note that $f(x)\equiv f(y) \pmod{p}~~ \forall p \in \mathbb{P}$ .
By Claim 2, we can conclude that $f(x-y) \equiv 0 \pmod{p}$ for all prime $p\in \mathbb{P}$ which leads to contradiction if we pick $p>f(x-y)$

Claim 4: $|f(m+1)-f(m)|=1 ~~\forall m \in \mathbb{N}$
Proof FTSOC, suppose $|f(m+1)-f(m)|>1~~ \exists m \in \mathbb{N}$
Pick a prime $p$ which divides $f(m+1)-f(m)$ .
By Claim 1, we can conclude that $f(1)\equiv 0 \pmod{p}\implies p \mid 1$ , a contradiction!

Finally, combine Claim 1,Claim 3 and Claim 4, we can conclude that $f(n)=n \forall n \in \mathbb{N}$ , as desired. $~~\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

sansgankrsngupta

130 posts

sansgankrsngupta

#52 h Oct 25, 2024, 10:18 AM

Y by

OG! My first N5!
We claim that only function that satisfies is
Claim: $f(1)=1$
Proof: FTSOC, assume $f(1)>1$ , let $p$ be a prime dividing $f(1)$ . Now, we prove by induction on $n$ , that $f(n)$ is divisible by p for all naturals $n$ .
Now, $n=1$ satisfies the condition(Base Case)
If the condition holds for $n=k$ , then $p|f(1)+f(k)$ which implies $p|f(k+1)$ , completing our induction.
Thus, $p|f(n)$ for any natural $n$ , however this is in contrary to the fact that $f$ is surjective. Hence, our claim is proved.
Claim: let $a$ be the the minimal number such that $f(a)=p$ . then $p|f(x) \iff a|x$
Proof: let $ka \leq x < (k+1)(a)$ . We induct on $k$ . For $k=0$ , since $a$ is the minimal number such that $f(a)=p$ . So it is clear. Now if the statement is true for $k$ for $k+1$ we have that for $(k+1)a \leq x < (k+2)(a)$ $p|f(x) \iff p|f(x-a)+f(a) \iff p|f(x-a).$ Since, $ka \leq x-a < (k+1)(a)$ , $p|f(x-a) \iff a|x-a \iff a|x$ and thus our induction is complete.

This post has been edited 2 times. Last edited by sansgankrsngupta, Oct 28, 2024, 2:38 AM
Reason: -

Z K Y