Given an even positive integer $m$, find all positive integers $n$ for which there exists a bijection $f:[n]\to [n]$ so that, for all $x,y\in [n]$ for which $n\mid mx-y$, $$(n+1)\mid f(x)^m-f(y).$$ Note: For a positive integer $n$, we let $[n] = \{1,2,\dots, n\}$. Proposed by Milan Haiman and Carl Schildkraut
Problem
Source: 2019 ELMO Shortlist N5
Tags: number theory, Elmo
BlazingMuddy
28.06.2019 16:44
Can I get a bit of clarifications for this? The header says FE from $\mathbb{Z}_n$ to $\mathbb{Z}_{n+1}$ but the function here is of type $[n] \rightarrow [n]$. Is it actually $[n] \rightarrow [n+1]$? Thank you. Edit: Nvm kinda feel stupid now; obviously it can't be $[n] \rightarrow [n+1]$ ($f$ is said to be bijective).
pieater314159
28.06.2019 22:57
BlazingMuddy wrote: Can I get a bit of clarifications for this? The header says FE from $\mathbb{Z}_n$ to $\mathbb{Z}_{n+1}$ but the function here is of type $[n] \rightarrow [n]$. Is it actually $[n] \rightarrow [n+1]$? Thank you. Edit: Nvm kinda feel stupid now; obviously it can't be $[n] \rightarrow [n+1]$ ($f$ is said to be bijective). What's basically going on here is a bijection from $\mathbb{Z}_n$ to the nonzero elements of $\mathbb{Z}_{n+1}$, as the predicate on $(x,y)$ is a condition $\bmod n$ while the requirement on $(f(x),f(y))$ is a condition $\bmod (n+1)$.
BlazingMuddy
17.07.2019 11:28
$n = p - 1$ where $p$ is an arbitrary prime number.
Construction for $n + 1$ being prime:
Simply let $t$ be a primitive root modulo $n + 1$ and let $f(x) = t^x \pmod{n+1}$ for all $x\in [n]$. Quite easy to check by help of Fermat's Little Theorem.
Now, to prove the other way, first see that $n + 1$ must be square free; otherwise there exists a positive integer $a < n + 1$ with $n + 1 | a^2$ (and hence $n + 1 | a^m$); then taking $x$ such that $f(x) = a$, we have $f(y) = 0$ which is a contradiction. Now, assume for the sake of contradiction that $n + 1$ is not prime.
Then, there exists a positive integer $k$ and different prime numbers $p_1, p_2, \ldots, p_k$ such that $n + 1 = p_1 p_2 \ldots p_k$. We will now prove a crucial lemma.
LemmaLet $b$ be an arbitrary element of $[n]$. If there exists $a\in [n]$ such that $a^m \equiv b \pmod{n + 1}$, then there exists $\gcd(m, n)$ such $a$.
ProofLet $y$ be an element of $[n]$ such that $f(y) = b$. Since $f$ is bijective, the lemma condition says that there exists an $x\in [n]$ such that $n + 1 | f(x)^m - f(y)$ (note that it becomes an if and only if condition because of bijectivity; $n | mx - y$ if and only if $n + 1 | f(x)^m - f(y)$). But if so, then that simply means $\gcd(m, n)$ divides $y$, and then there are $\gcd(m, n)$ possible picks for $x$ to satisfy $n | mx - y$, which translates to $\gcd(m, n)$ possible picks for $x$ to satisfy $n + 1 | f(x)^m - f(y)$.
Now, consider an element $q\in [n]$ such that $p_1 p_2 \ldots p_{k-1} | q$ but $q \equiv 1\pmod{p_k}$. Obviously, there exists $a\in [n]$ such that $a^m \equiv q\pmod{n+1}$ as in fact $q^m \equiv q\pmod{n+1}$. So, by the lemma, there exists $\gcd(m, n)$ elements $x\in [n]$ such that $x^m \equiv q\pmod{n+1}$; i.e. $p_i | x$ for $i \leq k - 1$, but $x^m \equiv 1\pmod{p_k}$. Similarly, there exists $\gcd(m, n)$ elements $y\in [n]$ such that $y^m \equiv 1\pmod{n+1}$ i.e. $x^m \equiv 1\pmod{p_i}$ for all $i \leq k$. But since $m$ is even, there must then be more such $y$ than such $x$; a contradiction.
Hence, $n + 1$ is prime.
analysis90
31.12.2019 10:03
BlazingMuddy wrote:
$n = p - 1$ where $p$ is an arbitrary prime number.
Construction for $n + 1$ being prime:
Simply let $t$ be a primitive root modulo $n + 1$ and let $f(x) = t^x \pmod{n+1}$ for all $x\in [n]$. Quite easy to check by help of Fermat's Little Theorem.
Now, to prove the other way, first see that $n + 1$ must be square free; otherwise there exists a positive integer $a < n + 1$ with $n + 1 | a^2$ (and hence $n + 1 | a^m$); then taking $x$ such that $f(x) = a$, we have $f(y) = 0$ which is a contradiction. Now, assume for the sake of contradiction that $n + 1$ is not prime.
Then, there exists a positive integer $k$ and different prime numbers $p_1, p_2, \ldots, p_k$ such that $n + 1 = p_1 p_2 \ldots p_k$. We will now prove a crucial lemma.
LemmaLet $b$ be an arbitrary element of $[n]$. If there exists $a\in [n]$ such that $a^m \equiv b \pmod{n + 1}$, then there exists $\gcd(m, n)$ such $a$.
ProofLet $y$ be an element of $[n]$ such that $f(y) = b$. Since $f$ is bijective, the lemma condition says that there exists an $x\in [n]$ such that $n + 1 | f(x)^m - f(y)$ (note that it becomes an if and only if condition because of bijectivity; $n | mx - y$ if and only if $n + 1 | f(x)^m - f(y)$). But if so, then that simply means $\gcd(m, n)$ divides $y$, and then there are $\gcd(m, n)$ possible picks for $x$ to satisfy $n | mx - y$, which translates to $\gcd(m, n)$ possible picks for $x$ to satisfy $n + 1 | f(x)^m - f(y)$.
Now, consider an element $q\in [n]$ such that $p_1 p_2 \ldots p_{k-1} | q$ but $q \equiv 1\pmod{p_k}$. Obviously, there exists $a\in [n]$ such that $a^m \equiv q\pmod{n+1}$ as in fact $q^m \equiv q\pmod{n+1}$. So, by the lemma, there exists $\gcd(m, n)$ elements $x\in [n]$ such that $x^m \equiv q\pmod{n+1}$; i.e. $p_i | x$ for $i \leq k - 1$, but $x^m \equiv 1\pmod{p_k}$. Similarly, there exists $\gcd(m, n)$ elements $y\in [n]$ such that $y^m \equiv 1\pmod{n+1}$ i.e. $x^m \equiv 1\pmod{p_i}$ for all $i \leq k$. But since $m$ is even, there must then be more such $y$ than such $x$; a contradiction.
Hence, $n + 1$ is prime.
Why “ But since $m$ is even, there must then be more such $y$ than such $x$”?
Aryan-23
06.11.2020 11:15
Nice problem !
We claim that $n$ works iff $n+1$ is a prime.
To note that $n=p-1$ works, just take $f(x)=g^x$, which works.
The basic motivation for the solution is that the problem asks to find such $n$ such that the maps $x \mapsto mx$ in $\mathbb Z/n\mathbb Z$ and the map $x\mapsto x^m$ in $\mathbb Z/(n+1)\mathbb Z \setminus \{0\}$ behave in the same way.
First we note that if $n+1$ is not squarefree, then there exists $z<n+1$ such that $n+1\mid z^2\mid z^m$. Choose $x$ such that $f(x)=z$, and then we'd get :
$$ n+1 \mid f(x)^m - f(mx \pmod p) \implies n+1 \mid f(mx \pmod p) $$
Which is a obvious contradiction. Hence $n+1= \prod_{i=1}^{k}p_i$, for distinct primes $p_i$ and $k\geq1$.
Next look at the mapping $x\mapsto mx$ in $\mathbb Z/ n\mathbb Z$, note that :
$$ mx_1 \equiv mx_2 \pmod n \iff x_1\equiv x_2 \pmod { \tfrac {n}{\gcd (m,n)} }$$
So for all $y\in \mathbb Z/ n\mathbb Z$, there are exactly $\gcd (m,n)$ values of $x$ such that $n \mid mx-y$. So we must have that for all $y \in \mathbb Z/ (n+1)\mathbb Z\setminus \{0\}$, there are exactly $\gcd(m,n)$ choices of $x$ such that $x^m \equiv y \pmod {n+1}$. We claim that this can't happen if there exists atleast $2$ distinct odd primes that divide $n+1$.
Indeed suppose $y_1$ be a non zero residue $\pmod {n+1}$ such that $y_1 \equiv 1 \pmod{p_i}$ for $i=1,2$ and $p_i \mid y$ for $i>2$. Its easy to see that there are $\gcd (p_1-1)\times \gcd (p_2-1)$ choices for $x$ such that $x^m \equiv y_1$.
Similarly pick $y_2$ to be divisible by all $p_i$ for $i>1$ and $1\pmod {p_1}$. We have $\gcd (p_1-1)$ solutions in this case. Note that $\gcd (p_2-1,m) \geq 2)$ (as $m$ is even), so we have a contradiction.
We now show that $n+1=2p$ doesnt work. Note that $p$ is a $m$-th power of only itself in this case, whereas $p+1$ has $2$ $m$-th roots, namely $(p+1)$ and $(p-1)$. This gives the desired contradiction. We are done. $\square$
alexiaslexia
16.11.2020 18:58
After long hours of grinding (m,n) such as (6,14) and (6,16) ... Also, this problem is not combi (for those who think otherwise). $\textcolor{green}{\textbf{\text{Notational convenience.}}}$ Since this is longer than necessary, I'm going to reference a number $x$ in the domain by $x_{(l)}$, but $x$ in the codomain will be referred as $x_{(r)}$ ($r$ is for "right" and "range"). For example, when $(m,n) = (6,14)$, I will say that \[ 14 \mid 6 \cdot 3_{(l)} - 4_{(l)},\ \text{and} \ 15 \mid 3_{(r)}^6-9_{(r)} \]Here we go a little bit beyond and create auxiliary graphs $G_d$ and $G_c$ (a.k.a. "fake" graphs that will, I hope, make the problem statement easier to comprehend.) In this case, I will say that $3_{(l)} \rightarrow 4_{(l)}$ forms an edge in $G_l$ and $3_{(r)} \rightarrow 9_{(r)}$ in $G_r$. To go full circle, we will say that $x_{(l)} \Rightarrow f(x)_{(r)}$ to represent the connection between a vertex $x_{(l)}$ in $G_l$ and $x_{(r)}$ in $G_r$. (If you don't get this $-$ it's totally fine, basically this is just saying to put $(l)$ under a number when we look at the left $[n]$ and $(r)$ under it when we look at the right $[n]$.) ${\color{green} \rule{25cm}{0.5pt}}$ $\textcolor{cyan}{\textbf{\text{Isomorphisms, Bijectives and elimination of cases.}}}$ First we will establish by the bijection in the problem statement that the two graphs $G_l$ and $G_r$ are isomorphic; and we first eliminate the easy cases $n+1 = p$ and $n+1$ not squarefree, using said isomorphism. Chunk 1: The problem statement goes both ways. Let it doesn't, for the sake of contradiction. Then, there exists $x_{(l)},y_{(l)}$ so that \[n+1 \mid f(x)^m - f(y), n \nmid mx - y \]However, letting $y'_{(l)} \equiv x_{(l)}$ mod $n$ yields \[n+1 \mid f(x)^m - f(y') \]so that $n+1 \mid f(y)-f(y')$, a contradiction. Chunk 2: Isomorphism. Match the vertices $x_{(l)}$ and $f(x)_{(r)}$. Note that since there exists an edge between vertices $u_{(l)}$ and $v_{(l)}$ in $G_l$ iff there exists a similar edge in $G_r$ by Chunk 1. Statement proven. Chunk 3: Easy cases. For $n+1 = p$, set $f(x) = g^x$ with $g$ primitive root of $p$, as in post $\#4$. For $n+1$ not squarefree, letting $p^2 \mid n+1$ yields a contradiction by noting that $n+1 \mid \left(\dfrac{n+1}{p}\right)_{(r)}^m - q_{(r)}$, but this is impossible since $q_{(r)} \equiv 0 \ \text{mod} \ n+1$ is not in the vertices of $G_r$. ${\color{green} \rule{25cm}{3pt}}$ So, now we can let $n+1 = \prod_{i \ne j} p_i.$ Here we proceed with a simple but central Lemma. $\textcolor{blue}{\textbf{\text{Lemma: Regularity of both graphs.}}}$ Each vertex in $G_l$ (in $G_r$, too, due to isomorphism) has outdegree $1$, and indegree either $0$ or $\text{gcd}(m,n)$. $\textbf{Proof.}$ Any $a_{(l)}$ has only one out-edge, that is with $ma_{(l)} \ (\text{mod} \ n)$. Moreover, it is easily seen that the equation \[ n \mid mx - a \]has no solutions if $(m,n) \nmid a$, implying $a_{(l)}$ has no indegree, or has $(m,n)$ solutions when $(m,n) \mid a$, implying $a_{(l)}$ has $(m,n)$ indegree. ${\color{blue} \rule{25cm}{1pt}}$ $\textcolor{red}{\textbf{\text{Finishing.}}}$ We now divide into two cases, first case being ($n$ odd, $n+1$ even) and ($n$ even, $n+1$ odd). Case 1. Note that $(m,n)$ odd. Because $n+1$ even, $n+1 = 2p_2 \ldots p_k$. Focusing on $\dfrac{n+1}{2}$, we let $(p_2 \ldots p_k)_{(r)} \rightarrow I_{(r)}$ ($I$ stands for identity and also indegree). Observe that all other $I'_{(r)} \ne I_{(r)}$ with positive indegree must have even indegree, because $x_{(r)} \rightarrow I'_{(r)}$ iff $(-x)_{(r)} \rightarrow I'_{(r)}$. Therefore, $f(x)_{(r)}^m = {(\text{any number})}_{(r)}^{m} \equiv I_{(r)} \ \text{mod} \ n+1$, so by setting $any \ number$ equal to $1$ and $2$, we get $1 \equiv 2 \ \text{mod} \ n+1$. Case 2. The idea here is to apply subtle CRT to "make" two vertices in $G_r$ have different indegrees. Noting that the equation \[ x^m \equiv 1 \ \text{mod} \ p_i \]have at least two solutions mod $p_i$, and the equation \[x^m \equiv 0\ \text{mod} \ p_i \]has only one solution ($0$) mod $p_i$, we use this idea to construct two numbers $u = 1$ and $a$ (unit, almost unit) so that \begin{align*} u &\equiv 1 \ \text{mod} \ p_1, \ldots, u \equiv 1 \ \text{mod} \ p_{k-1}, u \equiv 1 \ \text{mod} \ p_k \\ a &\equiv 1 \ \text{mod} \ p_1, \ldots, a \equiv 1 \ \text{mod} \ p_{k-1}, a \equiv 0 \ \text{mod} \ p_k \end{align*}Observe that if $x^m \equiv 1 \ \text{mod} \ p_i$ has $s_i$ solutions mod $p_i$, $u_{(r)}$ has $s_1\ldots s_{k-1} s_k$ indegree, but $a_{(r)}$ has only $s_1 \ldots s_{k-1}$ indegree. This is due to setting $f(y) = u,a$ in the original equation to get solutions in $f(x)$. We are done.
One beautiful lesson to learn from this problem is that "it's easy to lose track of what you're doing, if you haven't set your objective yet." I think I probably spent well over 4 hours trying to find a counterexample to $n+1$ prime, desperately trying to find an abnormal condition of $(m,n)$ which changes the conjecture, or just trying to find the "pattern blueprint" of the proof for $n+1 = p$.
After I was sure of the answer, the fatal mistake I made was trying to consider things in perspective of $m$ in relation to $n$ too long, or using the condition $mx \equiv y$ mod $n$ to find absurd stuff (such as cycles in $G_l$) which implies more uglier things such as finding $m^d \equiv 1$. What I should've noticed earlier is that if a pattern only depends on $n+1$, $\textbf{it only depends on}$ $n+1$. The secondary stuff $(m,n)$, $\phi(n+1)$, $\phi(n)$, or the prime factorization of $n$ (very likely) has nothing to do with the central idea of the problem.
Okay, if those stuff has nothing to do with the solution, then what about the $\textbf{isomorphicity}$ which naturally $\textbf{MUST}$ occur as a consequence of the problem statement? Turns out, only a small portion of it is absolutely necessary, which is the degree of each vertex staying "almost constant". I also spent a lot of time stuck here, because I did not realize the fact that $\textbf{directly proving two graphs not isomorphic is hard.}$ (See USA TST 2020-4 for an excellent illustration of this $-$ to finish that problem the only way out is to consider one particularly specific structure. All else fails.)
However, I cannot choose to avoid this "proving not isomorphic thing" because it's what I had to literally do to provide a contradiction for $n+1 \ne p$. Seeing that cycles fail, and components are also ugly (see attachment for details on some examples of $G_l$ and $G_r$), the only (desperate) structure is the basic structure itself, the degree of every vertex.
To overcomplicate things here a bit, my (still) dummy self decided that the next best thing is to decide on the parity of $n$, because up to this point I had been confused over the purpose of $m$ being even (therefore by matching that condition with $n$ brought some hope.) My initial suspicion on "counting degrees must work" brought some results, as by considering $x = \dfrac{n+1}{2}$ a contradiction can be extracted as in Case 1.
At that point I finally realized that $m$ even can be used to ensure that (obviously) $1_{(r)}$ being "in range" of $G_r$ (i.e. having positive indegree) implies at least it has $2$ indegree; $1_{(r)}$ and also $(-1)_{(r)}$, from above. However, when there was no $"2"$ in the prime factorization of $n+1$, I knew I had to pull something cleverer. Realizing further that $"2"$ is probably just an excuse to make computation more obvious (by considering the parity of $(m,n)$), I tried to mimic the proof for the second case, which succeeded because of the ingenuity in creating multiple "classes" modulo $p_i$, instead of just considering $p_i = 2$.
$\textcolor{green}{\textbf{\text{Final comments.}}}$ I was initially scared that such a naive construction works, but I realized that there's no other way of doing it, due to the nature of the equation $x^m \equiv a \ \text{mod} \ p_i$. If $a$ is not in the form of $g^{km}$, then it has $0$ solutions, if $a \equiv 0$ then it has exactly one solution, and if $a \equiv g^{km}$ for some $k$ then it has $\text{gcd}(m,n)$ solutions. Even by considering other congruences $a \ne 1$, I would suspect that the only way to proceed is by using $CRT$ like all the above solutions.
analysis90 wrote: BlazingMuddy wrote:
$n = p - 1$ where $p$ is an arbitrary prime number.
Construction for $n + 1$ being prime:
Simply let $t$ be a primitive root modulo $n + 1$ and let $f(x) = t^x \pmod{n+1}$ for all $x\in [n]$. Quite easy to check by help of Fermat's Little Theorem.
Now, to prove the other way, first see that $n + 1$ must be square free; otherwise there exists a positive integer $a < n + 1$ with $n + 1 | a^2$ (and hence $n + 1 | a^m$); then taking $x$ such that $f(x) = a$, we have $f(y) = 0$ which is a contradiction. Now, assume for the sake of contradiction that $n + 1$ is not prime.
Then, there exists a positive integer $k$ and different prime numbers $p_1, p_2, \ldots, p_k$ such that $n + 1 = p_1 p_2 \ldots p_k$. We will now prove a crucial lemma.
LemmaLet $b$ be an arbitrary element of $[n]$. If there exists $a\in [n]$ such that $a^m \equiv b \pmod{n + 1}$, then there exists $\gcd(m, n)$ such $a$.
ProofLet $y$ be an element of $[n]$ such that $f(y) = b$. Since $f$ is bijective, the lemma condition says that there exists an $x\in [n]$ such that $n + 1 | f(x)^m - f(y)$ (note that it becomes an if and only if condition because of bijectivity; $n | mx - y$ if and only if $n + 1 | f(x)^m - f(y)$). But if so, then that simply means $\gcd(m, n)$ divides $y$, and then there are $\gcd(m, n)$ possible picks for $x$ to satisfy $n | mx - y$, which translates to $\gcd(m, n)$ possible picks for $x$ to satisfy $n + 1 | f(x)^m - f(y)$.
Now, consider an element $q\in [n]$ such that $p_1 p_2 \ldots p_{k-1} | q$ but $q \equiv 1\pmod{p_k}$. Obviously, there exists $a\in [n]$ such that $a^m \equiv q\pmod{n+1}$ as in fact $q^m \equiv q\pmod{n+1}$. So, by the lemma, there exists $\gcd(m, n)$ elements $x\in [n]$ such that $x^m \equiv q\pmod{n+1}$; i.e. $p_i | x$ for $i \leq k - 1$, but $x^m \equiv 1\pmod{p_k}$. Similarly, there exists $\gcd(m, n)$ elements $y\in [n]$ such that $y^m \equiv 1\pmod{n+1}$ i.e. $x^m \equiv 1\pmod{p_i}$ for all $i \leq k$. But since $m$ is even, there must then be more such $y$ than such $x$; a contradiction.
Hence, $n + 1$ is prime.
Why “ But since $m$ is even, there must then be more such $y$ than such $x$”? This uses a similar idea in my proof for Case 2. , as when $m$ is even, $y^m \equiv 1\pmod{p_i}, 1 \leq i \leq k-1$ has more than $1$ solution, and couple that with $y^m \equiv 1 \pmod{p_k}$ yields so many solutions in $y$ compared to the highly specific condition $p_i \mid x$ for $i \leq k-1$ which yields only $1$ solution $\pmod{p_1\ldots p_{k-1}}$.
Attachments:
ELMO 2019 N5.pdf (414kb)