gcd(f(m) + n, f(n) + m) bounded for m != n

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

gcd(f(m) + n, f(n) + m) bounded for m != n

G H J

Reveal topic tags

greatest common divisor

L

G H BBookmark kLocked kLocked NReply

Source: IMO 2015 Shortlist, N7

The post below has been deleted. Click to close.

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

3564 posts

62861

#1 h Jul 7, 2016, 11:19 PM • 4 Y

Y by mathmaths, Adventure10, Mango247, TheHU-1729

Let $\mathbb{Z}_{>0}$ denote the set of positive integers. For any positive integer $k$ , a function $f: \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}$ is called $k$ -good if $\gcd(f(m) + n, f(n) + m) \le k$ for all $m \neq n$ . Find all $k$ such that there exists a $k$ -good function.

Proposed by James Rickards, Canada

This post has been edited 2 times. Last edited by 62861, Jul 20, 2016, 7:45 AM
Reason: added proposer

Z K Y

The post below has been deleted. Click to close.

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

6877 posts

#2 h Jul 7, 2016, 11:38 PM • 17 Y

Y by angiland, winnertakeover, ali.agh, pavel kozlov, Kayak, mijail, v4913, Kobayashi, HamstPan38825, Inconsistent, Jalil_Huseynov, Kingsbane2139, sabkx, Phorphyrion, Adventure10, Mango247, bhan2025

The answer is $k \ge 2$ .

For mod $2$ reasons, it is easy to check that $k=1$ fails.

Now we construct a function $f$ for which $\gcd(fn+m, fm+n) \le 2$ for all $m \neq n$ . We select our function $f$ of the form $f(n) = 2^{g(n)} - n - 1$ for some large $g$ , determined recursively by $g(1) = 1000$ , and $g(k+1) = 1 + \left( 1000^{g(k)} \right)!$ .

Now, assume $n > m$ and define $\begin{align*} A &= fn + m = 2^{g(n)} - n + m - 1 \\ B &= fm + n = 2^{g(m)} - m + n - 1 \\ \implies A+B &= 2^{g(m)} + 2^{g(n)} - 2. \end{align*}$ Since $A+B \equiv 2 \pmod 4$ , $4 \nmid \gcd(A,B)$ .

Now, suppose $p \mid B$ is an odd prime, hence $p \le B < 1000^{g(n-1)}$ . Consequently, $g(n) \equiv 1 \pmod{p-1}$ . So by Fermat's theorem, we obtain $A+B \equiv 2^{g(m)} \pmod p$ , hence $p \nmid A+B$ , which concludes the proof.

Z K Y

The post below has been deleted. Click to close.

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

478 posts

#3 h Jul 8, 2016, 10:57 AM • 2 Y

Y by Adventure10, Mango247

Answer: Such $k$ -good functions exists for all $k\ge 2$ only.

First we claim that there is no $1$ -good function. If there exist $m\neq n$ with $m, f(m)$ has same parity, and $n, f(n)$ has same parity, then $\gcd(f(m)+n, f(n)+m)$ is even, false. Then we can find two distinct $m, n$ with $m,f(m)$ has different parity and $n, f(n)$ has different parity, but then $\gcd(f(m)+n, f(n)+m)$ is still even, false.

Now we construct a $2$ -good function. Take $f(m)=g(m)-m$ , then we want to evaluate $d=\gcd(g(m)-m+n, g(n)-n+m)=\gcd(g(m)-m+n, g(m)+g(n))$ , and we want to make $d\le 2$ for all $m,n \in \mathbb{N}$ . First let us restrict $v_2(d)$ . We may achieve this by defining $g(m)=2^{h(m)+1}-1$ . Then $d|2^{h(m)+1}+2^{h(n)+1}-2$ , but $4\nmid 2^{h(m)+1}+2^{h(n)+1}-2$ because $h(m), h(n) \ge 1$ . So $v_2(d)\le 1$ .

