IMO Shortlist 2009 - Problem N3

The post below has been deleted. Click to close.

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

April

1270 posts

April

#1 h Jul 5, 2010, 11:52 AM • 8 Y

Y by Davi-8191, tenplusten, A_Math_Lover, yayitsme, HWenslawski, megarnie, StarLex1, Adventure10

Let $f$ be a non-constant function from the set of positive integers into the set of positive integer, such that $a-b$ divides $f(a)-f(b)$ for all distinct positive integers $a$ , $b$ . Prove that there exist infinitely many primes $p$ such that $p$ divides $f(c)$ for some positive integer $c$ .

Proposed by Juhan Aru, Estonia

Z K Y

The post below has been deleted. Click to close.

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

Zhero

2043 posts

Zhero

#2 h Jul 6, 2010, 8:12 PM • 10 Y

Y by anantmudgal09, utkarshgupta, Arshia.esl, SerdarBozdag, HWenslawski, strong_boy, Adventure10, Mango247, and 2 other users

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

daniel73

253 posts

daniel73

#3 h Jul 9, 2010, 9:42 AM • 8 Y

Y by A_Math_Lover, BaishuakRayimbek, wasikgcrushedbi, Adventure10, Mango247, and 3 other users

Alternative solution:

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

Learner94

634 posts

Learner94

#4 h Feb 2, 2012, 2:54 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

I think this can be done in a simpler way
Let $p_1,p_2, \cdots, p_r$ be the only primes dividing $f(c)$ , for all natural number $c$ .

Let $f(S) = \prod_{i=1}^{r}(p_i)^{\alpha_i}$ , where $\alpha_i \ge 0$

Now we will show that the sequence of natural numbers $\left \langle T_n \right \rangle _{n \ge 1 }$ such that $f(T_n + S) = f(S)$ is unbounded from above.

Indeed if for all $n \ge 1$ we let $T_n = \prod_{i=1}^{r}(p_i)^{\beta_i}$ , such that $\beta_i > \alpha_i$ we
have $(T_n + S) - S \mid f(T_n + S) - f(S)$ and its easy to see that $f(T_n + S)$ and $f(S)$ has same canonical factorization., hence are equal.

and take any natural number $N$ , so we have $T_n + S - N \mid f(S) - f(N)$ , if $T_n + S - N \le f(S) - f(N)$ or we have $T_n \le f(S) - f(N) + N - S$ for all $n \ge 1$ , which is a contradiction, since the sequence is unbounded from above. So we must have $f(S) = f(N)$ , so the function is constant, which proves the statement of the problem.

Z K Y

The post below has been deleted. Click to close.

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

filetmignon821

292 posts

filetmignon821

#5 h Jul 30, 2012, 4:46 PM • 2 Y

Y by Adventure10, Mango247

Much easier way:
Let f(0)=c
We have p|f(p)-c for all p, so f(p)=kp+c for some integer k. Now assume by contradiction that there are finitely many primes that divide f(a) for some positive integer a. Let their product be P. We have $f(P^ac)=kP^ac+c=c(kP^a+1) \forall a \in \mathbb{N}$ . Obviously, $kP^a+1$ is not divisible by any of the primes in our product, so k must be 0. Thus, $f(P^ac)=f(0) \forall a \in \mathbb{N}$ . This means that $P^ac-x|f(0)-f(x) \forall a,x \in \mathbb{N}$ . However, if we fix x, we can choose an a such that $P^ac-x>|f(0)-f(x)|$ , so $f(x)=f(0) \forall x \in \mathbb{N}$ . However, this means that f is constant, a contradiction. Thus, the problem statement is true.

Z K Y

The post below has been deleted. Click to close.

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

Zhero

2043 posts

Zhero

#6 h Jul 31, 2012, 2:30 AM • 1 Y

Y by Adventure10

Quote:

so k must be 0.

Why?

Z K Y

The post below has been deleted. Click to close.

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

filetmignon821

292 posts

filetmignon821

#7 h Aug 2, 2012, 1:01 AM • 2 Y

