GCD Functional Equation

The post below has been deleted. Click to close.

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

1207 posts

#1 h Jun 25, 2019, 5:36 PM • 15 Y

Y by anantmudgal09, rightways, Vietjung, adityaguharoy, Idio-logy, RedFireTruck, ImSh95, mathematicsy, megarnie, Mahmood.sy, Stuart111, Adventure10, Mango247, zhihanpeng, LP088

Let $f: \mathbb Z\to \{1, 2, \dots, 10^{100}\}$ be a function satisfying
$\gcd(f(x), f(y)) = \gcd(f(x), x-y)$ for all integers $x$ and $y$ . Show that there exist positive integers $m$ and $n$ such that $f(x) = \gcd(m+x, n)$ for all integers $x$ .

Ankan Bhattacharya

Z K Y

The post below has been deleted. Click to close.

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

pinetree1

1207 posts

pinetree1

#2 h Jun 25, 2019, 5:58 PM • 10 Y

Y by yayups, Idio-logy, Kyolcu22, Feng_230, RedFireTruck, ImSh95, megarnie, Stuart111, Adventure10, Mango247

Pretty fun problem! The key claim is the following.

Claim: There exists some integer $r$ satisfying
$r \equiv x\pmod {f(x)}$ for all $x$ .

Proof. We'll construct $r$ with CRT by computing the correct residue for $r$ modulo each prime power. For every prime $p$ dividing some $f(x)$ , choose $x_p$ such that $\nu_p(f(x_p))$ is maximal. Then there is some $r$ satisfying
$r\equiv x_p\pmod {p^{\nu_p(f(x_p))}}$ for all $p$ . We want to show that $r\equiv y\pmod {f(y)}$ for all $y$ , so it suffices to show that $r\equiv y\pmod {p^k}$ for any prime power $p^k\mid f(y)$ . Indeed, since $p^k\mid f(x_p)$ and $f(y)$ , we know that
$\begin{align*} \gcd(f(x_p), f(y)) = \gcd(f(x_p), x_p-y) &\implies p^k\mid x_p-y \\ &\implies r\equiv x_p\equiv y\pmod {p^k}, \end{align*}$ which proves the claim. $\blacksquare$

Now for any $x$ , we have
$\gcd(f(x), f(r)) = \gcd(f(x), x-r) = f(x) \implies f(x)\mid f(r).$ But then
$f(x) = \gcd(f(x), f(r)) = \gcd(f(r), r-x).$ Thus, taking $n = f(r)$ and $m = k\cdot f(r) - r$ for sufficiently large $k$ gives positive $m$ and $n$ such that $f(x) = \gcd(m+x, n)$ .

Z K Y

The post below has been deleted. Click to close.

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

Tintarn

9042 posts

Tintarn

#3 h Jun 25, 2019, 5:59 PM • 4 Y

Y by adityaguharoy, RedFireTruck, megarnie, Adventure10

Solution

Z K Y

The post below has been deleted. Click to close.

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

62861

3564 posts

62861

#4 h Jun 25, 2019, 6:16 PM • 8 Y

Y by v_Enhance, Vietjung, adityaguharoy, RedFireTruck, megarnie, aopsuser305, centslordm, Adventure10

Simple follow-up (and probably the question I should have asked instead): how many such functions are there?

This post has been edited 1 time. Last edited by 62861, Jun 25, 2019, 6:16 PM

Z K Y

The post below has been deleted. Click to close.

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

TheUltimate123

1740 posts

TheUltimate123

#5 h Jun 25, 2019, 8:40 PM • 7 Y

Y by Aryan-23, RedFireTruck, 407420, 554183, MrOreoJuice, megarnie, Adventure10

Let $p\le 10^{100}$ be a prime. Set $x$ such that $\nu_p\big(f(x)\big)$ is maximal, so that for all $y$ , $\nu_p\big(f(y)\big)=\min\big[\nu_p\big(f(x)\big),\,\nu_p(x-y)\big].$ It is immediate that all $y$ of the form $x+kp^{\nu_p(f(x))}$ have maximal $\nu_p\big(f(y)\big)$ , so $\nu_p\big(f(y)\big)$ is maximal when $y\equiv x\pmod{p^{\nu_p(f(x))}}.\qquad(*)$ By the Chinese Remainder Theorem, there exists negative $z$ obeying $(*)$ , so taking $m=-z$ and $n=f(z)$ yields $f(y)=\gcd(n,\,y+m)$ , as desired. $\square$

Z K Y

The post below has been deleted. Click to close.

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

rocketscience

466 posts

rocketscience

#6 h Jun 30, 2019, 8:39 PM • 7 Y

Y by mathisawesome2169, adityaguharoy, RedFireTruck, megarnie, Epsilon-, Adventure10, Mango247