Now we define $h$ inductively. Set $h(1)=1$ . Suppose we can define $h(1), h(2), \cdots h(k)$ for some $k$ , it suffices to find $h(k+1)$ such that in the original function $f$ , $\gcd(f(k+1)+m, f(m)+k+1) \le 2$ for all $m\le k$ . Till this end, set $D=\max\{2^{h(i)+1}-i+(k+1)-1\}$ for all $1\le i\le k$ , then if $p\mid g(m)-m+(k+1)=2^{h(m)+1}-m+(k+1)-1$ , then $p\le D$ . Take $Q$ to be the product of all odd primes at most $D$ , then take $h(k+1)=\phi(Q)$ . We claim that this choice works.

Indeed, if $p|2^{h(m)}+2^{\phi(Q)}-1$ , then since $p\le D$ , then $p\mid Q$ , so $p\mid Q\mid 2^\phi(Q)-1 \Rightarrow p\mid 2{h(m)} \Rightarrow p=2$ . So $d=\gcd(m+f(n),n+f(m))$ will not have odd prime factors, and $v_2(d)\le 1$ , thus $d\le 2$ . So this function is $2$ -good, as desired.

This post has been edited 1 time. Last edited by navi_09220114, Jul 8, 2016, 10:57 AM

Z K Y

The post below has been deleted. Click to close.

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

256 posts

#4 h Jul 9, 2016, 2:37 PM • 19 Y

Y by v_Enhance, 62861, ksun48, tenplusten, Kayak, AlastorMoody, Plops, mijail, khina, Justpassingby, gvole, Jalil_Huseynov, Kingsbane2139, sabkx, Adventure10, Mango247, thdnder, TheHU-1729, bhan2025

This is my problem! (James Rickards, Canada)
Until I saw the official solutions, I didn't know of an explicit function $f$ which worked (like in v_Enhance's solution).
A first approach to solving the problem (it was what I did initially at least) might take the form: set $f(1)=1$ , and define $f$ recursively. Let $P$ be the set of odd primes and $4$ , and assume $f$ has been defined up to $f(m-1)$ . Let $S=\{p\in P \text{ such that } p\mid f(n)+m,\text{ some } n<m\}$ . Then, using CRT define:
$\begin{align*} f(m)\equiv f(m-p) \pmod{p} \text{ for } p\in S, p<m\\ f(m)\equiv 0 \pmod{p} \text{ for } p\in S, p\geq m\\ \end{align*}$ This construction almost works, if $p\mid \gcd(f(m)+n,f(n)+m)$ , then $p\in S$ , so if $p\geq m$ then $p\mid n$ , so $p\leq n< m\leq p$ contradiction. So $p<m$ , and induction on the pair $(m-p,n)$ gives a contradiction, so the $\gcd$ is $1$ and you are done! So what went wrong?
The (quite easy to miss) problem is the case $n=m-p$ , for then you can't use induction that $\gcd(f(m-p)+n,f(n)+m-p)=1$ (this is of course equal to $f(n)+n$ when $m-p=n$ ). Unfortunately this can't be resolved very easily as is, but if you go back and be more careful with residues and your definition of $f$ , then you can modify this approach into a solution (make sure the set $f(n)+n$ does not take up too many residue classes modulo $p\in P$ ).

Z K Y

The post below has been deleted. Click to close.

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

308 posts

#5 h Mar 27, 2021, 9:34 AM

Y by

The answers are all $k\geq 2$ . We first show that there is no $1$ -good function.
Indeed, we show that for all function $f:\mathbb Z_{>0}\to\mathbb Z_{>0}$ there exists $m,n$ such that
$f(m)+n\text{ and }f(n)+m$ are both even. This is not hard. Notice that if $f(1),f(3)$ is both odd then $f(1)+3,f(3)+1$ is both even, therefore, $f(1),f(3)$ cannot both be odd, similarly $f(2),f(4)$ cannot both be even.

WLOG assume $f(1)$ is even while $f(2)$ is odd then $f(1)+2$ and $f(2)+1$ are both even as desired.