Y by Adventure10, Mango247

Zhero wrote:

Quote:

so k must be 0.

Why?

Because if k is not 0, $f(P^ac)=c(kP^a+1)$ is divisible by some prime not included in our product P. Unless c=0, but this is ok because if c=0 then p|f(p) for all p.

EDIT: Ultimately, this solution is identical to that of the same condition with polynomials, except we need to do a little extra for this problem, because the polynomial version would be finished after the step where $f(P^ac)=c(kP^a+1)$ .

Z K Y

The post below has been deleted. Click to close.

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

Zhero

2043 posts

Zhero

#8 h Aug 2, 2012, 3:35 PM • 3 Y

Y by TheThor, Adventure10, Mango247

Okay, I see. Thank you for clearing that up.

However, the problem specifies that the domain and range of $f$ is the set of positive integers, so you're not actually allowed to plug in 0.

Z K Y

The post below has been deleted. Click to close.

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

filetmignon821

292 posts

filetmignon821

#9 h Aug 4, 2012, 9:05 PM • 2 Y

Y by Adventure10, Mango247

Zhero wrote:

Okay, I see. Thank you for clearing that up.

However, the problem specifies that the domain and range of $f$ is the set of positive integers, so you're not actually allowed to plug in 0.

Oops sorry. But i think we can make a similar argument using f(1)=c and $f(P^ac+1)=c(kP^a+1)$ .

Z K Y

The post below has been deleted. Click to close.

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

mathocean97

606 posts

mathocean97

#10 h Sep 15, 2013, 3:36 PM • 4 Y

Y by nguyenhaan2209, XbenX, Adventure10, Mango247

Alternative solution:

So assume the only primes dividing some $f(n)$ are $p_1, p_2, \cdots, p_k$ , and let $\gcd(f(1), f(2), f(3), \cdots) = p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_k^{e_k}$ . (It is possible for some $e_i = 0$ ).
Note that $p_i^{e_i+1} \vert f(x+p_i^{e_i+1}) - f(x)$ . Because the $\gcd = p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_k^{e_k}$ , we can find a $x_i$ so that $p_1^{e_i+1} \not\vert f(x_i)$ for any $1 \le i \le k$ . Now consider the set of congruences $x \equiv x_i \pmod{p_i^{e_i+1}}$ for $1 \le i \le k$ . By the Chinese Remainder Theorem, this gives an arithmetic progression of solutions for $x$ . Call the set of elements in this progression $S$ .

Then for all $x \in S$ we can write $f(x) = p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_k^{e_k} \cdot q$ . By our construction of $x$ , $p_i \not\vert q$ for all $i$ . But the since the only primes dividing some $f(n)$ are the $p_i$ , we get that $q = 1$ . So all elements $x \in S$ , $f(x) = p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_k^{e_k}$ . Since $f$ is nonconstant, we can take a $y$ so that $f(y) \not= p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_k^{e_k}$ , and then $x-y \vert f(x) - f(y) \implies x-y \vert p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_k^{e_k}-f(y)$ when $x \in S$ . But $x-y$ can get arbitrarily large, contradiction.

Z K Y

The post below has been deleted. Click to close.

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

mathdebam

361 posts

mathdebam

#11 h Mar 8, 2014, 2:37 PM • 1 Y

Y by Adventure10

to filetmiqnon821 the function maps from positive integers to itself............................how can u take 0.

Z K Y

The post below has been deleted. Click to close.

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

JuanOrtiz

366 posts

JuanOrtiz

#12 h Apr 18, 2014, 5:58 PM • 2 Y

Y by Adventure10, Mango247

Suppose the problem is false. Then there exists a $k \in \mathbb{N}$ such that there exists distinct primes $p_1$ , ..., $p_k$ such that there exists functions $g_i : \mathbb{N} \mapsto \mathbb{N}_0$ such that $f(a)=\prod_{i=1}^k p_i^{g_i(a)}$ , $\forall a \in \mathbb{N}$ .