Let $P(x, y)$ denote the assertion, as usual. Note that if $f$ is such a function, then $g(x) \equiv f(x + c)$ works, too, so WLOG assume $f$ achieves its maximum at $f(0)=C$ . Considering $P(0,x)$ gives
$\gcd(C, f(x)) = \gcd(C, x) \quad (\heartsuit)$ so in particular if $C \mid x$ then $C \mid f(x)$ which implies $f(x) = C$ by maximality. Now let $x$ be arbitrary and let $d = \gcd(C, x)$ . Note that $d \mid f(x)$ , so write $f(x) = kd$ for some $k \in \mathbb{N}$ with $\gcd(k, C/d) = 1$ by $(\heartsuit)$ . I claim $k=1$ . Pick some $y'$ satisfying
$\begin{align*} y' &\equiv 0 \pmod{C/d} \\ y' &\equiv x/d \pmod{k} \\ \end{align*}$ and let $y = y'd$ so that $C \mid y$ and $f(x) \mid y-x$ . By an earlier observation, we must have $f(y) =C$ , but taking $P(x, y)$ gives
$\gcd(f(x), f(y)) = \gcd(f(x), x-y) = f(x)$ implying $f(x) \mid f(y) = C$ and thus $k \mid C/d$ . As $\gcd(k, C/d)=1$ , we must have $k=1$ , as desired. It follows that $f(x) = \gcd(C, x)$ for all $x$ , and accounting for the shift 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.

v_Enhance

6877 posts

v_Enhance

#7 h Jul 3, 2019, 5:48 AM • 11 Y

Y by adityaguharoy, v4913, RedFireTruck, HamstPan38825, mathematicsy, centslordm, megarnie, IMUKAT, maths_arka, Adventure10, Mango247

Official solution: Let $\mathcal{P}$ be the set of primes not exceeding $10^{100}$ . For each $p \in \mathcal{P}$ , let $e_p = \max_x \nu_p(f(x))$ and let $c_p \in \operatorname{argmax}_x \nu_p(f(x))$ .

We show that this is good enough to compute all values of $x$ , by looking at the exponent at each individual prime.

Claim: For any $p \in \mathcal P$ , we have $\nu_p(f(x)) = \min(\nu_p(x - c_p), e_p)$ .

Proof. Note that for any $x$ , we have $\gcd(f(c_p), f(x)) = \gcd(f(c_p), x - c_p)$ . We then take $\nu_p$ of both sides and recall $\nu_p(f(x)) \le \nu_p(f(c_p)) = e_p$ ; this implies the result. $\blacksquare$

This essentially determines $f$ , and so now we just follow through. Choose $n$ and $m$ such that $\begin{align*} n &= \prod_{p \in \mathcal P} p^{e_p} \\ m &\equiv -c_p \pmod{p^{e_p}} \quad \forall p \in \mathcal P \end{align*}$ the latter being possible by Chinese remainder theorem. Then, from the claim we have $\begin{align*} f(x) &= \prod_{p \in \mathcal P} p^{\nu_p(f(x))} = \prod_{p \mid n} p^{\min(\nu_p(x-c_p), e_p)} \\ &= \prod_{p \mid n} p^{\min(\nu_p(x+m), \nu_p(n))} = \gcd\left( x+m, n \right) \end{align*}$ for every $x \in {\mathbb Z}$ , as desired.

Remark: The functions $f(x) = x$ and $f(x) = |2x - 1|$ are examples satisfying the gcd equation (the latter always being strictly positive). Hence the hypothesis $f$ bounded cannot be dropped.
Remark: The pair $(m, n)$ is essentially unique: every other pair is obtained by shifting $m$ by a multiple of $n$ . Hence there is not really any choice in choosing $m$ and $n$ .

Z K Y

The post below has been deleted. Click to close.

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

FISHMJ25

293 posts

FISHMJ25

#12 h Jul 10, 2019, 12:25 AM • 2 Y

Y by RedFireTruck, Adventure10

I am probably making some mistake but i cant find it so please help. I get that for any $m,n$ the function $f(x) = \gcd(m+x, n)$ works.
We will show $\gcd ( \gcd (m+x, n), \gcd (m+y, n))= \gcd ( \gcd(m+x, n),x-y)$ Let $m+x=ka$ $n=kb$ $m+y=lc$ $n=ld$ with $\gcd (a,b)=1$ and $\gcd (c,d)=1$ Let $\gcd (k,l)=s$ so we need to show $s=\gcd ( \gcd(m+x, n),x-y)$ or $s=\gcd ( \gcd(m+x, n),(m+x)-(m+y))=\gcd ( \gcd(m+x, n),m+y)$ (because $\gcd(m+x, n)|m+x$ ) This is equivalent to $s=\gcd (k,lc)=s(k_1,l_1c)$ or $\gcd (k_1,l_1c)=1$ which is same as $\gcd (k_1,c)=1$ ( $\gcd (k_1,l_1)=1$ ) where $k=k_1s$ and $l=l_1s$ . Now if $r|k_1,c$ then from $n=k_1sa=l_1sc$ we get $k_1a=l_1c$ and $r|l_1c$ but $\gcd (r,l_1)=\gcd (k_1,l_1)=1$ so $r|c$ Then because $r|d,c$ we get $r=1$ which is wanted.

Z K Y

The post below has been deleted. Click to close.

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

Tintarn

9042 posts

Tintarn

#13 h Jul 10, 2019, 5:29 PM • 4 Y

