function
IMO Shortlist
modular arithmetic
number theory
Divisibility

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$.

[i]Author: Mohsen Jamaali and Nima Ahmadi Pour Anari, Iran[/i]

All congruences below are taken $ \bmod p$.

Let $ a$ be the smallest integer such that $ f(a) \equal{} 0$.  Then $ f(ka) \equal{} 0 \forall k \in \mathbb{N}$.  If $ b$ exists not of this form such that $ f(b) \equal{} 0$, then $ f(a) \equiv 0 \Leftrightarrow f(b) \plus{} f(a \minus{} b) \equiv 0 \Leftrightarrow f(a \minus{} 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 \equal{} ka$.  On the other hand, clearly $ f(kp) \equal{} 0 \forall k \in \mathbb{N}$.  It follows that $ a | p$.  If $ a \equal{} 1$ then $ f$ can't be surjective, so $ a \equal{} p$.

It now follows that if $ m \equiv \minus{} n$ then $ f(m) \equiv \minus{} f(pk \plus{} n) \forall k \in \mathbb{N} \implies f(m) \equiv f(pk \plus{} m) \forall k \in \mathbb{N}$.  The residues $ f(m), m \equal{} 1, 2, 3, ... \frac {p \minus{} 1}{2}$ (for odd $ p$) determine all the others.  In order for $ f$ to be surjective, the residues $ f(n), n \equal{} 1, 2, 3, ... p \minus{} 1$ must be precisely the nonzero residues $ \bmod p$, so the residues $ f(m), m \equal{} 1, 2, 3, ... \frac {p \minus{} 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 \minus{} 1}{2} }$ ways of assigning these pairs (for odd $ p$).  When $ p \equal{} 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 \equal{} 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.

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

[quote="orl"]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 \plus{} n)$ is divisible by $ p$ if and only if $ f(m) \plus{} f(n)$ is divisible by $ p.$

[i]Author: Mohsen Jamaali and Nima Ahmadi Pour Anari, Iran[/i][/quote]

we suppose that $ \boxed{n>m,f(n)\equal{}f(m)}$
$ \forall x\in\mathbb{N}: \ p|f(x\plus{}n)\iff p|f(x)\plus{}f(n)\iff p|f(x)\plus{}f(m)\iff p|f(x\plus{}m)$
then $ f(x\plus{}m)$ and $ f(x\plus{}n)$ have same pimes divisor
then $ \forall X\ge max(n,m): \ X\equiv r(mod\ n\minus{}m),r\in\{1,...,n\minus{}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\minus{}m))$
but $ f(M)$ have same primes divisor of an element of $ \{f(1),f(2),...,f(n\minus{}m)\}$ (impossible)
then we must have $ \boxed{n\equal{}m}$
$ f$ is [size=150][b]bijective[/b][/size].so we can take $ g\equal{}f^{\minus{}1}$
NOW we have $ p|n\plus{}m\iff p|f(g(n)\plus{}g(m))$
i continue after  :wink:

Hopefully, the following works:
[hide="Solution"]
We first prove that $ f$ is bijective, and since it is surjective, we must prove that it is injective.  Assume that $ f(m) \equal{} f(m \plus{} k)$ for $ k > 0$.  Now, consider numbers in the form of $ f(m \plus{} xk \plus{} i)$, where $ 0\le i < k$ and $ x$ ranges through nonnegative integers.  At least one of these is a multiple of infinitely many primes, say $ f(m \plus{} xk \plus{} j)$.  Then, $ f(m \plus{} j)$ has the same divisors as $ f(n) \plus{} f(j)$, which has the same divisors as $ f(m \plus{} j \plus{} k)$, and we may inductively apply the same reasoning to get that $ f(m \plus{} j)$ has the same set of prime divisors as $ f(m \plus{} j \plus{} xk)$ for $ x$ ranging across nonnegative integers.  Yet, this means that $ f(m \plus{} j)$ is a multiple of infinitely many primes, so it is $ 0$.  However, the problem condition does not allow this and hence we have a contradiction, so $ f$ is bijective.

Consider the minimal $ x$ for which $ p|f(x)$ where $ p$ is a prime.  If $ p|f(l) \equal{} f(x \plus{} k)$, then $ p|[f(x) \plus{} f(k)]$, so $ p|f(k)$.  Inductively repeating this gives that $ l$ is a mutliple of $ x$.  Thus, $ p|f(l)$ if and only if $ l$ is a mulitple of $ x$.  Consider numbers in the form of $ f(nx)$ for all natural $ n$.  Call this set $ S_x$, which consists of $ \frac {1}{x}$ of the numbers in $ S_1$.  Hence, $ \frac {1}{p}$ of the natural numbers map to $ S_x$, which is $ \frac {1}{x}$ of $ S_1$.  Since $ S_1$ bijects to $ \mathbb {N}$, it follows that $ \frac {1}{p}$ of $ \mathbb {N}$ maps to $ \frac {1}{x}$ of $ \mathbb {N}$, and thus, $ x \equal{} p\implies f(p) \equal{} p$ for all primes $ p$.  This means that $ f(x)$ divides $ p$ if and only if $ x$ divides $ p$, so $ x$ and $ f(x)$ have the same set of prime divisors.  Thus, $ f(m \plus{} n)$ has the same set of prime divisors as $ m \plus{} n$, so $ f(m) \plus{} f(n)$ has the same set of prime divisors as $ m \plus{} n$.  Hence, for a prime, $ q$,\[ f(m) \plus{} f(n)\equiv 0\bmod q\iff m \plus{} n\equiv 0\bmod q\]Then,\[ f(m)\equiv \minus{} f(n)\bmod q\iff m\equiv \minus{} n\bmod q\]Consider $ t\equiv m\bmod q$.  Then, $ t\equiv \minus{} n\bmod q$, so $ f(m)\equiv \minus{} f(n)\equiv f(t)\bmod q$, so $ f(m)\equiv f(t)\bmod q$ if and only if $ t\equiv m\bmod q$.