Now, take $b = M \left( \prod_{i=1}^k p_i^{g_i(a)+1} \right) + a$ , for any $M \in \mathbb{N}$ . Then we have

$X = \left( \prod_{i=1}^k p_i^{g_i(a)+1} \right)$ $|$ $b-a$ $|$ $f(b)-f(a) = \prod_{i=1}^k p_i^{g_i(b)} - \prod_{i=1}^k p_i^{g_i(a)}$ .

Notice that $v_{p_i}(X) = g_i(a)+1$ for all $i \le k$ , and therefore $v_{p_i}(f(b)-f(a)) \ge g_i(a)+1 = v_{p_i}(f(a))+1$ . So we must have $v_{p_i}(f(a))=v_{p_i}(f(b))$ for all $i \le k$ . But since no other prime divides $f(x)$ (for all $x$ ), then we have $f(a)=f(b)$ for any $M$ .

Notice that we can choose $M$ as big as we want, and they all generate different $b$ 's. Therefore, since $f$ is not constant, we can take $c$ such that $f(c) \neq f(a)$ . For any $M$ we must have $b-c | f(b)-f(c) = f(a)-f(c)$ and so $|b-c| \le f(a)-f(c)$ and so $b \le f(a)-f(c)+c$ . But if we choose a $M$ that is very very gigantic, this will be impossible.

So we're done.

Z K Y

The post below has been deleted. Click to close.

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

junioragd

314 posts

junioragd

#13 h Feb 5, 2015, 2:43 PM • 2 Y

Y by Adventure10, Mango247

Very easy for $N3$ ,but still very nice.Let f(1)=p1^a1*p2^a2*...pn^an.Now,if we pick a number of form $S*k+1$ where $k$ is an arbirtary positive integer and $S=f(1)*p1*p2...*pn$ ,then $f(S*k+1)$ is equal to $f(1)$ ,so we have infinity many integers $c$ such that $f(c)=f(1)$ ,so we can pick an integer $n$ such that $f(n)$ isn't equal $f(1)$ (function isn't constant),so we have
$n$ -very big $c$ divides $f(n)-f(1)$ ,but this is a contradiction cause we can pick an arbirtary large $c$ .

Z K Y

The post below has been deleted. Click to close.

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

va2010

1276 posts

va2010

#14 h Jun 2, 2015, 11:14 PM • 2 Y

Y by Pluto1708, Adventure10

We adapt the proof of Schur's theorem from Problems from the book. Again, let $g(x) = f(x+1)$ , so the domain of $g$ is nonnegative integers. Now if $g(0) = 0$ the question is trivial, because $f(p)$ is a multiple of $p$ for all primes $p$ . Now consider the function $h(x) = \frac{g(xg(0))}{g(0)}$ . Now this is integer valued, because $\frac{g(xg(0)) - g(0)}{xg(0)}$ is an integer, implying this result.

Now observe that it is sufficient to show that $h$ has infinitely many prime divisors. But this is easy. Assume that the largest prime divisor dividing any element of $f$ is $P$ , and now observe that $h(xP!) - h(0) \equiv 0 \pmod{P!}$ , so $h(xP!) \equiv 1 \pmod{P!}$ . Hence, $h(xP!) = 1$ for all integers $x$ , but then $h(xP!) - h(2) > xP! - 2$ , which is false for significantly large $x$ , so we are done.

Z K Y

The post below has been deleted. Click to close.

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

Aiscrim

408 posts

Aiscrim

#15 h Jan 25, 2016, 1:16 PM • 3 Y

Y by Crimson., Adventure10, Mango247

Lemma: For a fixed $c$ we can only have finitely many $x\in \mathbb{N}$ s.t. $f(x)=c$ .
Proof: Going by contradiction, let $M$ be the (infinite) set of positive integers with $f(x)=c$ . As $f$ is nonconstant, there exists a positive integer $n$ s.t. $f(n)\ne c$ . For any $x\in M$ we have that $x-n$ divides $c-f(n)$ . As $x-n$ is unbounded, we get that $f(n)=c$ , contradiction.