Y by adityaguharoy, RedFireTruck, Adventure10, Mango247

FISHMJ25 wrote:

I am probably making some mistake but i cant find it so please help.

No mistake. Everything you said is correct. Just that you didn't solve the problem.
The problem does not ask you to show that a function of this specific form satisfies the functional equation but that every function satisfying the functional equation is already of this specific form.

Z K Y

The post below has been deleted. Click to close.

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

FISHMJ25

293 posts

FISHMJ25

#14 h Jul 11, 2019, 11:16 AM • 3 Y

Y by RedFireTruck, Adventure10, Mango247

Tintarn wrote:

FISHMJ25 wrote:

I am probably making some mistake but i cant find it so please help.

No mistake. Everything you said is correct. Just that you didn't solve the problem.
The problem does not ask you to show that a function of this specific form satisfies the functional equation but that every function satisfying the functional equation is already of this specific form.

I understand that but in other solutions they showed that only specific $m$ and $n$ work which is contradiction with what i wrote.

Z K Y

The post below has been deleted. Click to close.

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

Tintarn

9042 posts

Tintarn

#15 h Jul 11, 2019, 11:24 AM • 2 Y

Y by RedFireTruck, Adventure10

Well, they showed that for a given function $f$ , essentially only a unique value of $m$ and $n$ works. But of course there is more than one such function $f$ ...

Z K Y

The post below has been deleted. Click to close.

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

FISHMJ25

293 posts

FISHMJ25

#16 h Jul 11, 2019, 11:41 AM • 2 Y

Y by RedFireTruck, Adventure10

I get it thanks i appreciate it!

Z K Y

The post below has been deleted. Click to close.

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

sriraamster

1492 posts

sriraamster

#17 h Nov 26, 2019, 7:46 AM • 3 Y

Y by 554183, megarnie, Adventure10

Solution with mfang92