Now, assume that $ f(x)\ne x$ for some $ x$.  Consider the smallest such $ x$.  For a sufficiently large prime, $ r$, we have that $ f(x)$ is not congruent to $ x\bmod r$.  Consider a prime $ q\equiv x\bmod r$ (which exists by Dirichlet's Theorem).  Then, we have that $ x\equiv q\equiv f(q)\equiv f(x)\bmod r$, which is a contradiction.  Hence, for all natural $ x$, we have that $ f(x) \equal{} x$.

[/hide]

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

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

[hide="Solution"]We shall show that $ f(n) \equal{} n$ is the only solution. Also, we shall denote $ p | m \iff p | n$ for all prime $ p$ as $ m \sim n$. Note that the problem condition translates to $ f(m \plus{} n) \sim f(m) \plus{} f(n)$ for all natural $ m$ and $ n$.

[b]Lemma 1[/b] If $ p$ is some prime, $ p | f(n)$, and $ k \in \mathbb{Z}^ \plus{}$, then $ p | f(kn)$.
[i]Proof[/i]: Induct on $ k$. The base case is given in the problem statement. For the inductive hypothesis, we have $ p | f(kn)$ and $ p | f(n)$, so $ p | f(kn) \plus{} f(n)$, giving $ p | f((k \plus{} 1)n$.

[b]Lemma 2[/b] $ f(1) \equal{} 1$.
[i]Proof[/i]: If $ f(1) \neq 1$, let $ p | f(1)$, where $ p$ is prime. Then our lemma implies that $ p | f(n)$ for all natural $ n$; but then, there is one $ n$ such that $ f(n) \equal{} 1$, contradicting the surjectivity of $ n$. Hence, we must have $ f(n) \equal{} 1$.

[b]Lemma 3[/b] $ f(2^k)$ is a power of 2 for all nonnegative $ k$.
[i]Proof[/i]: We use induction. $ k \equal{} 0$ is just lemma 2. For the inductive hypothesis, we have $ p | f(2^{k \plus{} 1})$ means $ p | f(2^k) \plus{} f(2^k)$, which is twice a power of 2, meaning $ p \equal{} 2$. Hence, $ f(2^{k \plus{} 1})$ must be a power of 2.

[b]Lemma 4[/b] If $ f(n) \equal{} 1$, then $ n \equal{} 1$.
[i]Proof[/i]: Assume $ n > 1$. Then $ f(n \minus{} 1) \plus{} 1 \sim f(n) \equal{} 1$, so $ f(n \minus{} 1) \plus{} 1$ has no prime factors, which is clearly impossible.

[b]Lemma 5[/b] $ f(2) \equal{} 2$ and $ f(3) \equal{} 3$.
[i]Proof[/i]: By lemma 4, we may let $ f(2) \equal{} 2^b$ for some natural $ b$. Now, $ f(3) \plus{} f(1) \sim f(3 \plus{} 1)$, which is a power of 2. Hence, $ f(3) \plus{} 1$ must be a power of 2, so $ f(3) \equal{} 2^a \minus{} 1$ for some positive integer $ a$. Also, $ 2^b \plus{} 1 \equal{} f(2) \plus{} f(1) \sim f(3) \equal{} 2^a \minus{} 1$, that is, $ 2^b \plus{} 1$ and $ 2^a \minus{} 1$ have the same set of prime factors.

If $ b \equal{} 3$, then $ 2^b \plus{} 1 \equal{} 9$, so $ 2^a \minus{} 1$ must be a power of 3 greater than 1. Hence, $ 2^a \minus{} 1 \equal{} 3^y$, for some integer $ y$. $ y > 0$, so taking this mod 3 reveals that $ a$ is even. Consequently, $ (2^{\frac{a}{2}} \minus{} 1)(2^{\frac{a}{2}} \plus{} 1) \equal{} 3^y$. Therefore, $ 2^{\frac{a}{2}} \equal{} 1$, giving $ a \equal{} 2$, so we must have $ a \equal{} 2$ in this case.

If $ b \neq 3$, then we shall show that $ a \equal{} 2b$. If $ a > 2b$, then by Zsigmondy's theorem, there exists some prime $ p$ such that the order of 2 modulo $ p$ is $ a$. If $ p | 2^b \plus{} 1$, then $ p | 2^{2b} \minus{} 1$. But then, $ 2b < a$, which contradicts the minimality of $ a$. If $ a < 2b$, then by Zsigmondy's theorem, there exists some prime $ p$ such that the order of 2 modulo $ p$ is $ 2b$. Hence, $ p | 2^{2b \minus{} 1} \equal{} (2^b \minus{} 1)(2^b \plus{} 1)$. $ p | 2^b \minus{} 1$ would contradict the minimality of $ 2b$, so we must have $ p | 2^b \plus{} 1$. If $ p | 2^a \minus{} 1$ as well, since $ a < 2b$, the minimality of $ 2b$ is contradicted. Hence, we must have that $ a \equal{} 2b$.

In this situation, we have that $ 2^b \plus{} 1$ and $ 2^{2b} \minus{} 1 \equal{} (2^b \plus{} 1)(2^b \minus{} 1)$ have the same prime factors, that is, $ 2^b \plus{} 1$ and $ 2^b \minus{} 1$ have the same prime factors. But if $ p | 2^b \minus{} 1$ and $ p | 2^b \plus{} 1$, $ p$ prime, then $ p | 2$; but $ 2 \not | 2^b \minus{} 1$, so we must have $ b \equal{} 1$. Consequentially, $ a \equal{} 2$. Hence, we may conclude that $ (a,b) \equal{} (2,1)$ or $ (a,b) \equal{} (2,3)$. In other words, $ f(3) \equal{} 3$ and $ f(2) \equal{} 2$ or $ f(2) \equal{} 8$.

Suppose for the sake of contradiction that $ f(2) \equal{} 8$. Then $ 11 \equal{} f(2) \plus{} f(3) \sim f(5) \sim f(4 \plus{} 1) \sim f(4) \plus{} f(1) \equal{} 2^c \plus{} 1$, for some natural $ c$ (since $ f(4)$ is a power of 2.) Hence, $ 2^c \plus{} 1$ is a power of 11. But $ 2^c \equal{} 11^z \minus{} 1$ for some integer $ z$ is impossible, since 5 divides $ 11^z \minus{} 1$, though it does not divide a power of 2. Therefore, we may conclude that $ f(2) \equal{} 2$, which completes the proof of this lemma.

[b]Lemma 6[/b] Let $ S_p$ be the set of all $ m$ such that $ f(m)$ is a multiple of $ p$, and let $ m_0$ be its smallest element (which, by the surjectivity of $ f$, necessarily exists). Then if $ n \in S_p$, then $ m_0 | n$.
[i]Proof[/i]: Write $ n \equal{} m_0q \plus{} r$, with $ r < m_0$. Assume for the sake of contradiction that $ r \neq 0$. Then $ p | f(n)$ implies that $ p | f(n \minus{} m_0) \plus{} f(m_0)$. Since $ p | f(m_0)$, we have $ p | f(n \minus{} m_0)$. We may repeat this until we get $ p | f(r)$. But $ r < m_0$, contradicting the minimality of $ m$. Hence, $ m_0 | n$, as desired.

[b]Lemma 7[/b] $ f$ is injective.
[i]Proof[/i]: Suppose that $ f(a) \equal{} f(b)$ for some natural $ a$ and $ b$, with $ a \leq b$. Then $ f(a \plus{} k) \sim f(a) \plus{} f(k) \equal{} f(b) \plus{} f(k) \sim f(b \plus{} k)$, for all natural $ k$. Suppose that $ a \plus{} k$ is prime. Let $ q$ be any prime factor of $ f(a \plus{} k)$, and let $ m_0$ be the smallest element in $ S_q$. By lemma 6, $ m_0 | a \plus{} k$. But $ a \plus{} k$ is prime, and $ m_0 \neq 1$, so $ a \plus{} k \equal{} m_0$. But $ q | f(a \plus{} k)$ implies that $ q | f(b \plus{} k)$, since the two functions share prime factors. Hence, $ b \plus{} k \in S_q$, so $ a \plus{} k \equal{} m_0 | b \plus{} k$, that is, $ a \plus{} k | b \minus{} a$ for all $ k$ such that $ a \plus{} k$ is prime. If $ b > a$, taking any prime $ p > b \plus{} a$ and setting $ k \equal{} p \minus{} a$ gives $ p | b \minus{} a$, meaning $ b \plus{} a < p \leq b \minus{} a$, which is a contradiction. Hence, $ a \equal{} b$, which completes our proof

[b]Lemma 8[/b] If $ q$ is any integer greater than 3, and $ n$ is an integer greater than 1, then $ q^n \minus{} 1$ has a prime factor that $ q \minus{} 1$ does not.
[i]Proof[/i]: Since $ q > 3$, $ q \neq 2$. If $ n \equal{} 2$ and $ q^2 \minus{} 1 \equal{} (q \minus{} 1)(q \plus{} 1)$ and $ q \minus{} 1$ have the same prime factors, $ q \plus{} 1$ and $ q \minus{} 1$ must have the same prime factors. But the only prime factor they could possibly share is 2 (as any factor would divide their difference), so $ q \plus{} 1$ and $ q \minus{} 1$ are both powers of 2. It follows trivially that $ q$ must equal 3, which contradicts our assumption that $ q > 3$. Now, because $ q, n > 2$, by Zsigmondy's theorem there exists a prime $ p$ such that the order of $ q$ modulo $ p$ is $ n$. Hence, $ p | q^n \minus{} 1$. If $ p | q \minus{} 1$, then the order of $ q$ modulo $ n$ must be 1, which contradicts our assumption that $ n > 1$. Hence, $ p \not | q \minus{} 1$, which completes the proof of this lemma.

------------------------------------------------------------------------------------------------------------

We shall proceed by strong induction to show that $ f(n) \equal{} n$ for all integers $ n$. The base case is covered in lemmas 2 and 5. Suppose now that there is some $ n \geq 3$ such that for all $ k$ between 1 and $ n$ inclusive, we have $ f(k) \equal{} k$. By Bertrand's postulate, there exists some prime $ q$ between $ n$ and $ 2n$ exclusive. It follows that $ n$ and $ q \minus{} n$ both lie between 1 and $ n$ inclusive, so $ f(q) \equal{} f(n \plus{} q \minus{} n) \sim f(n) \plus{} f(q \minus{} n) \equal{} q$, that is, $ f(q)$ is a power of $ q$, say, $ q^m$.

Because $ q < 2n$, $ q \plus{} 1 \leq 2n$. Hence, $ n$ and $ q \plus{} 1 \minus{} n$ both lie between 1 and $ n$ inclusive, so $ f(q \plus{} 1) \equal{} f(n \plus{} q \plus{} 1 \minus{} n) \sim f(n) \plus{} f(q \plus{} 1 \minus{} n) \equal{} q \plus{} 1$, so $ f(q \plus{} 1)$ and $ q \plus{} 1$ share the same prime factors. On the other hand, $ f(q \plus{} 1) \sim f(q) \plus{} 1 \equal{} q^m \plus{} 1$, so $ q \plus{} 1$ and $ q^m \plus{} 1$ must have the same prime factors. Suppose for the sake of contradiction that $ m > 1$. Then $ 2m > 2$, and clearly $ q \neq 2$, so by Zsigmondy's theorem there exists some prime $ p$ such that $ 2m$ is the order of $ q$ modulo $ p$. Hence, $ p | q^{2m} \minus{} 1 \equal{} (q^m \minus{} 1)(q^m \plus{} 1)$. It cannot divide $ q^m \minus{} 1$, since $ 2m$ was chosen to be minimal, so $ p | q^m \plus{} 1$. But $ q \plus{} 1$ and $ q^m \plus{} 1$ have the same prime factors, so $ p | q \plus{} 1$ as well, giving $ p | q^2 \minus{} 1$. It follows that $ 2m$, the order, must therefore divide 2. Therefore, $ m \equal{} 1$, so our assumption that hat $ m \neq 1$ is false. We may conclude from here that $ f(q) \equal{} q$.

If $ q \equal{} n \plus{} 1$, then we are done. Otherwise, we may suppose that $ q > n \plus{} 1$. Consider the integer $ q \minus{} 1$. Note that $ n < q \minus{} 1 < 2n$ (since we assumed that $ q > n \plus{} 1$), so $ n$ and $ q \minus{} 1 \minus{} n$ lie between 1 and $ n$ inclusive. Hence, $ f(q \minus{} 1) \equal{} f(n \plus{} q \minus{} 1 \minus{} n) \sim f(n) \plus{} f(q \minus{} 1 \minus{} n) \equal{} n \plus{} q \minus{} 1 \minus{} n \equal{} q \minus{} 1$. But $ f(q \minus{} 1) \plus{} f(1) \sim f(q) \equal{} q$, so $ f(q \minus{} 1) \equal{} q^j \minus{} 1$ for some positive integer $ j$. Hence, $ q \minus{} 1 \sim q^j \minus{} 1$, so they have the same prime divisors. Note that $ q > n \plus{} 1 \geq 4 > 3$, so by lemma 8, we must have that $ j \equal{} 1$. Hence, $ f(q \minus{} 1) \equal{} q \minus{} 1$.

If $ q \equal{} n \plus{} 2$, then we are done. Otherwise, we may suppose that $ q > n \plus{} 2$. It remains to show that $ f(n \plus{} 1) \equal{} n \plus{} 1$. By lemma 7, $ f(n \plus{} 1) < n \plus{} 1$ would contradict the injectivity of $ f$, so $ f(n \plus{} 1) \geq n \plus{} 1$. Suppose for the sake of contradiction that $ f(n \plus{} 1) > n \plus{} 1$. Let $ f(n \plus{} 1) \equal{} n \plus{} 1 \plus{} z$, where $ z$ is some nonnegative integer. Then $ 1 \leq q \minus{} n \minus{} 2, q \minus{} n \minus{} 1 \leq n$ (since $ n \plus{} 2 < q < 2n$). From this, it can be seen that $ q \plus{} z \equal{} f(n \plus{} 1) \plus{} f(q \minus{} n \minus{} 1) \sim f(n \plus{} 1 \plus{} q \minus{} n \minus{} 1) \equal{} f(q) \sim q$ and that, $ q \plus{} z \minus{} 1 \equal{} f(n \plus{} 1 \plus{} q \minus{} n \minus{} 2) \equal{} f(q \minus{} 1) \sim q \minus{} 1$. From $ q \plus{} z \sim q$, we have that $ q \plus{} z \equal{} q^i$ for some natural $ i > 1$ (or else $ z \equal{} 0$.) But then, we have that $ q^i \minus{} 1 \equal{} q \plus{} z \minus{} 1 \sim q \minus{} 1$. As before, $ q > n \plus{} 1 \geq 4 > 3$, so by lemma 8, we have that $ i \equal{} 1$, so $ z \equal{} 0$. Hence, $ f(n \plus{} 1) \equal{} n \plus{} 1$, which completes our proof. [/hide]

[hide="Solution"]Denote the relation $ p|a \iff p|b$ for all prime $ p$ as $ a\sim b$.

Lemma 1: $ f$ is bijective.
Proof: Suppose $ f(a) \equal{} f(a \plus{} m)$ for some $ a, m$. Then for any $ b > a$, $ f(b) \sim f(a) \plus{} f(b \minus{} a) \sim f(a \plus{} m) \plus{} f(b \minus{} a) \sim f(b \plus{} m)$. Thus for any $ x, y > a$ with $ x \equiv y \pmod m$, $ f(x) \sim f(y)$. But this means the set of prime divisors of $ \{f(n)\}_{n \in \mathbb{N}}$ is finite, which contradicts the surjectivity of $ f$.

Lemma 2: $ p|f(a), f(b) \iff p|f(\text{gcd}(a, b))$ for all prime $ p$.
Proof: Since $ f(kn) \sim f(n) \plus{} f((k \minus{} 1)n)$, it follows inductively that $ p|f(n) \Rightarrow p|f(kn)$ for all $ k \in \mathbb{N}$. By Bezout's identity, there exists $ x, y \in \mathbb{N}$ such that $ ax \minus{} by \equal{} \pm \text{gcd}(a, b)$. WLOG $ ax \minus{} by \equal{} \text{gcd}(a, b)$. Now, if $ p|f(a), f(b)$, then $ p|f(ax), f(by)$. Since $ f(ax) \sim f(by) \plus{} f(ax \minus{} by)$, $ p|f(ax \minus{} by)$ i.e. $ p|f(\text{gcd}(a, b))$. If $ p|f(\text{gcd}(a, b))$, then $ p|f(a), f(b)$ since $ \text{gcd}(a, b)|a, b$.

Lemma 3: $ f(x) \equiv f(y) \pmod p \iff x \equiv y \pmod p$ for all prime $ p$.
Proof: Let $ m_p$ be the smallest $ n$ such that $ p|f(n)$. By Lemma 2, $ p|f(n) \iff m_p|n$. WLOG $ y > x$. Take $ a > x$ with $ m_p|a$. Note $ m_p|y \minus{} x \iff p|f(y \minus{} x) \iff p|f(y \minus{} x \plus{} a) \iff p|f(y) \plus{} f(a \minus{} x)$. Since $ p|f(a)$, $ p|f(x) \plus{} f(a \minus{} x)$, so $ p|f(y) \plus{} f(a \minus{} x) \iff p|f(y) \minus{} f(x)$. Thus $ f(x) \equiv f(y) \pmod p \iff x \equiv y \pmod {m_p}$. In the other words, there is a bijection between the residue classes of $ \mathbb{Z}_{p}$ and $ \mathbb{Z}_{m_p}$, so $ p \equal{} m_p$, as desired.

By Lemma 3, for all prime $ p$, since $ x \not\equiv x \plus{} 1 \pmod p$, $ f(x) \not\equiv f(x \plus{} 1) \pmod p$. Thus $ p \nmid f(x \plus{} 1) \minus{} f(x)$ for all prime $ p$, which means $ f(x \plus{} 1) \minus{} f(x) \equal{} \pm 1$. Suppose $ f$ decreases at some point, then it must keep decreasing indefinitely. Otherwise, if it starts increasing at $ k$, then $ f(k \plus{} 1) \minus{} f(k) \equal{} 1$ and $ f(k) \minus{} f(k \minus{} 1) \equal{} \minus{} 1$, giving $ f(k \minus{} 1) \equal{} f(k \plus{} 1)$, which contradicts the bijectivity of $ f$. But then $ f$ will eventually become negative, contradiction. Hence, $ f(x \plus{} 1) \minus{} f(x) \equal{} 1$ for all $ x$. Since $ f(x)$ is surjective, it follows that $ f(1) \equal{} 1$ which means $ f(x) \equal{} x$ for all $ x$. QED
[/hide]

[hide="Alternately"]This solution does not require surjectivity. Lemma 2 and 3 are proven as before.

Lemma 4: $ f(p) \equal{} p$ for all prime $ p$ of the form $ 4k \plus{} 1$.
Proof: Let $ p$ be any prime of the form $ 4k \plus{} 1$. From Lemma 3, we have that $ f(n) \sim n$, so $ f(1) \equal{} 1$ and $ f(p) \equal{} p^a$ for some $ a$. Furthermore, we also have $ f(m) \plus{} f(n) \sim m \plus{} n$. Taking $ m \equal{} p, n \equal{} 1$, we get $ p \plus{} 1 \sim p^a \plus{} 1$. Note $ p \plus{} 1 \equiv p^a \plus{} 1 \equiv 2 \pmod 4$, so $ 2\parallel{}p \plus{} 1, p^a \plus{} 1$. Suppose $ r|p \plus{} 1$ for some prime $ r \neq 2$, then $ r|p^a \plus{} 1 \Rightarrow r|( \minus{} 1)^a \plus{} 1$, so $ a$ is odd. Denote $ v_q(x)$ to be the exponent of prime $ q$ in the factorization of $ x$. By Lifting the Exponent, for any odd prime $ r|p \plus{} 1$, $ v_r(p^a \plus{} 1) \equal{} v_r(p \plus{} 1) \plus{} v_r(a)$ (valid since $ a$ is odd). Since $ p \plus{} 1 \sim p^a \plus{} 1$, $ p^a \plus{} 1 \equal{} 2\cdot \prod_{r|p \plus{} 1, r\neq 2} r^{v_r(p^a \plus{} 1)} \equal{} 2\cdot \prod_{r|p \plus{} 1, r\neq 2} r^{v_r(p \plus{} 1)} \cdot r^{v_r(a)} \leq (p \plus{} 1)a$.
We claim $ p^a \plus{} 1 \geq (p \plus{} 1)a$ with equality if and only if $ a \equal{} 1$. Note $ p^a \plus{} 1 \equal{} (p \plus{} 1)a$ for $ a \equal{} 1$. Suppose the statement true for some $ a \geq 1$. Note $ p > 3$, so $ 2p > p \plus{} 1 \Rightarrow (p \minus{} 1)p^a > p \plus{} 1 \Rightarrow p^{a \plus{} 1} \minus{} p^a > p \plus{} 1$. Adding the last strict inequality to $ p^a \plus{} 1 \geq (p \plus{} 1)a$, we get $ p^{a \plus{} 1} \plus{} 1 > (p \plus{} 1)(a \plus{} 1)$, which completes the induction. Hence, $ a \equal{} 1$, as desired.

To finish the proof, again note $ p \nmid f(x \plus{} 1) \minus{} f(x)$ for all prime $ p$, which means $ f(x \plus{} 1) \minus{} f(x) \equal{} \pm 1$. Then for any prime $ q$ of the form $ 4k \plus{} 1$, $ f(q) \minus{} f(1) \leq q \minus{} 1$ with equality if and only if $ f(x \plus{} 1) \minus{} f(x) \equal{} 1$ for $ 1\leq x\leq q \minus{} 1$. By Lemma 4, $ f(q) \minus{} f(1) \equal{} q \minus{} 1$, so $ f(x \plus{} 1) \minus{} f(x) \equal{} 1$ for $ 1\leq x\leq q \minus{} 1$. Since there are arbitrarily large primes of the form $ 4k \plus{} 1$, this implies $ f(x \plus{} 1) \minus{} f(x) \equal{} 1$ for all $ x$, so $ f(x) \equal{} x$. QED

Edit: this solution still uses the surjectivity condition, since Lemma 3 used it.
[/hide]

i think for any prime p and numbers a and b , p|f(a)-f(b) if and only if p|a-b... In fact , consider natural number c so that p|a+c , then p| f(a+c) .Indeed p|f(a)+f(c) , so p|f(b)+f(c) . thus p|f(b+c) so p|b+c. indeed p|a-b. now if p|a-b then coose c such that p|a+c . So p|f(a+c)  . Then p|f(a)+f(c) . and p|b+c then p|f(b)+f(c) . Indeed p|f(a)-f(b) . Thus |f(a)-f(a-1)|=1 since a-(a-1)=1 . |f(a)-f(a-2)|=2^k since a-(a-2)=2. so we can see f(a) and f(a-2)  are different . thus we can see f(n)=n easily . here is , i proved f(1)=1 at first...

(Due to me & [url=http://www.artofproblemsolving.com/Forum/memberlist.php?mode=viewprofile&u=86115]mahi[/url])
[hide="Solution"]Very easy to prove $f(1)=1$.
Now fix $p$. Suppose $k$ is the least integer such that $p|f(k)$. (Such a $k$ exists because of surjectivity) Suppose $a,b<k$ such that $f(a)\equiv f(b)\pmod p$. We claim $a=b$. Indeed, assume $a>b$. So $0\leq a-b<k$. And $p|f(a)+f(k-a)\implies p|f(b)+f(k-a)\implies p|f(k-(a-b))$ a contradiction unless $a=b$.

So $f(1),f(2),...,f(k)$ are incongruent mod $p$. Hence we must have $k\leq p$. (Otherwise, from pigeon hole principle, there will be two congruent elements.)

Note that $f(r)\equiv f(k+r)\equiv \cdots\equiv f(kx+r)\pmod p\quad (1)$
So if $k<p$, then $\{f(1),f(2),...,f(k)\}$ is not a complete residue class of $p$. And due to (1), it will imply $\{f(n)\forall n\in N\}$ is not a complete residue class of $p$. This is a contradiction to surjectivity. So we must have $k=p$.

Now we'll prove $p|a\Longleftrightarrow p|f(a)$
The if part is obvious because $p|f(kx)=f(px)$. So, we'll prove the only if part. Let $a=px+r$. Note that $p|f(px+p)\implies p|f(a)+f(p-r)\implies p|f(p-r)$ a contradiction unless $r=0$.

From this lemma this is obvious that $f(p)=p^m$. Now we'll prove $m=1$. For a prime $q$,
$q|p+1\Longleftrightarrow q|f(p+1)\Longleftrightarrow q|p^m+1$
So $p+1$ and $p^m+1$ has same set of prime divisors. Then $m$ must be odd. Because if $m$ is even, then $\gcd(p+1,p^m+1)|2$.
Now notice that, if $q$ is odd, then from LTE $v_q(m(p+1))=v_q(p^m+1)$. And also $v_2(p+1)=v_2(p^m+1)$. Hence $m(p+1)=p^m+1$. Clearly, this is true only if $m=1$ i.e. $f(p)=p$.

Now we prove $f(n)=n$ for all positive integers. Suppose $p$ is a prime not dividing $n$. Then there exists a prime(actually infinitely many) of the form $q=pi-n$. So $p|f(pi)\implies p|f(q)+f(n)\implies p|pi-n+f(n)\implies p|f(n)-n$. Therefore infinitely many primes are dividing $f(n)-n\implies f(n)-n=0\implies f(n)=n\forall n\in \mathbb N$.[/hide]

[hide]
Throughout the solution, unless otherwise specified, $p$ will denote a prime, and all other variables will denote positive integers.

First, a trivial observation. By setting $m=n,$ we see that $p \mid f(2m) \iff p \mid 2f(m).$ By induction, it follows that $p \mid f(km) \iff p \mid kf(m)$ for all $k \in \mathbb{N}.$

[b]Claim 1:[/b] $f(1)=1$

[b]Proof:[/b] Suppose some prime $p$ divides $f(1).$ Then, for all $n \in \mathbb{N},$ $p$ divides $f(n)$ iff $p$ divides $f(n-1)+1,$ i.e. iff $p$ divides $f(n-1),$ so by induction we see that $p$ divides $f(n)$ for all $n,$ so no non-multiples of $p$ can be in the range of $f,$ contradicting its surjectivity. $\blacksquare$

[b]Claim 2:[/b] $f(x) = f(y) \iff x=y$

[b]Proof:[/b] 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.$ Take any $j>x$ and note that $p \mid f(j) \iff p \mid f(j-x) + f(x) \iff f(y) +  f(j-x) \iff p \mid f(y-x+j).$ For any $n,$ by the division algorithm, write $n= q(y-x) + r,$ where $1 \leq r  \leq y-x.$ By induction, we see that for all $q,$ $p \mid q(y-x)+r \iff p \mid r,$ so the set of prime divisors of $f(x)$ is equal to the set of prime divisors of $\{f(1), f(2), \cdots , f(y-x)\},$ contradicting the surjectivity of $f(x).$ $\blacksquare$

Let $g(n)$ denote the smallest positive integer such that $n \mid f(g(n)).$

[b]Claim 3:[/b] $p \mid g(p)$

[b]Proof:[/b] Suppose $g(p) = qp+r,$ where $1 \leq r \leq p$ by the division algorithm. Then, $p \mid f(g(p)) \iff p \mid f(qp+r) \iff p \mid f(r),$ contradicting the minimality of $g(p).$ $\blacksquare$

[b]Claim 4:[/b] $|f(n+1) - f(n)| = 1$

[b]Proof:[/b] Suppose some prime $p$ divides $f(n+1)-f(n).$ Take a $j$ such that $j> n+1$ and $g(p) \mid j.$ Note that $p \mid f(j),$ so
\[p \mid f(n+1)-f(n) \iff p \mid f(n+1) + f(j-n) \\ \iff p \mid f(j+1) \iff p \mid f(1)=1,\]
not possible. $\blacksquare$

We shall now show by induction that $f(n)=n \quad \forall \ n \in \mathbb{N}.$ The base case $n=1$ has already been shown. Also, by claim 4, $f(2) = 1 \pm 1.$ Since $f(2)$ is positive, $f(2)=2.$ Now suppose it is true for $n= 1, 2, \cdots , k-1, k,$ so $f(n)=n$ for all $n \leq k.$ By claim 4, $f(k+1) = f(k) \pm 1.$ However, if $f(k+1) = f(k)-1,$ $f(k+1)= f(k-1),$ contradicting the bijectivity of $f.$

In conclusion, the only solution is $\boxed{f(x)=x}.$
[/hide]

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$.

[quote="AnonymousBunny"]
[hide]Throughout the solution, unless otherwise specified, $p$ will denote a prime, and all other variables will denote positive integers.

First, a trivial observation. By setting $m=n,$ we see that $p \mid f(2m) \iff p \mid 2f(m).$ By induction, it follows that $p \mid f(km) \iff p \mid kf(m)$ for all $k \in \mathbb{N}.$

[b]Claim 1:[/b] $f(1)=1$

[b]Proof:[/b] Suppose some prime $p$ divides $f(1).$ Then, for all $n \in \mathbb{N},$ $p$ divides $f(n)$ iff $p$ divides $f(n-1)+1,$ i.e. iff $p$ divides $f(n-1),$ so by induction we see that $p$ divides $f(n)$ for all $n,$ so no non-multiples of $p$ can be in the range of $f,$ contradicting its surjectivity. $\blacksquare$[/hide]
[b]Claim 2:[/b] $f(x) = f(y) \iff x=y$

[b]Proof:[/b] 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$

[hide]Let $g(n)$ denote the smallest positive integer such that $n \mid f(g(n)).$

[b]Claim 3:[/b] $p \mid g(p)$

[b]Proof:[/b] Suppose $g(p) = qp+r,$ where $1 \leq r \leq p$ by the division algorithm. Then, $p \mid f(g(p)) \iff p \mid f(qp+r) \iff p \mid f(r),$ contradicting the minimality of $g(p).$ $\blacksquare$

[b]Claim 4:[/b] $|f(n+1) - f(n)| = 1$

[b]Proof:[/b] Suppose some prime $p$ divides $f(n+1)-f(n).$ Take a $j$ such that $j> n+1$ and $g(p) \mid j.$ Note that $p \mid f(j),$ so
\[p \mid f(n+1)-f(n) \iff p \mid f(n+1) + f(j-n) \\ \iff p \mid f(j+1) \iff p \mid f(1)=1,\]
not possible. $\blacksquare$

We shall now show by induction that $f(n)=n \quad \forall \ n \in \mathbb{N}.$ The base case $n=1$ has already been shown. Also, by claim 4, $f(2) = 1 \pm 1.$ Since $f(2)$ is positive, $f(2)=2.$ Now suppose it is true for $n= 1, 2, \cdots , k-1, k,$ so $f(n)=n$ for all $n \leq k.$ By claim 4, $f(k+1) = f(k) \pm 1.$ However, if $f(k+1) = f(k)-1,$ $f(k+1)= f(k-1),$ contradicting the bijectivity of $f.$

In conclusion, the only solution is $\boxed{f(x)=x}.$ [/hide]
[/quote]

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.

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!

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}$.

[b]Lemma[/b]: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}$.

[i]Proof[/i]: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.

I love these NT Fe's :love:
[quote=ISL 2007 N5]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$.
[/quote]
Since $2|2f(n) $ for all $n$ , we have that $2|f(2n)$.
[b][color=#f00]CLAIM 1:[/color][/b] For an odd prime $p$ ,$p|f(n)\iff p|n$
[hide=proof]
Let , for an odd prime $p$ , $a$ is the smallest natural number such that $p|f(a)$.Then $p|f(2a) \implies p|f(3a) \cdots$(this actually tells us that $f(1)=1$)
Now , FTSOC , let , $\exists k $ such that $p|f(k)$ and $na<k<(n+1)a$. But now , this would imply that $p|f((n+1)a-k)$ contradicting the minimality of $a$.Thus $p|f(n) \iff a|n$.
For the proof of this claim , it is only left to prove that $a=p$.First , let $a>p$.Then $\exists x,y <a$ such that $f(x)\equiv f(y) \pmod{p}$.Then $$p|f(x)+f(a-x)\implies p|f(y)+f(a-x) \implies p|f(a+y-x) \implies a|y-x $$ a contradiction.
[b][color=#960000]SUB-CLAIM 1.1: [/color][/b]$f(a+n) \equiv f(n) \pmod{p}$
[hide=proof 1.1]$$p|f(a+n)+f(k)\implies a|k+n \implies p|f(k+n) \implies p|f(n)+f(k)$$ [/hide]
This means that $\{f(1),f(2),...f(a-1\}$ must constitute a complete residue class mod $p$.Hence $a\geq p \implies a=p$.Hence claim 1 proved.:)

[/hide]
[b][color=#B45F06]CLAIM 2:[/color][/b]$f(p)=p$ for all odd primes $p$.
[hide=Proof]Let , $f(p^a)=p$.Then $$q|p^a+1 \implies q|f(p^a)+f(1) \implies q|p+1$$a clear contradiction by Zsigmondy's( avoiding restrictions) .

[/hide]
Now , taking a $b$ such that $f(b)=b$, we can restate the problem as follows:$$p|f(a)+b \iff p|f(a+b) \iff p|a+b \implies p|f(a)-a$$Now , varying $b$ , $\{a+b\}$ has infinitely many prime divisors, and thus $\boxed{f(a)-a=0}$

[hide=Solution]
Since $2\mid f(1)+f(1)$, this means that $f(2)$ is a power of $2$. Similarly, $f(4)$ is also a power of two. Then, $f(3)+1$ is a power of $2$. Let $f(3)+1=2^a$. Then, $f(3)=2^a-1$. If $f(2)=2^b$, then $2^b+1$ and $2^a-1$ have the same prime factors. By Zsigmondy's Theorem, there exists a prime such that $2^b\equiv-1\pmod p$ and $b$ is the smallest number that satisfies this unless $b=3$. Therefore, if $b\neq3$, then the order of $2$ mod $p$ is $2b$, so $2b\mid a$. However, this means that $2^{2b}-1\mid2^a-1$, so every prime factor of $2^{2b}-1$ must divide $2^b+1$. However, this is a contradiction for any prime factor of $2^b-1$ since $\gcd(2^b-1,2^b+1)=1$. Therefore, $b=1$ or $b=3$, so $2^a-1$ must be a power of $3$ greater than $1$. By Zsigmondy's Theorem, this is only possible for $a=2$, so $f(3)=3$. If $f(2)=8$, then $f(5)$ must be a power of $11$. However, since $f(4)+1$ must be a power of $11$, this means that $5\mid f(4)$, which is impossible. Therefore, we have $f(1)=1$, $f(2)=2$, $f(3)=3$, and $f(4)=4$.

Now, we will show that if $f(i)=i$ for $i\in\{1,2,3,\ldots,2^a\}$, then $f(i)=i$ for $i\in\{1,2,3,\ldots,2^{a+1}\}$. Let $n=2^{a+1}-b$ with $1\leq b<2^a$. Then, $f(n)+f(b)$ is a power of $2$, so since $f(b)=b$, this means that $f(n)=2^c-b$. Therefore, since $f(n)+f(b-1)$ and $f(2^{a+1}-1)$ have the same prime divisors, this means that $2^c-1$ and $2^{a+1}-1$ have the same prime divisors. Therefore, by Zsigmondy's Theorem, this means that $c=a+1$, so $f(n)=2^{a+1}-b=n$. Now, since $f(2^{a+1}+1)$, $2^{a+1}+1$, and $f(2^{a+1})+1$ have the same prime divisors, suppose that $f(2^{a+1})=2^m$. Then, $2^{a+1}+1$ and $2^m+1$ have the same prime divisors, so if $m\neq a+1$, then we must have $\{a+1,m\}=\{1,3\}$ by Zsigmondy's Theorem. However, since $f(2)=2$, we must have $a=2$ and $m=3$, so $f(8)=2$. However, this means that $f(7)+f(3)=10$ and $f(8)+f(2)=4$ have the same prime divisors, which is a contradiction. Therefore, this means that $f(2^{a+1})=2^{a+1}$, which means that $\boxed{f(n)=n}$ for all $n$.

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.

[u][b]Claim 1:[/b][/u] $p\mid f(x)\iff k\mid x.$
[i]Proof.[/i] 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$

[b][u]Claim 2:[/u][/b] $k=p.$
[i]Proof.[/i] 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$

[b][u]Claim 3:[/u][/b] $f(x)\equiv f(y)\iff x\equiv y.$
[i]Proof.[/i] 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$

[b][u]Claim 4:[/u][/b] $f(x)=x.$
[i]Proof.[/i] 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$

[quote=Physicsknight][u][b][color=#f00]Answer [/color][/b][/u]
 $f (n)=n\forall n\in\mathbb N$

[u][b][color=#00f]Solution [/color][/b][/u]

[u][b][color=#f00]Claim 1-[/color][/b][/u] $f (n)=n $
[u][b][color=#00f]Proof-[/color][/b][/u] $\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$.

[u][b][color=#f00]Claim 2- [/color][/u][/b] $f (0)=0$

[u][b][color=#00f]Proof-[/color][/b][/u] $f (0)=2af (0) $ for $n=m=0$. If $f\ne 0$ then $a=\tfrac 12$. Since $a$ is an integer, $f (0)=0$.
[u][b][color=#f00]Claim 3-[/color][/b][/u] $f (n+m)=a(f (n)+f (m)) $.

[u][b][color=#00f]Proof-[/color][/b][/u] 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.[/quote]

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

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.

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.

[hide=Solution] Firstly, notice that $f(1)=1$, otherwise take a prime divisor $p \mid f(1)$ and notice that $p \mid f(n)$ for all $n$, absurd as the function is surjective. Now, we will prove that $f$ is injective and $|f(n+1)-f(n)|=1$ which will instantly imply that $f(n)=n$ for all $n$.

If $f(m)=f(n)$, take some large prime $p$ and notice that the injectivity implies that there exists $k$, such that $p \mid f(n)+f(k)=f(m)+f(k)$, so $p \mid f(m+k), f(n+k)$. Suppose WLOG that $m>n$; then since $m+k=(m-n)+(n+k)$, we get $p \mid f(m-n)$, contradiction for large enough $p$, so $m=n$.

If $p \mid f(n+1)-f(n)$, then similarly by the injectivity we obtain that there is a positive integer $k$, such that $p \mid f(n+k+1),f(n+k)$.  As we saw above, this implies $p \mid f(1)$, contradiction, so we are done.

$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.

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$.

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:

[b]Remark:[/b] original proof was a bit off, fixed now

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$

My first N5 :D  :D
[hide=Incomplete, Badly written ]We will prove by induction. It is easy to see f(1) = 1 . Assume it is true for n.
The primes which will divide f(n) will also divide n because  $p \mid n \iff  p \mid f(n)$. Let p be  prime that divides n
It is easy to see that $v_p(f(n)) \geq v_p(n)$  which $\implies n \mid f(n)$
FTSOC Assume there exist a prime p such that $v_p(f(n)) > v_p(n)$ Let $v_p(n)=k and v_p(f(n))=k+m$. If $p^k+m < n$, it is easy to see we are done.The other case is also easy to do. [/hide]
[hide=remarks]I have solved this problem, but its writeup is too annoying(I am bored to write it :P [/hide]
Basically a bit of casework solves this problem

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)$.

-----

[b][color=#f00]Claim 1:[/color][/b] $\operatorname{rad}(f(2^e)) = 2$ for all integers $e \ge 1$.

[i]Proof:[/i] 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$

-----

[b][color=#f00]Claim 2:[/color][/b] We have $f(x)=x$ for $x \le 4$.

[i]Proof:[/i] $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:

[list]
    [*] 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$
[/list]

-----

[b][color=#f00]Claim 3:[/color][/b] If $\operatorname{rad} (2^x-1) = \operatorname{rad} (2^y-1)$ or $\operatorname{rad} (2^x+1) = \operatorname{rad} (2^y+1)$

[i]Proof:[/i] 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.

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}$

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:
[list]
[*] $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$.
[/list]

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}$:
[list]
[*] 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$
[/list]


group theory
abstract algebra
superior algebra
superior algebra unsolved

Let $ H$ and $ K$ be subgroups of a finite group $ G$.  Is it true that for $ HK$ to be a subgroup of $ G$, both $ H$ and $ K$ must be normal?  Or does it suffice for one of them to be normal?

For $ KH$ to be a subgroup, it's necessary and sufficient that $ KH\equal{}HK$.

Actually, we could have neither of them normal, as long as ZetaX's condition is met. For example, $ A_5$ can be expressed as $ A_4H$, where $ H\equal{}<(12345)>$. But neither $ A_4$ nor $ H$ are normal in $ A_5$.

If $ H,K$ intersect only in the identity, then $ HK$ is the direct product if $ H,K$ are normal and a semidirect product if $ H$ is normal.

So if we know that $ H$ and $ K$ are subgroups of $ G$ and that $ \left|G\right|\equal{}\left|HK\right|$, we can say that $ G\equal{}HK$ by the closure of $ G$, right?

Yes, and you can replace $ HK$ with any subset $ S$ of $ G$ as well (this all assumes that $ G$ is finite, but if not then what does $ |G|$ mean?).

No $ H$ and $ K$ do not even have to be normal for $ HK$ to be a subgroup. All we need is that $ khk^{\minus{}1} \in H$ for all $ h\in H$ and $ k\in K$.


Suppose (p,q) = 1, (p,10)=1 and (q,10)=1. if 1/p has period r and 1/q has period s find the period of 1/pq.

This is the third time this problem has been posted in the last two days:

[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=276131[/url]
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=276372[/url]

Obviously something is up.  Is this problem from a contest?  If so, it shouldn't be posted.

I posted it when I saw it was unanswered on other internet fora.

What other internet forum? Post a link to it.


Salam be hameye barobach Iran
Come to this link and Vote.
http://www.mathlinks.ro/Forum/index.php?f=387

chiniha az bacheggi kheili soalhaye saate baalaa migiran.  Fekr konam chiniha beberand.  Vali, age iraniha bebarand khoobeha... :)

Masoud Zargar

baro bach,
mitoonin soal haye rooz e avale IMO o ro inja bebinind:
http://imo2006.dmfa.si/problems-day1-en.pdf

soal e 1 maskharas!!!
soal e 2 ham asooneh.
soal e 3 tanha soal e khoob e rooz e aval e. (man dar ovardam: M=(9\sqrt{2})/32 ~~3 saaat tool keshid ta halesh kardam :) )

[quote="Omid Hatami"]Hamin alaan ba Nima sohbat kardam, migoft ke emtehan emsal kheili sakht boode va ziad ham khoob nadadand :( vali migoft emtehan badak nashode va hanooz hichi maaloom nist.[/quote]

khoda vakili,

ehtemalan hamoon tor keh goftam, talafisho rooze dovvom dar avordan,

kol e sola ha va rah e hal ha ro mitoonin inja bebinin:

http://imo2006.dmfa.si/imo2006-solutions.pdf

[quote="payman_pm"][quote="Omid Hatami"]Hamin alaan ba Nima sohbat kardam, migoft ke emtehan emsal kheili sakht boode va ziad ham khoob nadadand :( vali .[/quote]
sathe soalhaye emsal dar moghayese ba parsal kheili taghyeer nakardeh
.parsalam keh migoftan asoon bood pas ghaedatan emsal ham bayad
asoon bashe!!?[/quote]
Sharayete metehane jahani kheili fargh dare, soalhayi ke be nazare to asoon miyad shayad oona natoonan hal konand. Baraye man chenin ettefaghi pish oomad, vaghti az mosabeghat bargashtam ye seri adam goftand ke chera emtehan ra intori dadi.

Salam!

hala joda az in harfa, kasi midune bacheha che kardan?

Omid, ba Nima dige sohbat nakardi?

khob, zaheran tebghe akhbare reside, hame bacheha 21 ro migiran va Naser Talebi Zade ham ehtemalan tala mishe, Jalil mige man bronze misham

afarin bacheha  :)

age hame 21 beshan fekr nakonam bronze dashteh bashim! :wink:

**side note:
intor ke man shenidam, faghat yek nafar as china 42 shod.

va hich cas az tim e USA soal e 3 ro hal nakard.

be ehtemal e 90%:

Chin avale
Korea 2vom.
Germany 4th.

Iran ya 5 ya 6.

Salam,

emsal Iran ba 3 tala va 3 noghre 8om shod ! hooorraaah

:first: :first: :first:
Nima..........28
Mohammad.19
Arman........23
Jalil............19
Naser.........28
Jaber..........28
:first: :first: :first:

jaleb ine ke parsal ba 2 tala va 4 noghre 4om shodim! ehtemalan dalilesh ine ke emsal, 5 ta nomreye labe marzi dashtim  :D  . albate jury ham komakemun kard, dastesh dard nakone!!

nokteye dige inke az sale 2003 ke 0 tala gereftim, har sal darim 1 tala bishtar migirim!

khoobe ke bacheha sale dige bishtar havasehuno jam konan va az soalaye asoon nomreye kamel ro begiran  :wink:


I dont think I understoon the question right.

9+9+3 = 21?

[quote="Silverfalcon"]In a paper, following numbers are written. Circle 3 numbers so that they add up to 21.

[code]333
666
999[/code][/quote]

I don't get the problem. Can I choose 6, 6, 9?

[quote="Silverfalcon"]Circle them without taking your pencil off.[/quote]
I still don't get the problem. Is it just me? :blush:
Can you make it more clear?

[quote="Geehoon"]This is how I understood the question.

There are nine lattice points. ($0\le x \le 2, 0\le y \le 2$)
each lattice points are assigned value according to their y coordinates, 9 for y=0, 6 for y=1, and 3 for y=2.

Draw a circle so that three of those lattice points are on the circle, and the values add up to 21.[/quote]
If this is the case, we can choose second 3, first 9, third 9.

[quote="probability1.01"]I think you can do two 6's and a 9.[/quote]
Oh. It's also possible. We can pick second and third 6 and first 9. :)

No, circle simply means draw.

The shape doesn't have to be circle. Maybe I should said draw lines around three numbers without taking your pencil off so that their sum is 21.

Ummm... that's also not hard.  You can make it enclose any three numbers...

Ok now the question is not so hard[hide]6+6+9=21[/hide]


modular arithmetic
Additive Number Theory

Prove that every integer $n \ge 12$ is the sum of two composite numbers.

is the problem such easy or am i misunderstanding it?
if we have $2|n$ or $3|n$ we can write $n=6+(n-6)$. because of $2|n$ or $3|n$ we have $2|(n-6)$ or $3|(n-6)$ with $n-6\geq 6$ -> finished.
if not $2|n$ or $3|n$ we get $n\equiv 1 , 5 \pmod{6}$. if $n\equiv 1$ we set $n=4+(n-4)$, $3|(n-4)$ -> done. if $n\equiv 5$ we set $n=8+n-8$, $3|(n-8)$, $n-8\geq 4$ -> done too.
so we have managed all cases and found a solution.

Naphthalin

For $ n$ even it is already proved as $ n \equal{} 2m ,m\geq6$
$ \equal{} (2m \minus{} 4) \plus{} 4, (2m \minus{} 4)\geq8$
which is the sum of two composite numbers.

For $ n$ odd we have $ n \equal{} 2m \plus{} 1 , m\geq6$
$ \equal{} (2m \minus{} 8) \plus{} 9, (2m \minus{} 8)\geq4$
which is again the sum of two composite numbers!

Another similar kind of problem is the following:
Show that if $ n$ is an even integer $ n\geq40$ then there exists odd composite positive integers $ u$ and $ v$ such that $ n\equal{}u\plus{}v$.

More than half of the integers smaller than $n$ are composite. So both $k$ and $n-k$ must be composite, for some $k$


conics
parabola
geometry proposed
geometry

Dear everyone.

Please think of the following.
There are parabola p and two circles a, b so that the common tangent t of them exists.
Centers of circles are on the axe of parabola p.
The midpoint of the segment connecting centers of two circles is the focus of the parabola p.
Then the radical axe of two circles is the tangent (at its vertex) of the parabola p.

Thank you for reading my shoddy post. :)
I don't know its origin because I got this from my nephew.
Sorry.

My little hope is thinking without analytic method.

Excuse me, but I cannot resist the pun. A radical axe was used on Mary Stuart.

Let's call ours a radical axis.


Find all Integral Solutions Of:

\[ x\plus{}y\equal{}x^{2}\minus{}xy\plus{}y^{2}\]

With $ x,y\in\mathbb{Z}$

Not exactly elegant, but...
[hide]
Note that both $ x$ and $ y$ cant be negative, or the LHS < RHS.

If $ x$ is positive and $ y$ is negative, then $ x\minus{}|y|\equal{}x^{2}\plus{}|xy|\plus{}y^{2}$, in which for integer values the LHS < RHS.

Therefore both $ x$ and $ y$ are nonnegative.

$ x\plus{}y\equal{}x^{2}\minus{}xy\plus{}y^{2}$
$ y^{2}\minus{}(x\plus{}1)y\plus{}(x^{2}\minus{}x)\equal{}0$
$ y\equal{}\frac{x\plus{}1\pm\sqrt{\minus{}3x^{2}\plus{}6x\plus{}1}}{2}$
Note that $ y$ has to be a nonnegative integer, so this limits $ x\le2$ or else the discriminant $ \minus{}3x^{2}\plus{}6x\plus{}1 < 0$

So using $ x\equal{}2$ yields $ y\equal{}1, 2$,
using $ x\equal{}1$ yields $ y\equal{}0, 2$
using $ x\equal{}0$ yields $ y\equal{} 0, 1$,

thus our solutions are $ {(0,0), (0,1), (1,0), (1,2), (2,1), (2,2)}$[/hide]

Another soln for x,y non-negative:
$ x^{2}\minus{}xy\plus{}y^{2}\geq xy$,
$ x\plus{}y\geq xy$
$ xy\minus{}x\minus{}y\plus{}1\leq 1$
$ (x\minus{}1)(y\minus{}1)\leq 1$
either
$ (x\minus{}1)(y\minus{}1)\equal{}1$ (yielding x=y=2 or x=y=0)
$ (x\minus{}1)(y\minus{}1)\equal{}0$ or (yielding x=1 or y=1).
If x=1, $ 2y\equal{}y^{2}$, so either y=0 or y=2.
If y=1, $ 2x\equal{}x^{2}$, so either x=0 or x=2.


Are you sure the thesis is true?

If a_k=2k I can take 2006 positive integer and a_0=0; a_{2005}=4010 and |a_i-a_{i+1}|=2.
But all this positive integer are even.
if a_k-a_l=2005 then a_k is odd and a_l is even or a_l is odd and a_k is even.

Where is my mistake?

Good night, Simone.

Sorry, it was a mistake when I missed some words. I've just fixed


solve equation :
$12^n + 5^n =a^2$ ( where$a,n \in Z^{+}$)

If n is odd, then a^2=5^n=2(mod 3). It is contradiction.(Because perfect squares are can not be 2 mod 3)

        So n is even number. Let n=2k. 5^2k + 12^2k = a^2
Then 5^2k = a^2 - 12^2k = (a-12^k)(a+12^k) ...(*)
gcd(a-12^k,a+12^k)=gcd(a-12^k,2a)=gcd(a-12^k,2)=1
( we used (a,12)=1 and a is odd.)

 Let x=a-12^k and y=a+12^k.
 We know that x<y  and  x.y=5^2k  and  gcd(x,y)=1.
 Then x=1. So a=12^k+1
           Put a=12^k+1 in (*) we have 5^2k = 2.(12^k)+1.
 3.(12^k) >=  2.(12^k)+1 = 5^2k =25^k . So 3.(12^k) >= 25^k.

  And 3 >= (25/12)^k . Then 3 >= (2 + 1/12)^k > 2^k . So k=1,0

  If k=0 then n=0  and  1+1=a^2 there is no solution.
  If k=1 then n=2  and  25+144=a^2  and  a=13  .

  There is only one solution (n,a)=(2,13)  .


inequalities
calculus
calculus computations

hello,to you first question. We assume that $ ac \minus{} bd\geq0$ and now we write the left-hande side in the form
$ ac \minus{} bd \equal{} ac \minus{} ad \plus{} ad \minus{} bd \equal{} a(c \minus{} d) \plus{} d(a \minus{} b)$. Now it es clear that
$ a(c \minus{} d)$ is nonpositive because of $ 0\le a$ and $ c \minus{} d < 0$
and
$ d(a \minus{} b)$ is negative because of $ 0 < d$ and $ a \minus{} b < 0$
and so the inequality $ ac \minus{} bd\geq0$ does not hold, contradiction.
To your second problem. We assume $ a^2 \geq b^2$ and we write the left-hand side in the form $ (a \minus{} b)(a \plus{} b)\geq0$ after a binomial formula. Now $ a \plus{} b$ is positve and $ a \minus{} b$ is negative, so our product can not be non negative,contradiction.
Sonnhard.


calculus
integration
logarithms
calculus computations

Define $ f(z)\equal{}\frac{z}{(1\plus{}z^{2})\sinh\pi z}\qquad u_{N}\equal{}N\plus{}\frac{1}2$

$ A\equal{}\minus{}u_{N}$ , $ B\equal{}u_{N}$ , $ C\equal{}u_{N}(1\plus{}i)$ , $ D\equal{}u_{N}(\minus{}1\plus{}i)$

Because of $ \int_{BC}f$ , $ \int_{CD}f$ , $ \int_{DA}f\to 0$ for $ N\to\infty$

$ \int_{AB}f\to 2\pi i\sum_{i\Bbb{N}}\text{Res}f\equal{}\minus{}\frac{1}2\plus{}\sum_{k\equal{}2}^{\infty}(\minus{}1)^{k}\frac{2k}{k^{2}\minus{}1}$

$ \equal{}\minus{}\frac{1}2\plus{}\sum_{k\equal{}2}^{\infty}\left[\frac{(\minus{}1)^{k}}{k\plus{}1}\plus{}\frac{(\minus{}1)^{k}}{k\minus{}1}\right]\equal{}2\ln 2\minus{}1$


abstract algebra
group theory
superior algebra
superior algebra unsolved

Let  $ G$ be a finite group which possesses an automorphism P such that P(g)=g iff g = e.if $ P^2$ is an identity map from G to G.Prove that G is abelian. Please give a proof involving basic group theory (not lie group or anything).

thanx in advance.

You have to prove first the following

[b]Fact. [/b] $ P(x) \equal{} x^{ \minus{} 1}$ for every $ x \in G$.

Once you have done so proceed as follows...

Take any $ a, b \in G$. Since P is an automorphism of G we can find $ x \in G$ such that

$ ab \equal{} P(x) \equal{} x^{ \minus{} 1}$.

Hence,

$ x^{ \minus{} 1} \equal{} P^{2}(x^{ \minus{} 1}) \equal{} P(P(x^{ \minus{} 1})) \equal{} P((ab)^{ \minus{} 1}) \equal{} P(b^{ \minus{} 1}a^{ \minus{} 1}) \equal{} P(b^{ \minus{} 1})P(a^{ \minus{} 1}) \equal{} ba$

and the proof terminates.

Regards,
José.

P.S. I guarantee you that the proof of the auxiliary [b]fact[/b] doesn't require any heavy machinery. So long, man!


geometry
geometric transformation
function

Let be a set $6,5,4,3,2,1$
If we are swapping two terms in places it called "swap".
How much permutations we can get with exactly 4 "swaps"?
For example:
$6,5,4,3,2,1-1,5,4,3,2,6-1,3,4,5,2,6-1,4,3,5,2,6-1,4,2,5,3,6$

it has something to do with the fact that most swaps make different sequences, but if there are 2 swaps that can undo each other, you have to subtract that from the total...but it seems that this would take a lot of case work

what the signature are you talking about ?? I didn't understand.

PS, i dont think i explained it too well. Doing what i did is just an example of making a sequence, but the important thing is that i set up a bijection between the makables and non-makables, thus each must be half of all possible combinations.

For my example, you dont get everything. what if the first number you want is already there? You could just say swap two that as of yet dont matter, which gives a satisfactory answer.

[quote="seamusoboyle"]I reckon the answer to be $\frac{6!}{2}$

Look at it like this. Consider trying to make a certain permutation. swap the first one with the one that you want to be first. Swap the second with the number you want to be second etc etc... there are two numbers left on the end we cant change (as weve used all our swaps) But now, we can prove you CANT make the permutation that has those last two swapped. Its easy, just look at the signature. After the first four the signature is always 1. But with those last two swapped, its -1. So for every permatation we can make, there is exactly one we cant. Hence the answer is $\frac{6!}{2}$[/quote]
Ok, but I don't understand your prove about the permutation that we cant make.
Can you explain more clearly please?

We have an thing called the signature of a permutation. Basically, we can write every permatation of these 6 numbers in terms of two cycles, eg:

342516=(15)(14)(12)(13) kinda hard to explain, but hear me out. What we have is that the translation of swap 2 and 4, then 5 and 6, then 2 and 4, then 5 and 6 into maths talk is (24)(56)(24)(56) Now each two cycles has signature -1. Also, its multiplicitive, so whenever we do four of our swaps, the signature of our permatation is always 1. Now, say we had made the permatation 234165 with four swaps. Then the permutation 234156 is 234165 by the two cycle (65), so it would have signature -1, since the permutation of 234156 is +1. So that definately cannot be made with four swaps.

But we can prove we can make every combination starting with whatever 4 digits we want, but the last two have be in a certain order. And we cannot make the combination with the last two swapped, as proved above, so for every permutation we can make, we have exactly one that we cant make. So then each of the sets is half all possible possible permutations ie $\frac{6!}{2}$

PS we can use the same idea to show if we do $n-2$ swaps on $n$ elements, we get exactly $\frac{n!}{2}$ permutations.

All clear? Im terrible at explaining things, but ill try again if nescessary!

Now I understand, the only thing that I didn't understand is the signature and the all thing about the combinations that we can make I understand by myself. Thanks.  ;)

EDIT: Swaps don't have to be a flip of consecutive terms.  :(

seamusoboyle, did you take into account the possibility that you don't need to swap one or more of the first four numbers? It doesn't seem like you did.

I did  :)

Basically i showed that all permutations with signature -1 cant be made, and all permutations with +1 can be made.

For example, say you wanted to make the sequence that goes 1 3 6 5 2 4

6 5 4 3 2 1   We want the one at the front, so swap 1 and 6.
1 5 4 3 2 6   Now we want the 3 in place number two, so swap the 5 and 3.
1 3 4 5 2 6   Now we want the 6 in place 3, so swap the 6 and 4.
1 3 6 5 2 4   Now we have the sequence we want, so just do two swaps the same.

Can you see after 4 swaps we can make the first 4 digits whatever we want? Even if the digit we want is in place (As in the example, just do a rubbish swap twords the end in the digits that dont matter. To illustrate:

Making the sequence 6 5 4 3 2 1 with four swaps.

6 5 4 3 2 1   The first digit is right, so make a swap anywhere after it.
6 5 3 4 2 1   The second digit is right, so swap any two anywhere after it.
6 5 3 1 2 4   The third digit needs to be 4, so swap the 3 and 4.
6 5 4 1 2 3   The fourth digit needs to be 3, so swap the three and the 1.
6 5 4 3 2 1   And were done!

The idea with the signature is that if the sequence:

a b c d e f   can be made, the the sequence
a b c d f e   cant be made.

So making the first four digits what we want, the last two have to take a certain order, we cant swap them and expect to be able to make the new sequence in 4 swaps, its impossible!

So for whatever sequence we can make (a b c d e f) there is exactly one sequence we cant make (a b c d f e) Since the total number of sequence is $6!$ We get that

$\text{Total number of sequences that can be made}=\text{Total number of sequences that can't be made}=\frac{6!}{2}=360$

Hope this clears thing up and it didnt sound too babyish! If not, just ask!

Yeah, sorry, I just realized that it was [i]exactly[/i] 4 swaps.  :blush: Nice solution.

[quote="seamusoboyle"]The idea with the signature is that if the sequence:

a b c d e f   can be made, the the sequence
a b c d f e   cant be made.

So making the first four digits what we want, the last two have to take a certain order, we cant swap them and expect to be able to make the new sequence in 4 swaps, its impossible!

So for whatever sequence we can make (a b c d e f) there is exactly one sequence we cant make (a b c d f e)[/quote]

K, my only question is, how do you determine which is the respective possible arrangment given an impossible arrangment?

What if you had instead focused on the last four numbers when you made your sequences? In that case it would not be the last two numbers, it would be the first two numbers, because any four numbers can be made the "last four", just like any four numbers can be made the "first four".

Since you don't know which 4 numbers were "focused on" when the possible sequence was made, how do you determine the respective possible sequence?

[quote="seamusoboyle"]Thats why i said that the way i made the sequence was only an example earlier on.
The important thing was the bijection. With your method, the bijection is that if you can make the sequence e f d c b a then you cannot make f e d c b a, which is again a bijection. If you like, you can make any four numbers what you want, but those last two are invarient..[/quote]

Yea, it is an example, and true, there are always two you can switch. However, (1) I don't know what a bijection is, and (2) there still no way of determining the respective possible sequence from a given impossible sequence, as far as I can tell.

How are the last two invarient? There are always two that are invarient, but it's not always the last two... as you said, it's only an example.

I'm still unclear about your explanation.

OK, i think the problem here is the bijection.

Basically, a bijection means that we can pair up any one 'makable sequence' with exactly one other 'unmakable sequence'. This means that there is the same amount of each, and since the total is $6!$, each must be exactly half of this.

Now, im saying, look at the function that swaps the last 2 numbers in the sequence.
Now, kinda obviousally, this function is bijective. To see why it is so, for every sequence we put in, we only get one sequence out, but importantly, we can work backwards. Given the 'out' sequence, there is only one sequence we could have possibly in. So the function is bijective.

So now put a certain sequence into the function, say 1 4 3 5 6 2
And out pops the sequence 1 4 3 5 2 6

We know we can make one of these sequences with exactly 4 swaps (cause we can make the first four numbers with 4 swaps, as shown earlier, and the last two digits are in every possible order.)

Now, the big deal with the signatures is that whichever of these it was possible to make, it is impossible to make the other.

Fill in the rest yourself? Of shall i go on!?!

Now, I'm saying, look at the function that swaps the first two numbers in the sequence.

"Now, kinda obviousally, this function is bijective. To see why it is so, for every sequence we put in, we only get one sequence out, but importantly, we can work backwards. Given the 'out' sequence, there is only one sequence we could have possibly in. So the function is bijective.

We know we can make one of these sequences with exactly 4 swaps (cause we can make the [last] four numbers with 4 swaps, as shown earlier, and the last two digits are in every possible order.)

Now, the big deal with the signatures is that whichever of these it was possible to make, it is impossible to make the other."

How do we know which bijective function to use, the one you gave or the one I gave, given an impossible sequence?

We can take any function we like like those ones, i just chose the one i did for the sake of simplicity.


Why does the first quotation mark end up backwards when converted to PDF?

Are you using the double quotation marks on your keyboard?  It's better to use the single quotation marks: To start the quote, type the left single quotation mark twice, and to end, type the right single quotation mark twice.  For example, type ``to be or not to be''.

If you have TeXnicCenter you can have the double quotation marks automatically replaced by the ones Ravi B suggested as you type.

Go to Tools, Options, tick Replace quotation marks and choose English, then OK.

I should point out that the start of the quotation is not 2 single quote marks but backticks which look like `` instead of ' '. They are at the top left of my keyboard but could be elsewhere on yours.

I was also wondering about this. I'm not using quotation marks i.e. shift 2, but the one near the enter button! Can't remember what it's called now :blush:  but I just used it then- '.

I've written: 'c' but in the document the one on the left doesn't change direction. I mean they're both the same. Not really a big deal, but is there anyway I can have them work nicely?

(I've just seen the lecturers handout and it seems that he has the same problem!)

[quote="stevem"]Use the backtick ` which is on the left of the keyboard with ¬ and ¦
Two of them give double quotes so you get $`$ or $``$.
(You'll be able to tell your lecturer :))

In TexnicCenter, Tools, Options you can tell it to replace ' by ` automatically if you wish.[/quote] So I use the back tick for the left quotation mark and the one on the @ key (') for the right one? I do this but they're uneven.  :oops:

Just noticed you have used the dollar sign- do you have to do this in between the dollar signs?  (I'm using them in \begin{vert...} you see.)

Haha, I'll tell him. I figured it out because when I viewed my document, both the quotation marks were the same way like in the notes. :ninja:

[quote="beans"]So I use the back tick for the left quotation mark and the one on the @ key (') for the right one?[/quote]That's correct
[quote="beans"]I do this but they're uneven.  :oops:

Just noticed you have used the dollar sign- do you have to do this in between the dollar signs?[/quote]I only used dollar signs because that is how this forum knows to use LaTeX. In fact, in your document, you mustn't use quotes in maths mode (ie between dollar signs) as you will get the wrong sized quote like you said. Maths mode gives $`c'$ but text mode should look like this $\text{`c'}$ (ignore \text as I am only using it here so I can tell the forum I want text mode)
[quote="beans"](I'm using them in \begin{vert...} you see.)[/quote]I'm not sure what this is - perhaps it is causing LaTeX to go into maths mode causing the problem. Could you give more of the code you've used?

[quote="stevem"]I'm not sure what this is - perhaps it is causing LaTeX to go into maths mode causing the problem. Could you give more of the code you've used?[/quote] I've written(typed!):
\begin{verbatim}
fprintf('The L_p estimate is %8.4f for p = %4.2f\n', lpe, p)
The L_p estimate is   0.0244 for p = 1.00
\end{verbatim}\\

The stuff inside is written in type set font, but I wanted it to be different because that's the matlab input that I have used. (I got this from one of the guides that I have).

I've got the quotes inside there working now aswell. Thanks :) Just don't know whether I can change the font size of the text?

[quote="stevem"]Ah, in program listings you don't want curly quotes but a straightforward '. To do this just put
\usepackage{upquote}
somewhere before \begin{document} and then you'll get straight quotes in the verbatim environment but nice curly ones in normal text.[/quote] That's for you! :first:  You know getting something to work for you in LaTeX is a bit like crunching through a problem. :oops: Feels great! Cheers. :)

(I do tend to use a lot of smilies don't I- good that they have a limit on them!)


In a sequence, each term after the second is the sum of the two preceding terms. The first and fifth terms are each 3. What is the second term in the sequence?

Let the second term be $ x$, then we have
\begin{align*}
\text{first} &= 3 \\
\text{second} &= x \\
\text{third} &= 3+x \\
\text{fourth} &= 3+2x \\
\text{fifth} &= 6+3x \\
\end{align*}
We are also given that the fifth term is $ 3$, so $ 6+3x=3 \Rightarrow x=\boxed{-1}$

Couldn't the sequence also be 3,0,3,0,3?


linear algebra
matrix
linear algebra unsolved

Sorry, I do not remember whether I've already posted this problem, but I find it very nice:
  Let's call "k-radical" of a matrix A any matrix $B$ such that $B^k=A$. Assume that $A,B$ are matrices $2x2$ with integer elements which commute and that for all $n$ the matrix $A^n+B^n$ admits an integer "n radical". Prove that we have $B^2=0$ or $A^2=0$ or $AB=0$.
   I do not know how to solve it if we do not assume that they commute. Also, for higher dimensions, I have no idea what could happen.

I think I have the solution.
It is quite long, so I attach the file with it.
In the way I had many errors, and fixed them many times.
I hope that this solution is ok.


AMC
AIME
function
algebra
rational function

Combine stuff to get a rational function having the form

[tex]\displaystyle\frac{f(a)}{(a-1)(a-9)(a-25)(a-49)}=0[/tex]

where the function f(a) has roots at 4,16,36,64 (you don't actually have to do ALL of hte algebra... see the following). The a^3 and a^4 coefficients are easy to find, and we can use these to find a relation between these coefficients (which includes x^2+y^2+z^2+w^2 and some constants) and the sum of the roots, which we know to be 4+16+36+64. Solve.


algebra
polynomial
modular arithmetic
floor function
number theory unsolved
number theory

Let $ a_n$ denote the coefficient of $ x^n$ in the polynomial $ (x^2\plus{}x\plus{}1)^n$. Prove that if $ p\geq 5$ is a prime number then $ a_p\equal{}1(\mod p^2).$

[hide]Let $r_1 = \frac{-1 + i \sqrt{3}}{2}$ and $r_2 = \frac{-1 - i \sqrt{3}}{2}$ be the two roots to $x^2+x+1$. Let $S_1(x) = \frac{(x-r_1)^p - x^p + r_1^p}{p} = -r_1 x^{p-1} + r_1 x^{p-2} - \ldots + r_1^{p-1} x$ and $S_2(x) = \frac{(x-r_2)^p - x^p + r_2^p}{p} = -r_2 x^{p-1} + r_2 x^{p-2} - \ldots + r_2^{p-1} x$. Observing that $\{r_1^p, r_2^p\} = \{r_1, r_2\}$ (since $r_1, r_2$ are distinct 3rd roots of unity and $p \geq 5$), we have
\begin{align*}
(x^2+x+1)^p
&= (x-r_1)^p (x-r_2)^p \\
&= (x^p - r_1^p + p S_1(x))(x^p - r_2^p + p S_2(x)) \\
&= (x^p - r_1^p)(x^p - r_2^p) + p(x^p - r_1^p)S_2(x) + p(x^p - r_2^p)S_1(x) + p^2 S_1(x) S_2(x) \\
&= x^{2p} + x^p + 1 + p(x^p - r_1^p)S_2(x) + p(x^p - r_2^p)S_1(x) + p^2 S_1(x) S_2(x).
\end{align*}
We seek the coefficient of $x^p$ in this expression modulo $p^2$. All monomials in $x^p S_1(x)$ and $x^p S_2(x)$ have degree at least $p+1$, while all monomials in $r_1^p S_2(x)$ and $r_2^p S_1(x)$ have degree at most $p-1$, so the coefficient of $x^p$ in this expression must be the coefficient of $x^p$ in $x^{2p} + x^p + 1 + p^2 S_1(x) S_2(x)$. Since the coefficient of $x^p$ must be an integer (as it comes from the expansion $(x^2 + x + 1)^p$), the coefficient of $x^p$ in $p^2 S_1(x) S_2(x)$ must be an integer. But the coefficients of $S_1(x)$ and $S_2(x)$ can be written as numbers of the form $\frac{a+bi \sqrt{3}}{2^k}$ for some integers $a,b,k$. Because the set of these numbers is closed under addition and multiplication, the coefficients of $S_1(x) S_2(x)$ also have this form. As the coefficient of $x^p$ in $S_1(x) S_2(x)$ must be of this form and is rational, we see that it must be a rational number which, when written in lowest form, does not have a denominator divisible by $p$. Consequently, $p^2 S_1(x) S_2(x)$ must be an integer divisible by $p^2$, so the coefficient of $x^p$ in $(x^2+x+1)^p$ modulo $p^2$ is indeed 1. [/hide]

Easy: $\left(\sum_{i=1}^k x_i\right)^p \equiv \sum_{i=1}^k x_i^p\;(\mathrm{mod}\,p)$ if $p$ is prime.

[hide]Use $C^p_{2p} \equiv 2 \pmod {p^2} $[/hide]

My deepest apologies for my carelessness in my previous post.  Here I give a correct solution:

Write $P(x):=\left(x^2+x+1\right)^p = \left(1-x^3\right)^p\left(1-x\right)^{-p}$.  Expanding it, we get \[P(x) = \left(1-x^3\right)^p \sum_{r \geq 0} (-1)^r\binom{-p}{r} x^r = \left(\sum_{k=0}^p (-1)^k\binom{p}{k}x^{3k}\right)\left( \sum_{r \geq 0} \binom{p+r-1}{p-1} x^r\right)\,.\]  The coefficient of $x^p$ is \[a_p=\sum_{k=0}^{\lfloor{p/3}\rfloor}(-1)^k\binom{p}{k}\binom{p+(p-3k)-1}{p-1}\,.\]  For $1 \leq k \leq \left\lfloor{\frac{p}{3}}\right\rfloor$, both $\binom{p}{k}$ and $\binom{p+(p-3k)-1}{p-1}$ are divisible by $p$.  Thus, this leaves $k=0$ in consideration, and \[a_p \equiv \binom{2p-1}{p-1} \equiv 1 \;\left(\mathrm{mod}\,p^2\right)\,,\] by Wolstenholme's theorem.