We now show that there is a $2$ -good function. Let $P$ be the union of the set of odd primes and $4$ . It suffices to show that there exists a function $f$ such that
$p\nmid (f(m)+n,f(n)+m)$ for all $m\neq n$ and $p\in P$ . We will strengthen the condition such that $f(n)+n$ is a prime for all $n$ and that $f(n)+n$ is injective.
We define $f$ recursively. Define $f(1)=1$ , $f(2)=3$ .
Now suppose we have define $f(1),f(2),...,f(n-1)$ , we will assign a value for $f(n)$ . We will do so by showing that given $p\in P$ there exists $0\leq g_p(n)\leq i$ such that
$p\nmid (f(m)+n,g(p)+m)$ for every $1\leq m\leq n-1$ . Then by Chinese Remainder Theorem we can take $f(n)\equiv g_p(n)\pmod p$ for all $p\in P$ . If $p=3$ we can take
$g_3(n)\equiv 2n-1\pmod 3$ If $p=4$ we can take $g_4(n)=2,1,3,2,3$ for $5\leq n\leq 8$ and extend it periodically with period $4$ . Let $P_s$ be the set of elements in $P$ smaller than $n$ . Suppose $p\in P_s$ , we call $p$ bad if
$f(n-p)\equiv -n\pmod p$ and good otherwise. Notice that if $p$ is good, then we can let $f(n)\equiv f(n-p)\pmod p$ , then if $m<n$ we have
$(f(n)+m,f(m)+n))\equiv (f(n-p)+m,f(m)+n-p)\not\equiv 0\pmod p$ So we can just take $g(p)\equiv f(n-p)\pmod p$ .
Now suppose $p$ is bad. Since $f(m)+m$ is a prime by inductive hypothesis, for each $p$ there exists exactly one integer $n$ such that $n$ is bad. Therefore, we have $n<2p$ and $f(m)\equiv f(m-p)\pmod p$ for all $m=p+1,...,n-1$ . Therefore, at most $n-2$ of the following numbers
$\{f(1)+n,f(2)+n,...,f(n-1)+n\}$ will be equal to $0\pmod p$ (since $f(1)+n\not\equiv f(2)+n\pmod p$ ). Therefore suppose $p\nmid f(i)+n$ we can just take $g_p(n)\equiv -i\pmod p$ .
If $p\in P$ and $p\geq n$ then again the following $n-1$
$\{f(1)+n,f(2)+n,...,f(n-1)+n\}$ contain at most $n-2<m-1$ multiples of $p$ , so suppose $p\nmid f(i)+n$ we can just take $g_p(n)\equiv -i\pmod p$ .
This completes the proof.

Bacteria wrote:

This is my problem! (James Rickards, Canada)