Fix $p \le 10^{100}$ and choose $x$ such that $\nu_{p} (f(x))$ is maximal. Then from the condition, $\min(\nu_p(f(x)), \nu_p(f(y)) = \min(\nu_p(f(x)), \nu_p(x-y)) \implies \nu_p(f(y)) = \min(\nu_p(f(x)), \nu_p(x-y))$ so we have that $\nu_p(f(y)) = \nu_p(f(x))$ (i.e, $\nu_p(f(y))$ is maximized) if $\nu_p(x-y) \ge \nu_p(f(x))$ or $y = kp^{\nu_p(f(x)} + x$ . Now, we want $\nu_p(f(y)) = \min(\nu_p(m+y), \nu_p(n)).$ Taking $n = f(x)$ and $m = -x$ , we get $\nu_p(f(y)) = \min(\nu_p(-x+y), f(x))$ as desired. $\blacksquare$

This post has been edited 1 time. Last edited by sriraamster, Nov 26, 2019, 7:46 AM

Z K Y

The post below has been deleted. Click to close.

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

pad

1671 posts

pad

#19 h Dec 8, 2019, 2:50 AM • 5 Y

Y by megarnie, mzxj, tapir1729, Adventure10, vrondoS

Taking the $\nu_p$ of both sides gives
$\min(\nu_p(f(x)), \nu_p(f(y))) = \min(\nu_p(f(x)), \nu_p(x-y)).$ Since $f$ is bounded, take $x_{max}$ such that $\nu_p(f(x_{p,max}))$ is maximal, and call this value $C_p$ . Why? Then
$\nu_p(f(y)) = \min(C_p, \nu_p(x_{p,max}-y)) = \min(C_p, \nu_p(y-x_{p,max}).$ What we want is to find integers $m,n$ such that
$\nu_p(f(y)) = \min(\nu_p(n), \nu_p(m+y)).$ So taking $\nu_p(n) = C_p$ and $m=-x_{p,max}$ works. But we want this single values for $m,n$ regardless of $p$ . We can fix this with CRT: the following works:
$\begin{align*} n &= \prod_{p \le 10^{100}} p^{C_p} \\ m &\equiv -x_{p,max} \pmod{p^{C_p}}. \end{align*}$

Z K Y

The post below has been deleted. Click to close.

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

math_pi_rate

1218 posts

math_pi_rate

#20 h Mar 16, 2020, 7:23 AM • 1 Y

Y by amar_04

Nice! Here's my solution (pretty much the same as the above solutions): First of all, it's easy to see that if $f$ is constant, then we must have $f \equiv 1$ (since this constant value divides $x-y$ for all integers $x,y$ ). In this case, $n=1$ and $m=\text{anything}$ works. So from now on assume $f$ is non-constant. Note that we have $\gcd(f(x),f(x+af(x)))=\gcd(f(x),x-(x+af(x)))=f(x) \Rightarrow f(x) \mid f(x+af(x)) \text{ } \forall a \in \mathbb{Z}$ The main claim is as follows-

CLAIM Let $k$ be an integer such that $f(k)=\max_{x \in \mathbb{Z}} f(x)$ . Then $f(x) \mid f(k)$ for all $x \in \mathbb{Z}$ .

Proof of Claim Since for any $a \in \mathbb{Z}$ , we have $f(x) \mid f(x+af(x))$ , so it suffices to show that there exists $k \in \mathbb{Z}$ such that $k \equiv x \pmod{f(x)}$ for all $x \in \mathbb{Z}$ (Since in that case $f(x) \mid f(k)$ gives that this $k$ is the same as the one given in the statement of our claim). For some $x \in \mathbb{Z}$ , consider a prime $p$ dividing $f(x)$ (at least one such prime $p$ exists since $f$ is non-constant). Let $y \in \mathbb{Z},e \in \mathbb{N}$ be the integers such that $e=\nu_p(f(y))$ is maximum as $y$ varies over $\mathbb{Z}$ . Using CRT, choose $k \equiv y \pmod{p^e}$ , and do so for all primes $p$ dividing some element in the range of $f$ . Now, for any $z \in \mathbb{Z}$ , if $p^m \mid f(z)$ with $1 \leq m \leq e$ , then $p^m \mid \gcd(f(y),f(z))=\gcd(f(y),y-z) \Rightarrow p^m \mid y-z \Rightarrow k \equiv y \equiv z \pmod{p^m}$ Thus, we can form such a $k$ using CRT for all primes dividing $f(x)$ as $x$ varies on $\mathbb{Z}$ , giving the desired result. $\Box$

Let $k$ be as in our claim. Since $f(k)$ is maximum, and $f(k) \mid f(k+af(k))$ , so we get $f(k+af(k))=f(k)$ for all $a \in \mathbb{Z}$ . Let $n=f(k)$ and $m=af(k)-k$ with $a$ sufficiently large (so that $m>0$ ). Then, using our claim, we get $f(x)=\gcd(n,f(x))=\gcd(f(-m),f(x))=\gcd(f(-m),-m-x)=\gcd(m+x,n) \text{ } \blacksquare$

This post has been edited 4 times. Last edited by math_pi_rate, Mar 16, 2020, 7:38 AM

Z K Y

The post below has been deleted. Click to close.

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

Leo.Euler

577 posts

Leo.Euler

#57 h Nov 16, 2023, 6:12 PM

Y by

Fix any prime $p$ less than $10^{100}$ . It suffices to show that the desired holds under $\nu_p$ analysis.

Let $x$ be an integer such that $\nu_p(f(x))$ is maximal. Then for any $y$ distinct from $x$ , $\nu_p(f(y)) = \nu_p(x - y).$ Taking $n=f(x)$ and $m \equiv -x \pmod{p^{\nu_p(f(x)}}$ , $y \neq x$ satisfy the desired. Realize that plugging in $x$ into the desired with these values of $m$ and $n$ returns a valid equality, as desired.

Z K Y

The post below has been deleted. Click to close.

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

shendrew7

796 posts

shendrew7

#58 h Dec 19, 2023, 3:58 AM

Y by

Suppose $S$ is the set of primes under $10^{100}$ , $p$ as an arbitrary prime in $S$ , $e_p$ be the maximum possible value $v_p(f(x))$ , and $x_p$ be a value of $x$ for which this maximum holds. Using $v_p$ and substituting $(x,y) = (x_p,t)$ , we get
$\min \left(v_p(f(x_p)), v_p(f(t))\right) = \min \left(v_p(f(x_p)), v_p(x_p-t)\right)$ $\implies v_p(f(t)) = \min(e_p, v_p(x_p-t)).$
Then we construct our values of $m$ and $n$ such that
$m = -x_p \pmod{p^{e_p}} \quad \forall \quad p \in S, \qquad n = \prod_{p \in S} p^{e_p},$
which works as
$v_p(\gcd(n, x+m)) = \min(v_p(n), v_p(x+m)) = \min(e_p, v_p(x-x_p)) = v_p(f(x))$
for all primes $p \in S$ and $x \in \mathbb{Z}$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

Shreyasharma

682 posts

Shreyasharma

#59 h Dec 20, 2023, 12:55 AM

Y by

Ew. Weird, intractable number theory because I'm bad.

The idea is to interpret the condition in $\nu_p$ . We are motivated to do so because in terms of $\nu_p$ the desired conclusion can be restated in terms of individual primes.

Then fix a prime $p$ . Then over all primes the given can be restated as,
$\begin{align*} \min(\nu_p(f(x)), \nu_p(f(y))) = \min(\nu_p(f(x)), \nu_p(x-y)) \end{align*}$ Consider $k_p$ such that $\nu_p(f(k_p))$ is maximal. Also let $\nu_p(f(k_p)) = e_p$ . Then we find we have,
$\begin{align} \nu_p(f(x)) = \min (e_p, \nu_p(x-k_p)) \end{align}$ Now a hint told me to use CRT because I'm bad. To finish note that we want to find $m$ and $n$ such that we always have,
$\begin{align*} \nu_p(f(x)) = \min(\nu_p(m+x), \nu_p(n)) \end{align*}$ over all primes $p$ .

Now choose $m$ satisfying,
$\begin{align*} m \equiv -k_p \pmod{p^{e_p}} \end{align*}$ over all $p$ . A solution is guaranteed by CRT. Similarly for $n$ choose it to satisfy,
$\begin{align*} n \equiv 0 \pmod{p^{e_p}} \end{align*}$ for all $p$ which exists, once again, by CRT. Now from $(1)$ our choices of $m$ and $n$ suffice.

Z K Y

The post below has been deleted. Click to close.

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

Markas

150 posts

Markas

#60 h May 5, 2024, 1:39 PM

Y by

Take $x_0$ such that $\nu_p(f(x_0))$ is max for some given prime p. Let $x = x_0$ , we get $\min(\nu_p(f(x_0)), \nu_p(x_0-y)) = \nu_p(f(y))$ . Now take $m \equiv -x_0 \pmod {p^{\nu_p(f(x_0))}}$ , $n \equiv f(x_0) \pmod {p^{\nu_p(f(x_0))}}$ $\Rightarrow$ such $f(x)$ satisfies a condition equivalent to the one we wanted. If we use this expression over all valid p, we get a working solution (m, n) by CRT.

Z K Y

The post below has been deleted. Click to close.

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

de-Kirschbaum

201 posts

de-Kirschbaum

#61 h Aug 18, 2024, 6:19 PM

Y by

If we rephrase the problem in terms of $\nu_p$ we have that for all primes $p$ , $\min(\nu_p(f(x)),\nu_p(f(y))=\min(\nu_p(f(x)), \nu_p(x-y))$ for all integers $x,y$ . Now since the image of $f$ is bounded, we know that there exists some $c$ such that $\nu_p(f(c))=s$ is maximized. Note that if we fix $x=c$ , then that reduces the above condition to $\nu_p(f(y))=\min(s, \nu_p(c-y))$ for every positive integer $y$ , so we are done if we can prove that $\min(s, \nu_p(c-y))=\min(\nu_p(m+y),\nu_p(n))$ for some integer $m,n$ . Suppose the set of primes contained in $\{1, 2, \ldots, 10^{100}\}$ is $P=\{p_1, \ldots, p_k\}$ . Now note that if we take $n=\prod_{p \in P}p_i^{e_{i}}$ where $e_i$ is the maximal power of $p_i$ contained in $\{1, 2, \ldots, 10^{100}\}$ , would have $\nu_p(n)$ be maximized for any prime $p$ , thus $\nu_p(n)=s$ . Now we just need $\nu_p(m+y)=\nu_p(c-y)$ for all $p$ . Note that when $c-y \equiv 0 \mod{p_i^{e_i}}$ , we have $y \equiv c \mod{p_i^{e_i}}$ . That means we just need
$\begin{align*} m &\equiv -c \mod{p_1^{e_1}}\\ m &\equiv -c \mod{p_2^{e_2}} \\ &\vdots \\ m &\equiv -c \mod{p_k^{e_k}} \end{align*}$ By CRT we know such a positive integer $m$ exists. Thus 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.

Mathandski

758 posts

Mathandski

#62 h Aug 19, 2024, 9:48 PM

Y by

Suspiciously simple solution without modular arithmetic

Attachments:

Z K Y

The post below has been deleted. Click to close.

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

numbertheory97

43 posts

numbertheory97

#63 h Sep 17, 2024, 1:18 AM

Y by

Fun problem!

Solution. For each prime $p < 10^{100}$ , let $P_p = p^k$ denote the largest power of $p$ for which $P_p \mid f(x)$ for some $x$ . The main idea is the following:

Claim: Suppose $P \mid P_p$ . All integers $x$ for which $P \mid f(x)$ are congruent mod $P$ .

Proof. Let $x, y$ be integers for which $P \mid f(x), f(y)$ , and suppose to the contrary that $\nu_p(x - y) < \nu_p(P) \leq k$ . Then $\min(\nu_p(f(x)), \nu_p(f(y))) \geq k > \nu_p(x - y) = \min(\nu_p(f(x)), \nu_p(x - y))),$ so our assumption was wrong. $\square$

Thus for each $p$ , there is a unique integer $a_p \in [0, P_p - 1]$ for which all solutions of $f(x) \equiv 0 \pmod{P_p}$ satisfy $x \equiv a_p \pmod{P_p}$ . We now claim that taking $m > 0$ such that $m \equiv -a_p \pmod{P_p}$ for all $p < 10^{100}$ (possible by CRT) and setting $n = \prod_p P_p$ is a valid choice of $(m, n)$ .

Indeed, let $p$ be a prime, and $x$ an integer with $\nu_p(f(x)) = \ell$ . Since $x \equiv a_p \pmod{p^\ell}$ and $x \not\equiv a_p \pmod{p^{\ell + 1}}$ , we have $\nu_p(\gcd(m + x, n)) = \min(\nu_p(m + x), \nu_p(n)) = \min(\nu_p(x - a_p), \nu_p(n)) = \ell = \nu_p(f(x))$ from the fact that $\nu_p(n) = \nu_p(P_p)$ . Combined with the observation that $\nu_p(f(x)) = 0 = \nu_p(n)$ for all primes $p > 10^{100}$ , this completes the proof. $\square$

Remark. I had to edit the above proof a bit, since originally I assumed taking $n = \text{lcm}(1, 2, \dots, 10^{100})$ was fine. But after looking at hints, I realized this raises issues when some prime power dividing $\text{lcm}(1, 2, \dots, 10^{100})$ isn't actually in the range of $f$ .

Z K Y

The post below has been deleted. Click to close.

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

L13832

268 posts

L13832

#65 h Sep 25, 2024, 5:44 PM

Y by

For a prime $p$ we have $\min(\nu_{p}(f(x)), \nu_{p}(f(y))) = \min(\nu_{p}(f(x), \nu_{p}(x - y))$ , let $x$ be the maximal value of $\nu_{p}(f(x))$ , so we have $\nu_{p}(f(k))=\min(\nu_{p}(f(x)),\nu_{p}(k-x))\qquad{(*)}$ We basically want to always have
$\nu_p(f(x)) = \min(\nu_p(m+x), \nu_p(n))$ .
Now choose $m\equiv -x \pmod{p^{\nu_{p}(f(x))}}$ and $n\equiv f(x)\pmod {p^{\nu_{p}(f(x))}}$ by CRT and we are done!

This post has been edited 1 time. Last edited by L13832, Oct 26, 2024, 5:23 AM
Reason: latex typo and solution error

Z K Y

The post below has been deleted. Click to close.

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

pi271828

3371 posts

pi271828

#66 h Oct 16, 2024, 2:33 PM • 1 Y

Y by megarnie

Define $x_p$ to be the maximal value such that $\nu_p(f(x)) = \ell_p$ and $\ell_p$ be the maximum value it attains. We claim that $\begin{align*} n = \prod_{p \le 10^{100}} p^{\ell_p} \\ m \equiv x_p \pmod{p^{\ell_p}} \; \text{for all} \; p \le 10^{100}\end{align*}$
work for $(m, n)$ . We note that there exists an $m$ satisfying that condition by CRT.

Take a value $L$ and note that $\nu_p(f(a))$ can be found by directly using the given equation. Note that $\begin{align*} \operatorname{min}(\nu_p(f(L)), \nu_p(f(x_p))) = \nu_p(f(L)) = \operatorname{min}(\ell_p, \nu_p(L-x_p))\end{align*}$ Now note that with the given values of $m$ and $n$ , we have $\begin{align*} \nu_p(f(L)) = \operatorname{min}(\nu_p(L-\operatorname{lcm} \{x_p\}), \nu_p(n)) \\ = \operatorname{min}(\nu_p(L-x_p), \ell_p) \end{align*}$ 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.

bjump

1028 posts

bjump

#67 h Dec 5, 2024, 6:15 PM

Y by

Call the primes less than $10^{100}$ in increasing order, $p_1$ , $p_2$ , $\dots$ , $p_{n}$ . Where $n$ is the number of primes less than $10^{100}$ . Call the smallest positive $x$ such that $\nu_{p_i} (f(x))$ is maximized $x_{p_i}$ for each prime $p_i$ . We have
$\nu_{p_i}(\gcd(f(x_{p_i}), f(x + k \cdot p^{\nu_{p_i} f(x_{p_i})} )) = \nu_{p_i} ( \gcd(f(x_{p_i}), k \cdot p^{\nu_{p_i} f(x_{p_i})} ) ) = \nu_{p_i} ( f(x_{p_i}))$ $\implies \nu_{p_i} (f(x + k \cdot p^{\nu_{p_i} f(x_{p_i})} )) = \nu_{p_i} (f(x_{p_i}))$ So by CRT there exists a negative value of $x$ call it $x_{\text{ook}}$ such that for each prime $\nu_{p} f(x_{\text{ook}})$ is maximized. Now if $\nu_{p_{i}}(y) = k < \nu_{p_{i}} ( f(x_{\text{ook}}))$ then
$\nu_{p_i} (\gcd(f(x_{\text{ook}}), f(x_{\text{ook}} + y))) = \nu_{p_i}(\gcd(f(x_{\text{ook}}), y)) = \nu_{p_i}(y)$ So $f(x) = \boxed{ \gcd \left( x - x_{\text{ook}}, \prod_{i=1}^n p_i^{\nu_{p_i} ( f(x_{\text{ook}}))} \right)}$

Z K Y

The post below has been deleted. Click to close.

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

D4N13LCarpenter

13 posts

D4N13LCarpenter

#69 h Jan 5, 2025, 6:28 PM • 1 Y

Y by Vahe_Arsenyan

Here's a nice solution which doesn't look at the $\nu_p$ :

Let $x_0$ be such that $f(x_0)$ is the maximum value of $f$ over all possible inputs, which exists as $f$ is upper bounded. We begin by proving the following

Claim 1: $f(x)\mid f(x_0)$ for all $x$
Notice that $f(x)\mid f(x+kf(x))$ $\forall k$ as we have $\gcd(f(x), x-(x+kf(x))=\gcd(f(x), -kf(x))=f(x)$ so $\gcd(f(x),f(x+kf(x))=f(x)$ . The key idea now is to prove that there exist $a, b$ such that $x+af(x)=x_0+bf(x_0)$ . By rearranging the terms, we obtain $af(x)-bf(x_0) = x_0-x$ but we have $\gcd(f(x_0), f(x))\mid x_0-x$ so this is just Bézout's identity.

To finish, note that by the previous observation there exists a $n$ such that $f(x)\mid f(n)$ and $f(x_0)\mid f(n)$ . However, we have $f(n)\leq f(x_0)$ by definition, hence $f(n)=f(x_0)$ , from which the result is immediate.
We know that $\gcd(f(x_0), f(y))=\gcd(f(x_0), x_0-y)$ for all $y$ , but by Claim 1 $\gcd(f(x_0), f(y))=f(y)$ , so this rewrites to $f(y)=\gcd(f(x_0), x_0-y)$ from where the choices $n=f(x_0)$ and $m=-x_0$ finish the problem.

Z K Y

The post below has been deleted. Click to close.

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

mathwiz_1207

100 posts

mathwiz_1207

#70 h Feb 11, 2025, 3:30 AM

Y by

Nice problem! We claim that for any positive integer $m$ , and $n$ such that
$v_p(n) = \text{max}\{v_p(x)\}$ over all integers $x$ and primes $p$ . $n$ is finite because $v_p(n) = 0$ for all $p > 10^{100}$ , and $v_p(n)$ is finite for all $p \leq 10^{100}$ . We prove the following claim:

For integers $a, b$ we have
$\text{min}\{v_p(a-b), v_p(a)\} = \text{min}\{v_p(a), v_p(b)\}$
Proof. If either $a$ or $b$ is $0$ , it is trivial, so assume $a, b$ are nonzero. Then, let $v_p(a) = c$ and $v_p(b) = d$ so $a = a' \cdot p^c$ , and $b = b' \cdot p^d$ . We take cases.

If $c > d$ , the condition is equivalent to
$\text{min}\{v_p(p^d(a' \cdot p^{c -d} - b')), c\} = \text{min}\{c, d\}$ which is equivalent to $d = d$ , true.

If $c = d$ , the condition is equivalent to
$\text{min}\{v_p(p^d(a' - b')), d\} = \text{min}\{d, d\}$ which is equivalent to $d = d$ , true.

If $c < d$ , the condition is equivalent to
$\text{min}\{v_p(p^c(a' - b' \cdot p^{d-c})), c\} = \text{min}\{c, d\}$ which is equivalent to $c = c$ , true.

Now, the given condition in the problem rewrites as
$\text{min}\{v_p(n), v_p(m + x), v_p(n), v_p(m + y)\} = \text{min}\{v_p(n), v_p(m + x), v_p(x - y)\}$ for all primes $p$ . Furthermore since $v_p(n)$ is maximized, the above is equivalent to
$\text{min}\{v_p(m + x), v_p(m + y)\} = \text{min}\{v_p(m + x), v_p(x - y)\}$ Setting $a = m + x, b = m + y$ , this is true by the claim we proved above, 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.

lelouchvigeo

183 posts

lelouchvigeo

#71 h Apr 12, 2025, 1:59 PM • 1 Y

Y by alexanderhamilton124

Solution

Z K Y

The post below has been deleted. Click to close.

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

cursed_tangent1434

634 posts

cursed_tangent1434

#72 h Apr 21, 2025, 3:51 PM

Y by

Let $\ell = \text{lcm} (1,2,\dots,10^{100})$ . We start off with the following simple observation which allows us to work on $f$ with a finite domain.

Claim : For all integers $n$ , $f(n)=f(n+\ell)$ .

Proof : Simply note that,
$\gcd(f(\ell+n),f(n))=\gcd(f(\ell+n),\ell) = f(\ell+n)$ which implies that $f(\ell+n) \mid f(n)$ . Similarly,
$\gcd(f(n),f(\ell+n))=\gcd(f(n),-\ell)=f(n)$ which implies that $f(n) \mid f(\ell+n)$ which in conjunction with the prior result implies that $f(n)=f(n+\ell)$ as claimed.

Now we work with the restricted function $f:\{1,2,\dots,\ell\} \to \{1,2,\dots , 10^{100}\}$ and extend the function to all of $\mathbb{Z}$ using the above claim. Now comes the most important result.

Let $p_1<p_2<\dots < p_a$ be the set of all primes dividing $\ell$ . Let $M_i$ be the positive integer such that $\nu_{p_i}(f(M_i))$ is maximal under the restricted domain.

Claim : For all positive integers $x$ , and primes $p_i\mid \ell$ ,
$\nu_{p_i}(f(x))=\min\{\nu_{p_i}(x-M_{_i}),\nu_{p_i}(f(M_{p_i}))\}$
Proof : If $\nu_p(f(x))=\nu_p(f(M_i))$ by the given condition,
$\nu_p(f(x))=\min\{\nu_p(f(x)),\nu_p(f(M_i))\} = \min\{\nu_p(f(x),\nu_p{(x-M_i)})\}$ which implies that $\nu_p((x-M_i)) \ge \nu_p(f(x))$ so the claim holds. Else, $\nu_p(f(x))<\nu_p(f(M_i))$ and in this case the given condition implies,
$\nu_p(f(x)) = \min\{\nu_p(f(M_i)),\nu_p(f(x))\}= \min\{\nu_p(f(M_i)),\nu_p(M_i-x)\}$ clearly $\nu_p(f(M_i))=\nu_p(f(x))$ is impossible so it follows that $\nu_p(f(M_i)) > \nu_p(M_i-x)$ and hence $\nu_p(f(x))= \nu_p(M_i-x)$ which finishes the proof of the claim.

We now make the above expression symmetric in $M_i$ . To do this, first note that,
$\nu_{p_i}(M_i) = \max\{\nu_{p_i}(M_1),\nu_{p_i}(M_2), \dots , \nu_{p_i}(M_a)\} = \nu_{p_i}(\text{lcm}(M_1,M_2,\dots , M_a))$ Now, let $r_i = \max\{\nu_{p_i}(M_{p_i}-x),\nu_{p_i}(M_{p_i})\}$ across all $1 \le x \le \ell$ and $x \ne M_{p_i}$ . Then, consider $T \equiv -M_{p_i} \pmod{p^{r_i+1}}$ . So, for $x \ne M_{p_i}$ we have,
$\nu_{p_i}(M_{p_i}-x) = \nu_{p_i}(x-M_{p_i}+(M_{p_i}+T)) = \nu_{p_i}(x+T)$ as $\nu_{p_i}(M_i+T) > \nu_{p_i}(x-M_{p_i})$ by nature of construction. And when $x=M_{p_i}$ we similarly have,
$\nu_{p_i}(x-M_i+M_{p_i}+T) = \nu_{p_i}(M_i+T) > \nu_{p_i}(M_i)$ as $\nu_p(x-M_i)= \infty$ . Thus, for all $1\le x \le \ell$ we have,
$\min\{\nu_{p_i}(M_{p_i}-x),\nu_{p_i}(f(M_{p_i}) = \min\{\nu_{p_i}(x+T),\nu_{p_i}(f(M_{p_i}))\}\}$ Now, by the Chinese Remainder Theorem we can pick $T$ which satisfies the prescribed congruence for each prime $p_1,p_2,\dots , p_a$ we provides us with a positive integer $T$ for which the above relation holds for all primes $p_i$ for a fixed constant $T$ . Combining our two conclusions we have,
$\nu_{p_i}(f(x))= \min\{\nu_{p_i}(x+T),\nu_{p_i}(\text{lcm}(f(M_1),f(M_2),\dots , f(M_a)))\}$ which summing across all primes $p_1,p_2,\dots , p_a$ implies
$f(x) = \gcd(x+T,L)$ where $T$ and $L=\text{lcm}(f(M_1),f(M_2),\dots , f(M_a))$ are fixed positive constants as desired.

Z K Y

The post below has been deleted. Click to close.

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

ihategeo_1969

235 posts

ihategeo_1969

#73 h Apr 21, 2025, 11:02 PM

Y by

I am so trash at maths genuinely.

Let $p_1 < \dots < p_t$ be all primes $\le 10^{100}$ . Let $e_i$ , $a_i$ be $\max(\nu_{p_i}(x))$ and such a $x$ respectively.

Now by $Q(a_i,x)$ (where $Q(x,y)$ is the assertion) we get $\nu_{p_i}(f(x))=\min(e_i,\nu_{p_i}(f(x))=\min(e_i,\nu_{p_i} (x-a_i))$ Now by CRT choose $m$ such that $-m \equiv a_i+p_i^{e_i} \pmod {p_i^{e_i+1}} \iff \nu_{p_i}(m+a_i)=e_i$ Claim: $\min(e_i,\nu_{p_i}(x-a_i))=\min(e_i,\nu_{p_i}(x+m))$ .
Proof: See that $\nu_{p_i}(x-a_i)=\min(e_i,\nu_{p_i}(x+m))$ unless $e_i=\nu_{p_i}(x+m)$ . In each of these cases, we will analyse what can go ``wrong" and prove it cannot happen.

$\bullet$ Let $e_i<\nu_{p_i}(x-a_i)$ . If $e_i>\nu_{p_i}(x+m)$ then $e_i<\nu_{p_i}(x-a_i)=\nu_{p_i}(x+m)<e_i$ , contradiction.
$\bullet$ Let $e_i>\nu_{p_i}(x-a_i)$ . If $e_i<\nu_{p_i}(x+m)$ then $e_i>\nu_{p_i}(x-a_i)=e_i$ , contradiction.
$\bullet$ Let $e_i=\nu_{p_i}(x-a_i)$ . If $\nu_{p_i}(x+m)<e_i$ then $e_i=\nu_{p_i}(x-a_i)=\nu_{p_i}(x+m)$ , contradiction.

Done. $\square$

Now just choose $n=\prod_{i=1}^t p_i^{e_i}$ And hence $\nu_{p_i}(f(x))=\min(\nu_{p_i}(x+m),\nu_{p_i}(n)) \iff f(x)=\gcd(x+m,n)$ As required.

Z K Y