Lemma: Given a positive integer $n$ such that $f(n)\ne 1$ , we can find a positive integer $m$ such that $f(n)|f(m)$ and $f(m)$ has at least one prime divisor which cannot be found in $f(n)$ .
Proof: Let $f(n)=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$ and denote $a=p_1^{\alpha_1+1}p_2^{\alpha_2+1}...p_k^{\alpha_k+1}$ . Then $a|f(n+a)-f(n)$ and $a|f(n+ta)-f(n+(t-1)a)$ , hence (by summing) $a|f(n+ta)-f(n)$ for all positive integers $n$ . By the previous lemma, $f(n+ta)$ cannot be equal to $f(n)$ for all values of $t$ . Let $k$ be a positive integer such that $f(n+ka)\ne f(a)$ . As $a|f(n+ka)-f(n)$ , we infer that $f(n)|a|f(n+ka)-f(n)$ , hence $f(n+ka)=f(n)r$ with $r\ne 1$ . We get $p_1...p_k|r-1$ , so $r$ has a prime divisor which is not among $p_1,...,p_k$ , i.e. $f(n+ka)$ has all the prime divisors of $f(n)$ and at least one more.

As $f$ is nonconstant, we have a positive integer $n$ such that $f(n)\ne 1$ . Starting with $n$ and applying the second lemma repeatedly, we find positive integers $m$ such that the number of prime divisors of $f(m)$ is as big as we want, whence the conclusion.

Z K Y

The post below has been deleted. Click to close.

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

thdnder

194 posts

thdnder

#51 h Feb 9, 2024, 7:49 AM

Y by

Assume the contrary, let $p_1, p_2, \dots, p_k$ be all primes dividing the sequence $f(1), f(2), f(3), \dots$ . Let $f(1) = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ and let $T = p_1^{a_1+1}p_2^{a_2+1}\cdots p_k^{a_k+1}$ . Then consider the following claim:

Claim: $f(aT + 1) = f(1)$ for all $a \ge 1$ .

Proof. Note that $T \mid aT + 1 - 1 \mid f(aT + 1) - f(1)$ , hence $\nu_{p_i}(T) = a_i+1 \le \nu_{p_i}(f(aT + 1) - f(1))$ . If $\nu_{p_i}(f(1)) \neq \nu_{p_i}(f(aT+1))$ , then $a_i+1 \le \nu_{p_i}(f(aT+1) - f(1)) = \min(\nu_{p_i}(f(1)), \nu_{p_i}(f(aT+1))) \le \nu_{p_i}(f(1)) = a_i$ , a contradiction. Therefore $\nu_{p_i}(f(1)) = \nu_{p_i}(f(aT+1))$ for all $i$ , which means $f(1) = f(aT+1)$ for all $a \in \mathbb{N}$ .

Now take $b$ such that $f(b) \neq f(1)$ . Then for large $n$ , we have $nT + 1 - b \mid f(nT + 1) - f(b) = f(1) - f(b)$ , thus $nT + 1 - b \le |f(1) - f(b)|$ , contradicting the fact that $n$ is sufficiently large. Hence $f(b) = f(1)$ for all $b$ , contradicting $f$ is nonconstant. So we're done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

OronSH

1724 posts

OronSH

#52 h Feb 24, 2024, 8:56 PM • 2 Y

Y by megarnie, alsk