Congratulations on finding such an amazing problem!
It turns out that my idea is exactly the same as yours. I try to construct the function recursively using the quite obvious way (CRT with $f(m)\equiv f(m-p)$ for every prime. But indeed I find out that it is impossible due to the case $n=m-p$ . So basically all my wordy explanation is try to avoid that case.

Z K Y

The post below has been deleted. Click to close.

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

966 posts

#6 h Jul 4, 2022, 8:10 PM • 1 Y

Y by JG666

The answer is $\boxed{k\ge2}.$

If we have two integers $m,n$ of different parities where $f(m), f(n)$ have different parities than $m,n$ respectively, then $2 \mid \gcd(f(m)+n, f(n)+m).$ Otherwise, there exists two integers $m,n$ of the same parity where $f(m), f(n)$ also have that same parity. Then $2 \mid \gcd(f(m)+n, f(n)+m)$ still.

It suffices to construct a $2$ -good function, we construct this inductively. Let $f(1) = 2^2-1-1=2.$

Suppose we have constructed valid $m$ up to a certain $n.$ Then consider an integer $C$ larger than $f(m) + n$ for any $m < n.$ Then set $f(n) = 2^{C! + 1} - n-1.$

For any positive integer $m < n,$ we have $f(m) + n + f(n) + m \equiv 2^{C!+1} + 2^{c} - 2 \equiv 2 \pmod{4}$ where we assume to have set $f(m) = 2^{c} - m - 1$ earlier, so $4$ does not divide the gcd. Also if prime $p$ divides $f(m) + n,$ then $p-1$ divides $C!$ and $f(m) + n + f(n) + m \equiv 2^{C!+1} + 2^{c} - 2 \equiv 2^{c} \not\equiv 0 \pmod{p}$ by FLT, so this works. $\blacksquare$

This post has been edited 1 time. Last edited by squareman, Jul 4, 2022, 8:12 PM

Z K Y

The post below has been deleted. Click to close.

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

5001 posts

#7 h Oct 29, 2023, 3:18 PM • 1 Y

Y by TheHU-1729

rickards... :maybe:

:maybe:

The answer is $k \geq 2$ .

I first show $k=1$ fails. Suppose that $f$ works. If it sends some odd $a_1$ to an even and some even $a_2$ to an odd, we get a contradiction since $2 \mid \gcd(f(a_1)+a_2,f(a_2)+a_1)$ . Thus $f$ must either send all evens to evens or all odds to odds (possibly both), which clearly fails too.

I will now construct a function $f$ that is $2$ -good, which finishes the problem. We construct $f$ of the form
$f(n)=2^{g(n)}-n-1$ for a function $g$ that will be defined as follows: let $g(1)=1000$ , and then recursively define $g(n)$ such that all the prime divisors of $f(m)+n=n-m+2^{g(n)}-1>0$ across any $m<n$ also divide $2^{g(n)}-2$ , and $g(n)>g(n-1)$ . This is easy: for each prime divisor $p$ just multiply a factor of $p-1$ to $g(n)-1$ .

Now suppose some prime $p$ divides $\gcd(f(m)+n, f(n)+m)$ , so it has to divide $2^{g(n)}-2$ as well. On the other hand, we require
$p \mid m+n+f(m)+f(n)=2^{g(m)}+2^{g(n)}-2 \implies p \mid 2^{g(m)} \implies p=2.$ Furthermore, since $m+n+f(m)+f(n) \equiv 2 \pmod{4}$ , we cannot have $4 \mid \gcd(f(m)+n,f(n)+m)$ , hence we always have $\gcd(f(m)+n,f(n)+m) \leq 2$ , as desired. $\blacksquare$

Remark: The driving motivation behind this solution is the fact that if we allow $f$ to go from $\mathbb{Z}^+ \to \mathbb{Z}$ then $f(n)=-n+1$ works perfectly, so we need a way to translate this to some $\mathbb{Z}^+ \to \mathbb{Z}^+$ function that sort of has the same behavior "modulo primes". My first idea was to define $f(n)=p_{g(n)}\#-n+1$ (a primorial that grows sufficiently large), but if you write stuff out you realize that it's more convenient to have $f(n)+n+1$ be a convenient form whose prime factors we can control easily: this turns out to be possible as well, and we're done!

This post has been edited 2 times. Last edited by IAmTheHazard, Oct 29, 2023, 5:49 PM

Z K Y

The post below has been deleted. Click to close.

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

196 posts

#8 h Dec 12, 2023, 5:00 AM • 2 Y

Y by TheHU-1729, Iveela

Answer: For all $k \ge 2$ .

Firstly observe that there isn't any 1-good function because of modulo 2 reasons. Now we'll construct function $f$ for which $\gcd(f(m)+n, f(n)+m) \le 2$ . We'll select $f(n) = 2^{g(n)} - n - 1$ for some $g \colon \mathbb{N} \to \mathbb{N}$ . Let $N$ be a sufficiently large integer and let $g(1) = N$ . Now we'll construct the sequence $g(n)$ recursively. Assume $g(1), \dots, g(n-1)$ are defined and we'll define $g(n)$ such a way:

$g(n) > \max(g(1), g(2), \dots, g(n-1))$ and for all primes $p$ less than $f(n-1) + n + 1$ , $g(n) \equiv 1 (p-1)$ .
Then it suffices to check that $\gcd(f(m) + n, f(n) + m) \le 2$ for all $1 \le m \le n - 1$ . Since $f(m) + n + f(n) + m = 2^g(n) + 2^g(m) - 2 \equiv 2 (4)$ , so $4 \nmid \gcd(f(m) + n, f(n) + m)$ . Now assume the contrary, let $p$ be an odd prime that $p \mid \gcd(f(m) + n, f(n) + m)$ . Since $p \mid f(m) + n$ , so $p \le f(m) + n < f(n-1) + n + 1$ , so $g(n) \equiv 1 (p-1)$ . Thus by FLT, we have $f(n) + m = 2^{g(n)} - n - 1 + m \equiv 2 - n - 1 + m = m + 1 - n \equiv 0 (p)$ . On the other hand, $0 \equiv f(m) + n = 2^{g(m)} - m - 1 + n \equiv 2^{g(m)} (p)$ , so $p \mid 2^{g(m)}$ , a contradiction. Thus $\gcd(f(m) + n, f(n) + m) \le 2$ for all $1 \le m \le n - 1$ and we can construct $g$ recursively. Thus we're done. $\blacksquare$

Remark: This is a very difficult problem, or I'm so bad at constructions. Somehow I managed to solve it, but it doesn't feel intuitive after solving it. Firstly I think if we let $f(m) + f(n) + m + n$ is a power of 2, then we only have to deal 4. Thus $f(n) = 1 - n$ perfectly work. And I think I have to enhance $f$ , so my first idea was taking $f(n) = 2^{g(n)} - n$ and it didn't work well. And I think I should at least deal with 4, so I take $f(n) = 2^{g(n)} - n + 1$ and I thought defining $g$ recursively by using CRT would work. But it didn't work.

It took almost 2 hours to realise that if we're gonna deal with 4, so $f(n) = 2^{g(n)} - n + 2k + 1$ would work. So I chose $f(n) = 2^{g(n)} - n - 1$ and that works perfectly. :-D

:-D

This post has been edited 3 times. Last edited by thdnder, Dec 12, 2023, 5:05 AM

Z K Y

The post below has been deleted. Click to close.

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

498 posts

#9 h Aug 20, 2024, 5:07 AM

Y by

We claim the answer is $k\ge 2$ .

Claim:
There is a $2$ -good function.

Proof:
Let $p_1=4$ and $p_2, p_3,\dots$ be the odd primes in order.
We will recursively define sequences $x_1, x_2,\dots$ , $s_1, s_2,\dots$ , and $f(1), f(2),\dots$ of positive integers.
First, define $x_{1} =\dots = x_{10} = 1$ , $s_1=10$ , and $f(1) = p_1\dots p_{10}$ .

Go through each value of $i>1$ .
Define $s_i>s_{i-1}$ such that
$p_{s_i}> i+\max_{m<i}(f(m)).$ Then, for each $s_{i-1}<j\le s_i$ , choose a value of $x_j\not\equiv 0\pmod{p_j}$ such that
$x_j+m+f(m)\not \equiv 0 \pmod{p_j}$ for all $m< i$ . This is possible because $p_j>p_{s_{i-1}}\ge i$ .
Then, choose $f(i)$ such that $i+f(i)\equiv x_j\pmod{p_j}$ for all $j\le s_i$ .

Assume towards a contradiction that $p_i\mid f(a)+b$ and $p_i\mid f(b)+a$ for $a<b$ .
Then, $p_i \le f(a)+b < p_{s_b}$ . So, $f(b)+b \equiv x_i \pmod{p_i}$ .
Let $r$ be the lowest number such that $s_r\ge i$ .

Case 1: $a<r$

Then, by definition,
$b+f(b)+a+f(a)\equiv x_i+a+f(a)\not \equiv 0\pmod{p_i},$ a contradiction.

Case 2: $a\ge r$

Then,
$b+f(b)+a+f(a)\equiv 2x_i\not \equiv 0\pmod{p_i},$ a contradiction.

Claim:
There is no $1$ -good function.

Proof:
Assume toward a contradiction $f$ is $1$ -good.
There is at most $1$ value of $x$ such that $x\equiv f(x)\equiv 0\pmod{2}$
and at most $1$ value of $x$ such that $x\equiv f(x)\equiv 1\pmod{2}$ .
So, there exists $a, b$ such that $a\equiv f(b)\equiv 0\pmod{2}$ and $b\equiv f(a)\equiv 1\pmod{2}$ ,
a contradiction.

Z K Y

The post below has been deleted. Click to close.

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

1533 posts

#10 h Jan 19, 2025, 12:06 AM • 1 Y

Y by MS_asdfgzxcvb

your telling me this whole induction is what?

Note that a $1$ -sunny function can't exist, since if $f$ maps infinitely many even numbers to even numbers or odd numbers to odd numbers, taking both $m, n$ to be that type of even / odd number gives $k \ge 2$ . If there are infinitely many even numbers mapped to odd and odd mapped to even, then taking $m, n$ to be different parity that satisfy the above gives $k \ge 2$ as well.
We claim that a $2$ -sunny function exists and construct it through transfinite induction.

Claim: Suppose that $m \mapsto -f(m)$ has no involutions and forms a digraph on residues $\pmod{p}$ , other than $r + f(r) \equiv 0 \pmod{f(p)}$ holding for at most one number $r$ . Then $p \nmid \gcd(f(m)+n, f(n)+m)$ for all $n, m$ .
Proof. A contradiction can only occur if $n \equiv -f(m) \pmod{p}, m \equiv - f(n) \pmod{p}$ . Our graph is just a non-involutive arrow graph with one node pointing to itself which still has no involutions other than taking that arrow twice, which can't occur since there's at most one $r$ . $\blacksquare$
The idea is to iteratively construct this digraph for each prime $p$ , at each time only worrying about finitely many primes.
For all small primes $k$ and $4$ we can manually construct a working digraph and function $f_p$ on residues $\pmod{p}$ that forms the digraph $G_p$ .
Define a set $\mathcal{S}$ of dirty primes initially empty. Define a set $\mathcal{C}$ of completed primes containing all small primes and $4$ .
Construct $f(n)$ by CRT to have its correct residue of $f_p(n) \pmod{f(p)}$ . For each dirty prime $q$ , we take $f(n) \equiv f_q(n)$ to continue building the digraph $G_q$ (at this point we have our one fixed number $r$ ). If $G_q$ has been specified for all residues properly, we remove $q$ from $\mathcal{S}$ and add it to $\mathcal{C}$ .
We add all prime divisors of $n + f(n)$ to the set $\mathcal{S}$ of dirty primes (as this is their fixed point), which keeps it finite.
At the end of this transfinite induction process, all primes and $4$ are in $\mathcal{C}$ , and thus by our claim $\gcd(f(m) + n, f(n) + m)$ isn't divisible by any element of $\mathcal{C}$ as desired.

Z K Y

The post below has been deleted. Click to close.

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

217 posts

#11 h Apr 7, 2025, 5:23 AM

Y by

We claim answer is $\boxed{k \ge 2}$ .

Proving $k=1$ doesn't work:

Assume for we find some valid $1$ -sunny function. Now we look at $n \mapsto f(n)$ in $\mathbb{F}_2$ , we get that there cant be more than one of $0 \mapsto 0$ or $1 \mapsto 1$ .

Consequently both $0 \mapsto 1$ and $1 \mapsto 0$ cannot exist. But this means either the image of infinitely many odd $n$ or even $n$ aren't defined, contradiction.

Proving $k \ge 2$ works:

Define $f(n)=g(n)-n$ . Now let $g(1)=2 \text{ and } g(n)=2^{g(n-1)!+1}-1$ Say there exists some odd prime $q$ such that $q \mid \gcd(g(m)-m+n,g(n)-n+m)$ ( $m < n$ ) and hence $q \le g(m)-m+n \le g(n-1)+1 \implies q-1 \mid g(n-1)!$ . This means $0 \equiv g(m)+g(n)=2^{g(m-1)!+1}+2^{g(n-1)!+1}-2 \equiv 2^{g(m-1)!+1} \pmod q$ Which is a contradiction. And obviously see that $\nu_2 \left(2^{g(m-1)!+1}+2^{g(n-1)!+1}-2 \right)=1$ And so the $\gcd$ is always atmost $2$ as required.

Remark: Main motivation for the construction is that if $f$ was defined from $\mathbb{N} \to \mathbb{Z}$ , then a much simpler $2$ -sunny function existed which is just $n \mapsto 1-n$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a