Otherwise suppose $f$ is $p$ -smooth. For primes $2\le q\le p$ take $n_q$ to be the smallest positive integer such that $\nu_q(f(n_q))$ is minimized and call this minimum $m_q.$ Then $f(n_q+k\cdot q^{m_q+1})$ also shares this minimum $\nu_q$ for any positive integer $k.$ Now by chinese remainder theorem there is a solution to the congruence system $z \equiv n_q\pmod{q^{m_q+1}}$ for all $q.$ We then have $\nu_q(f(z))=m_q$ for all $q.$ Now let $\prod_{q\in\mathbb P,q\le p}q^{m_q}=\mathcal L.$ Consider $\frac{f(z)}{\mathcal L}.$ By $\nu_q$ it cannot be divisible by any prime $2\le q\le p.$ By assumption it cannot be divisible by any prime $>p,$ so it must be $1$ so $f(z)=\mathcal L.$ Similarly, we have $f(z+k\mathcal L\cdot p\#)=\mathcal L$ for any positive integer $k,$ where $p\#$ is the primorial of $p.$ Thus $f(x)=\mathcal L$ for infinitely many $x.$ There must exist some $y$ with $f(y)\ne\mathcal L.$ However we must have $x-y\mid \mathcal L-f(y)$ for arbitrarily large $x,$ contradiction. Thus our original assumption is false.

Z K Y

The post below has been deleted. Click to close.

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

jp62

53 posts

jp62

#53 h Feb 25, 2024, 9:22 AM

Y by

Suppose for the sake of contradiction that the only primes dividing any value of $f$ are $p_1$ through $p_n$ .
Let $P=f(1)\times\prod p_i$ , so that $\nu_{p_i}(P)>\nu_{p_i}(f(1))$ for each $p_i$ .
$P\mid f(1+P)-f(1)$ , so $\nu_{p_i}(f(1))=\nu_{p_i}(f(1+P))$ for each $p_i$ . This means that $f(1+P)=f(1)$ .
Similarly we can prove by induction that $f(1+kP)=f(1)$ for all positive integers $k$ .
Then for any integer $m$ , choose $k$ large such that $|kP+1-m| > |f(1)-f(m)|$ . Then $kP+1-m\mid f(kP+1)-f(m)=f(1)-f(m)$ , so $f(1)=f(m)$ for all $m$ .
But $f$ is non-constant, contradiction.

Z K Y

The post below has been deleted. Click to close.

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

Pyramix

419 posts

Pyramix

#54 h Mar 27, 2024, 7:18 AM

Y by

Suppose for contradiction there are only finitely many such primes, say from the set $\{p_1,p_2,\ldots,p_k\}$ . We claim that the function has to be constant. Define $P=f(1)\cdot p_1p_2\cdots p_k$ .

Claim: $f(Pn+1)=f(1)$ for each $n$ .
Proof. From original condition, $P\mid f(Pn+1)-f(1)$ , and since $f(1)\mid P$ we have that $f(1)\mid f(Pn+1)$ . Let $f(Pn+1)=xf(1)$ . Then, $p_i\mid x-1$ for each $1\leq i\leq k$ . Suppose $x\ne 1$ . Since $x$ is not divisible by any prime from $\{p_1,p_2,\ldots,p_k\}$ , there is some new prime that divides $x$ . So there's a new prime which divides $f(Pn+1)$ , which is impossible. Hence, $x=1$ is forced.So, $f(Pn+1)=f(1)$ , as claimed.

We now show that $f(n)=f(1)$ for each $n$ . Suppose $f(n)\ne f(1)$ . Then, for each positive integer $m$ , we have (from our claim)
$Pm+1-n\mid f(Pm+1)-f(n)=f(1)-f(n)$ Since $m$ can be arbitrarily large, it follows that $f(1)-f(n)$ has infinitely many divisors, which is impossible. So, $f(1)=f(n)$ is forced for each $n$ . So, the function is constant.

Z K Y

The post below has been deleted. Click to close.

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

dolphinday

1313 posts

dolphinday

#55 h Mar 30, 2024, 5:14 PM • 1 Y

Y by megarnie

FTSOC that there are finitely many $p$ that divide $f$ . Then let $f(1) = k = \prod_i p_i^{e_i}$ . Then let $\mathcal{P} = \prod_i p_i^{e_i + 1}$ . Then we have(for some arbitrary constant $M$ ) $M\mathcal P + 1 - 1 \mid f(M\mathcal P + 1) - k$ so it follows that $\nu_{p_i}(f(M\mathcal P + 1)) = \nu_{p_i}(k) \implies f(M\mathcal P + 1) = k$ . Then take sufficiently large $M$ and some arbitrary $t$ to get $M\mathcal P + 1 - t \mid k - f(t)$ to get a size contradiction, implying $k = f(t)$ for all $t$ . However this is a contradiction as $f$ is nonconstant, done.

Z K Y

The post below has been deleted. Click to close.

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

ismayilzadei1387

219 posts

ismayilzadei1387

#56 h Apr 4, 2024, 2:04 PM

Y by

Suppose that it is not true.
Let, $p_{1},\cdots,p_{n}$ are the prime factors of $f(1),f(2),\cdots$
Then $f(a)=p^{a_{1}}_{1} \cdots p^{a_{k}}_{k}$
Let be some $x_{\mathcal{Q}}=\mathcal{Q}*p^{a_1+1}_1 \cdots p^{a_k+1}_k$
So,that $x_{\mathcal{Q}} \vert (f(a+x)-f(a))$
$\nu_{p_i}{f(a)} < \nu_{p_i}{f(x_{\mathcal{Q}})}$
From that, $\nu_{p_i}{f(a)} = \nu_{p_i}{f(a+x_{\mathcal{Q}})}$
Thus it follows every $\mathcal{Q} \geq 1$ this identity is true.
But, if we plug $P(a+x_{\mathcal{Q}}+1,1)$
Since that $f(a)=f(1)$
Which gives us contradiction.

This post has been edited 1 time. Last edited by ismayilzadei1387, Apr 4, 2024, 2:05 PM

Z K Y

The post below has been deleted. Click to close.

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

Thapakazi

53 posts

Thapakazi

#57 h May 27, 2024, 8:39 AM • 1 Y

Y by surpidism.

Solved with surpidism.

Assume the contrary. The condition can be translated to $N \mid a - b \implies N \mid f(a) - f(b).$ Take an $N$ such that $\nu_p(N) > \nu_p(f(1))$ for all primes $p \mid f(1).$ Then,

$f(kN+1) \equiv f(1) \pmod N.$
As, $\nu_p(N) \leq \nu_p(f(kN+1) - f(1)),$ forcing $\nu_p(f(kN+1)) = \nu_p(f(1)),$ otherwise

$\nu_p(f(1)) < \nu_p(N) \leq \nu_p(f(kN+1) - f(1) \leq \min(\nu_p(f(kN+1)), \nu_p(f(1)))$
a contradiction. As $f(kN+1)$ and $f(1)$ share the same prime divisors, we get $f(kN+1) = f(1).$ To finish, note that

$kN + 1 - a \mid f(kN+1) - f(a) = f(1) - f(a).$
Taking arbitrarily large $k$ such that $|f(a) - f(1)| < kN+1 - a \leq |f(1) - f(a)|$ , a contradiction.

This post has been edited 2 times. Last edited by Thapakazi, May 27, 2024, 8:42 AM

Z K Y

The post below has been deleted. Click to close.

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

fearsum_fyz

48 posts

fearsum_fyz

#58 h Aug 7, 2024, 4:58 AM • 1 Y

Y by Ywgh1

Assume, for the sake of contradiction, that there are only finitely many such primes $p_1, p_2, ... p_n$ .
Substituting $a = (f(1) p_1 p_2 p_3 \ldots p_n) + 1$ and $b = 1$ , we get:
$(f(1) p_1 p_2 p_3 \ldots p_n) | f((f(1) p_1 p_2 p_3 \ldots p_n) + 1) - f(1)$
$\implies f((f(1) p_1 p_2 p_3 \ldots p_n) + 1) = k (f(1) p_1 p_2 p_3 \ldots p_n) + f(1) = f(1) (k p_1 p_2 p_3 \ldots p_n + 1)$ which clearly has a prime divisor other than $p_1, p_2, ... p_n$ , a contradiction.

Z K Y

The post below has been deleted. Click to close.

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

Ywgh1

136 posts

Ywgh1

#59 h Aug 27, 2024, 8:45 AM

Y by

2009 N3

Assume FTSOC otherwise, and let { $p_1$ , $p_2$ , $\ldots$ , $p_n$ } be the set of primes dividing $f$ . Let $Q=f(1)\cdot p_1p_2\cdots p_n$ . Then we Claim that.
$f(Qn+1)=f(1) .$
Proving that we get that $m-Qn\mid f(m)-f(1)$ ,we can take $n$ as it approaches infinity, so $f(m)=f(1)$ for all $m$ , a contradiction.

This post has been edited 1 time. Last edited by Ywgh1, Aug 27, 2024, 8:45 AM

Z K Y

The post below has been deleted. Click to close.

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

N3bula

254 posts

N3bula

#60 h Oct 5, 2024, 6:40 AM

Y by

Let $P$ be the set of primes dividing $f$ . Let $m$ be a value such that $f(m)=\prod_{p_i\in P}p_i^{\alpha_i}$ , such that $\alpha_i>0$ for all $i$ ,
now let $N$ be a value such $N=\prod_{p_i\in P}p_i^{\beta_i}$ such that $\beta_i>\alpha_i$ for all $i$ . Thus we have that $N\mid f(N+m)-f(m)$ however we can see
that $\nu_{p_i}(f(N+m))=\nu_{p_i}(f(m))$ , thus we get $f(N+m)=f(m)$ , so we get arbitrarily large values that are equal to $f(m)$ . Now by taking a sufficently large value
$k$ such that $f(k)=f(m)$ we can get for values below a certain constant, are constant and by using increasingly large values of $k$ we get the function must be constant.

Z K Y

The post below has been deleted. Click to close.

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

lelouchvigeo

172 posts

lelouchvigeo

#61 h Dec 15, 2024, 11:17 AM

Y by

Easy
FTSOC, assume there are finite number of primes $p_1,p_2,...p_n$ that divide any $f(k)$
Consider $a=kn$ and $b=mn$ and let n be such that $GCD ( n, p_i) = 1$ for all $i$
SInce $n(k-m) \mid f(nk) - f(n)$ and due to our above condition we will have GCD $( f(kn) , f(mn) ) =1$
But since our number of primes are limited we have a contradiction

Z K Y

The post below has been deleted. Click to close.

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

Mathandski

715 posts

Mathandski

#62 h Jan 14, 2025, 8:49 PM

Y by

Please contact westskigamer@gmail.com if there is an error with my solution for cash bounties by 3/18/2025.

Attachments:

This post has been edited 2 times. Last edited by Mathandski, Jan 16, 2025, 5:27 AM

Z K Y

The post below has been deleted. Click to close.

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

AshAuktober

927 posts

AshAuktober

#63 h Jan 15, 2025, 3:14 AM

Y by

I have the exact same solution as mathocean97

Z K Y

The post below has been deleted. Click to close.

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

bin_sherlo

662 posts

bin_sherlo

#64 h Jan 20, 2025, 9:03 AM • 2 Y

Y by MihaiT, MS_asdfgzxcvb

Assume contrary. Let $p_1,\dots,p_k$ be the set of prime divisors of $f$ . Let $f(1)=p_1^{x_1}\dots p_k^{x_k}$ for $x_i\geq 0$ . For $m_i>x_i$ , we have $p_1^{m_1}\dots p_k^{m_k}|f(p_1^{m_1}\dots p_k^{m_k}n+1)-f(1)$ and $p_i^{x_i+1}|f(p_1^{m_1}\dots p_k^{m_k}n+1)-p_1^{x_1}\dots p_k^{x_k}$ . Thus, $\nu_{p_i}(f(p_1^{m_1}\dots p_k^{m_k}n+1))=x_i$ which implies $f(p_1^{m_1}\dots p_k^{m_k}n+1)=f(1)$ . Pick some $x$ and $n\gg f(x)$ in order to have
$p_1^{m_1}\dots p_k^{m_k}n+1-x|f(p_1^{m_1}\dots p_k^{m_k}n+1)-f(x)=f(1)-f(x)$ $f(1)-f(x)$ is a constant while $p_1^{m_1}\dots p_k^{m_k}n+1-x$ increases hence $f(x)=f(1)$ which gives a contradiction since $f$ is non-constant as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

asdf334

7586 posts

asdf334

#65 h Mar 19, 2025, 3:02 AM • 1 Y

Y by OronSH

fun problem here is sort of how i motivate it

Okay so first off if there's a number where $f(c_p)\not\equiv 0\pmod p$ then essentially $f(c_p+kp)\not\equiv 0\pmod p$ always. So if FTSOC there's a finite number of primes $p$ that make up the prime factorization of any $f(c)$ , then if there's a prime $p$ that is non-permanent, or that doesn't divide EVERY single one of the outputs of $f$ , then there's an infinite arithmetic sequence of inputs that yield outputs not divisible by $p$ , where the common difference is $p$ .

That means: if $p_1,\dots,p_a$ are the non-permanent primes, then $P=p_1\dots p_a$ is such that by CRT there is some sequence of numbers $f(c+kP)$ for some $c$ and all $k\ge 0$ where each of those outputs is not divisible by any $p_i$ . In other words, the permanent primes $q_1,\dots,q_b$ , which are divisible by EVERY output of $f$ , are the only primes making up the prime factorization of $f(c+kP)$ .

So brainstorming time. It looks like things worked because we found a MINIMAL $\nu_p$ in the non-permanent primes (there, it was zero). We'd like to get rid of some of the $q_i$ primes. Here's the idea: what we just did was decrease the set of inputs of $f$ to some arithmetic sequence, and by restricting the domain so, we were able to cut out some of the primes. So we'd like to further reduce this arithmetic sequence, and cut out more primes.

But now all of the primes $q_1,\dots,q_b\mid f(c+kP)$ , which is a little annoying. In light of this, we write $f(c+kP)=g(c+kP)\cdot q_1^n$ , where $n$ is the minimal $\nu_{q_1}$ achieved.

At this point I was sort of able to tell that something nice could happen, so I switched to this: $f(x)=g(x)\cdot p^n$ in general, with $n$ allowed to be $0$ , really just focusing on a single prime, including both non-permanent and permanent. The hope was that I would get a nice arithmetic sequence for every prime where each output of any input in the arithmetic sequence would not be divisible by the prime that corresponded to that arithmetic sequence.

So: $a-b\mid g(a)\cdot p^n - g(b)\cdot p^n$ . Assume also that $g(a)\cdot p^n$ has a $\nu_p$ equal to $n$ ; that's why we specified the minimum condition---now choose $p^{n+1}\mid a-b$ , which we do in order to gain $\nu_p(g(b)\cdot p^n)=n$ as well.

And boom: this creates an infinite arithmetic sequence of inputs $c_p+kp^{n_p+1}$ where $c_p$ is some residue, $k\ge 0$ , and $n_p$ is the minimal $\nu_p$ that may be achieved.

Each of these inputs has an output with $\nu_p$ equal to $n_p$ .

By CRT, the intersections of all of the arithmetic sequences we get from looking at each prime will itself be an infinite arithmetic sequence. Each of the outputs of this new sequence can only use our original finite number of primes $p_1,\dots,p_m$ , but the $\nu_{p_i}$ of any output for any $i$ is fixed at the minimal possible for that $p_i$ , as these outputs are part of every one of the $m$ arithmetic sequences.

In other words we have an infinite arithmetic sequence of inputs where the outputs are all the same number $C$ .

Now take $b$ large as an input in this arithmetic sequence, and choose $A$ so that $f(A)\ne C$ to be fixed. We get
$A-b\mid f(A)-C$ and as $b$ goes to infinity while everything else is constant, this is a contradiction. good stuff man! that was quite good xdxd not locked at all will fail usamo but oh well its ok $\blacksquare$

This post has been edited 1 time. Last edited by asdf334, Mar 19, 2025, 3:05 AM

Z K Y