Let $k \in \mathbb{Z}^+$ and set $n=2^k+1.$ Prove that $n$ is a prime number if and only if the following holds: there is a permutation $a_{1},\ldots,a_{n-1}$ of the numbers $1,2, \ldots, n-1$ and a sequence of integers $g_{1},\ldots,g_{n-1},$ such that $n$ divides $g^{a_i}_i - a_{i+1}$ for every $i \in \{1,2,\ldots,n-1\},$ where we set $a_n = a_1.$ Proposed by Vasily Astakhov, Russia
Problem
Source: IMO Shortlist 2011, Number Theory 8
Tags: function, number theory, IMO Shortlist
18.07.2012 17:22
Point "only if". Let $n = 2^{k}+1$ be a prime number. Then $k = 2^{t}$ for $t \in \mathbb{Z}_{+}$ (otherwise $n$ would be divisible by $2^{q}+1$, where $q$ is an odd prime divisor of $k$), so $n = 2^{2^{t}}+1$. Cases $t = 0, 1$ are trivial so we'll assume $t \geqslant 2$. For $m \in \mathbb{Z}$ we shall denote the remainder of $m$ $(\mathrm{mod}\ n)$ as $r(m)$. Let $g$ be an arbitrary primitive root $(\mathrm{mod}\ n)$. For $0 \leqslant m \leqslant 2^{t}$ we shall denote $A_{m} = \{2^{2^{t} - m}q, 0 < q \leqslant 2^{m}, q$ is odd $\}$ and $B_{m} = \{r(x) \mid \mathrm{ord}(x) = 2^{m}\} = \{r(g^{u}), u \in A_{m}\}$. Lemma 1. If $m \geqslant 2$ then in the set $B_{m}$ there are exactly $2^{m-2}$ even numbers and $2^{m-2}$ odd numbers. Proof. For every positive odd $q < 2^{m-1}$ we have $r(g^{2^{2^{t} - m}(q + 2^{m-1}) }) = r(g^{2^{2^{t} - m}q}g^{2^{2^{t} - 1}}) = r( - g^{2^{2^{t} - m}q}) = n - r(g^{2^{2^{t} - m}q})$ so in the pair $\{r(g^{2^{2^{t} - m}q}), r(g^{2^{2^{t} - m}(q + 2^{m-1}) })\}$ there is one even number and one odd number. But $B_{m}$ consists of $2^{m-2}$ such pairs.$\Box$ Lemma 2. There exists a function $f: \{2,4,6,...,2^{2^{t}}\}\rightarrow \{1,2,3,...,2^{2^{t}}\}$ with the following properties: 1) $f$ is injective; 2) $\forall m$ $f(A_{m}) = B_{m}$; 3) If we construct the oriented graph $G$ with vertices $\{1,2,3,..., n-1\}$ and oriented edges $\{(m, f(m)) \mid m$ is even $\}$ then there would be no oriented cycles. Proof. We shall construct that function consequently on the sets $A_{m}$ using induction by $m$. Since $\{2,4,6,...,2^{2^{t}}\}$ is the union of sets $A_{m}$, it's all right. At first, $A_{0} = \{2^{2^{t}}\}$, $B_{0} = \{1\}$, $A_{1} = \{2^{2^{t - 1}}\}$ and $B_{1} = \{2^{2^{t}}\}$ so we assume $f(2^{2^{t}}) = 1$ and $f(2^{2^{t - 1}}) = 2^{2^{t}}$, three conditions are satisfied and this is the base of induction. Further, if we constructed our function on the sets $A_{0}, A_{1},..., A_{m-1}$, we shall now construct it on the set $A_{m}$. At first we define function $f$ on $A_{m}$ as an arbitrary bijection to $B_{m}$. First and second conditions are satisfied (sets $B_{m}$ disjoint), but there can be some problems with the third condition. We call the oriented edge $(s, f(s))$ (where $s \in A_{m}$) bad if there exists an oriented cycle consisting this edge. Now we define $f$ on $A_{m}$ as the bijection to $B_{m}$ with the minimal number of bad edges. Now we shall prove that there are no bad edges at all (that completes the proof of lemma 2). Let's denote $C = \{s \in A_{m}\mid f(s)$is odd $\}$ and $D = \{s \in A_{m}\mid f(s)$is even $\}$. By lemma 1, $|C| = |D| = 2^{m - 2}$. Edges from $C$ to $B_{m}$ can't be bad (because there are no edges from odd vertices to anywhere so there can be no oriented cycles with the vertices from $C$), so the bad edges could only begin in vertices in the set $D$. Let $(s, v)$ be the one of the bad vertices, $s \in D$. We have $v \notin C$ (otherwise this edge can't be bad), then let's take an arbitrary vertex $x \in C$ with $f(x) = w$ and redefine our function as $f(x) = v$ and $f(s) = w$ (we don't change function on other vertices). Now edge $(x,v)$ is not bad (because after following the oriented edges we have this situation: $x \rightarrow v \rightarrow ... \rightarrow s \rightarrow w$ ($w$ is odd) so there are no oriented cycles with this edge), so the number of bad edges has decreased by 1 - a contradiction. $\Box$ Let's consider our function $f$ from lemma 2. By lemma 2, the corresponding graph is a union of disjoint oriented paths. Then it is obvious that function $f$ can be continued to the bijection $\{1,2,3,..., n-1\} \rightarrow \{1,2,3,..., n-1\}$ such that the corresponding graph would be a simple cycle consisting all vertices. Now we shall define our permutation with $a_{1} = 1$ and $a_{m+1} = f(a_{m})$. We're gonna prove that this permutation is satisfying the condition of the problem. We must prove that for every $m$ the congruence $x^{a_{m}} \equiv a_{m+1}(\mathrm{mod}\ n)$ is solvable. If $a_{m}$ is odd this congruence has a solution for any $a_{m+1}$ (because $x \mapsto x^{2m+1}$ is an automorphism of the group $\mathbb{Z}^{*}_{n}$). If $a_{m}$ is even then we have the congruence $x^{2^{2^{t} - s}q} \equiv g^{2^{2^{t} - s}p} (\mathrm{mod}\ n)$ for some odd $p$ and $q$, which is solvable because the congruence $x^{q} \equiv g^{p}$ is solvable. Our point is done. Point "if". Now let $n$ be a composite odd number and let's assume that such permutation exists. If $n$ is divisible by $p^{2}$ for some prime $p$ then we denote $a_{i} = p$ and $a_{j} = 2p$. Then obviously $a_{i-1} = a_{j - 1} = 1$ (because if $a_{i-1} > 1$ then $a_{i} = g_{i-1}^{a_{i-1}}$ must be divisible by $p^{2}$, in the same way $a_{j-1} = 1$) - a contradiction. So $n$ is free from squares and $n = p_{1}p_{2}...p_{m}$, $p_{i}$ are different prime numbers. If $a_{j}$ is even then $a_{j+1}$ must be a quadratic residue $(\mathrm{mod}\ p_{i})$ (or zero) for all $i$ so $a_{j + 1}$ has only $\frac{p_{1}+1}{2}\frac{p_{2}+1}{2}...\frac{p_{m}+1}{2} < \frac{2p_{1}}{3}\frac{2p_{2}}{3}...\frac{2p_{m}}{3} \leqslant \frac{4}{9}p_{1}...p_{m} = \frac{4}{9}n < \frac{n - 1}{2}$, but there are exactly $\frac{n-1}{2}$ even numbers among $a_{j}$ - a contradiction. We are done.
18.07.2012 18:57
On the if part is easy to show that if any odd $n$ is not prime there are less than $\frac{n-1}{2}$ cuadratic residues mod $n$. Suppose that is possible, as there are $\frac{n-1}{2}$ even $a_i$ by Pigeonhole principle there must be two $a_{i+1}$ which are the same, contradiction. Only if
29.09.2016 20:25
Proof: <= First we need to show that $n$ is square free. Let $p^2|n$, then consider $i$, such that $a_{i+1} = p$, so we have that $n|g_i^{a_i} - p$ and that $p|g_i$, so if $a_i>1$ we will get contradiction to $p^2|n, p^2|g_i^{a_i}, p^2\not= 0 mod p$. So $a_i = 1$. Note that $n=2^k+1\not= p^t$, so we can take $q\not=p|n$. Consider $j: a_{j+1} = pq$, so $j\not= i$. From same arguments we get that $a_j = 1$, but then we get contradiction to $i\not=j$. So $n = p_1\ldots p_l$ for different primes $p_i$. There are only $\frac{n-1}{2}$ even numbers from $1$ to $n$, so if we chose $a_{i+1}$ to be even number then we get corresponding numbers $a_i$ which are quadratic residues mod $n$. So we get $|\{\text{non zero quadratic res mod n}\}|\geq\frac{n-1}{2}$. But on the other hand we can consider injective morphism $\phi : \mathbb{Z}_n\to \mathbb{Z}_{p_1}\times\ldots\times \mathbb{Z}_{p_l}$ by taking residues by mods $p_i$. Easy to see that $\phi(\{\text{non zero quadratic res mod n}\})\subseteq \prod_i\{\text{non zero quadratic res mod p_i}\} $ and that $\{\text{non zero quadratic res mod n}\} \leq \prod_i|\{\text{non zero quadratic res mod p_i}\}|\leq\prod_i\fraq{p_i+1}{2}$. But if $n>10$, $l>1$ we get that $\prod_i\fraq{p_i+1}{2}\leq \fraq{n-1}{2}$. Contradiction. Done => Consider even primitive root $\alpha$ modulo odd prime number $n$. So there exists permutation $\tau\in S_{n-1}$ such that $a_i = \alpha ^{\tau(i)}$. Lets search $g_i$ in terms $g_i = \alpha^{h_i}$. We get $n| \alpha^{h_i\tau(i)} - \alpha^{\tau(i+1))$. We know that $\alpha$ is even primitive root mod $n$, so it is equivalent to $n - 1| h_i\tau(i) - \tau(i+1)$. From this easy to chose $a_i$ and $h_i$ to finish this part. $\Box$
07.02.2017 09:24
solver6 wrote: => Consider even primitive root $\alpha$ modulo odd prime number $n$. So there exists permutation $\tau\in S_{n-1}$ such that $a_i = \alpha ^{\tau(i)}$. Lets search $g_i$ in terms $g_i = \alpha^{h_i}$. We get $n| \alpha^{h_i\tau(i)} - \alpha^{\tau(i+1))$. We know that $\alpha$ is even primitive root mod $n$, so it is equivalent to $n - 1| h_i\tau(i) - \tau(i+1)$. From this easy to chose $a_i$ and $h_i$ to finish this part. $\Box$ Sorry your solution is wrong because it's $$h_{i}\cdot \alpha^{\tau _{i}}\equiv \tau _{i+1}\left( mod2^{k}\right) $$but not $$h_{i}\cdot \tau _{i}\equiv \tau _{i+1}\left( mod2^{k}\right) $$
18.02.2018 20:30
Let $S = \left\{ 1, \dots, n-1 \right\}$ henceforth. First we claim no such permutation exists for any odd composite $n$ (not necessarily $2^k+1$) Indeed, for such an $n$, fewer than half the elements of $S$ are quadratic residues (by Chinese remainder theorem, say) but half the elements of $S$ are even, so such a cycle cannot exist. Now for the interesting part, assume $n = 2^k+1$ is prime. Assume $n \ge 17$ (with $n=3$ and $n=5$ being easy to verify by hand). For Fermat primes the notion of ``primitive root'' and ``quadratic nonresidue'' coincide, and moreover since $n \equiv 1 \pmod 8$ and $n \equiv 2 \pmod 3$ we have \[ \left( \frac{-1}{n} \right) = \left( \frac{2}{n} \right) = +1, \qquad \left( \frac{3}{n} \right) = -1. \]Consequently, $3$ is a primitive root modulo $n$, while $2$ is a quadratic residue. So we'll use $3$ as a distinguished primitive root throughout.
We now abstract away the elements of $S$ and construct a directed multigraph $G$ with vertex set $\{T_0, \dots, T_k\}$; for each $s \in S$, if $s \in L_i$ and $s \in R_j$, we will add an edge $T_j \to T_i$ (self-loops allowed). Then it's equivalent to find a directed Eulerian circuit on the graph $G$, (since reading the labels of a circuit gives the desired). Now it is well-known that this is equivalent to $G$ having equal indegree and outdegree at each vertex, and being (strongly) connected. The first part is clear; for strongly connected follows from a few more observations. The vertices $T_{k-1}$ and $T_k$ are both have indegree/outdegree $1$, and there is a path $T_{k-1} \to T_k \to T_0$ (and no edge $T_0 \to T_{k-1}$). Note that because $-1$ is a quadratic residue, every $R_i$ contains odd elements for $i \le k-2$ (pairing each element with its negative). Thus there is an edge from $T_i$ to $T_0$ for $i \le k-2$. Combined with the first observation, we see $T_0$ can be reached from any vertex. There is also an edge from $T_0$ to $T_i$ for $i \le k-2$ by considering the element $3 \cdot 2^i \in L_i$, which is a quadratic nonresidue hence in $R_0$. Combined with the first observation we find that $T_0$ can reach any vertex. This implies $G$ is strongly connected, which completes the proof.
03.07.2019 01:36
Posting for storage. Way too easy for an N8
03.07.2019 05:09
Here is a longer solution. We show only if; if is trivial. We wish to construct the permutation. Let $m = n-1 = 2^k$. If $m = 2$ (take $12$) or $4$ (take $1324$) the problem is also trivial, so assume otherwise ($m \geq 16$) For each $i\in [m]$ we associate a red score $\nu_2(i)$ and a blue score. The blue score is the maximal integer $x\leq k$ such that there exists $g\in [m]$ so that $n := p \mid g^{2^x}-a$. For example, if we ``tier" the numbers based on score we get the following for $p = 17$: \[ \begin{array}{c c c} 0: & \textcolor{red}{1, 3, 5, 7, 9, 11, 13, 15} & \textcolor{blue}{3, 5, 6, 7, 10, 11, 12, 14} \\ \hline 1: &\textcolor{red}{2, 6, 10, 14} & \textcolor{blue}{2, 8, 9, 15} \\ \hline 2: &\textcolor{red}{4, 12} & \textcolor{blue}{4, 13} \\ \hline 3: &\textcolor{red}{8} & \textcolor{blue}{16} \\ \hline 4: &\textcolor{red}{16} & \textcolor{blue}{1} \end{array} \]We will draw arrows from red numbers of tier $t$ to blue numbers of tier $t$ and attempt to get a Hamiltonian cycle on the $[m]$-graph. Indeed, we will first show that we can draw arrows for the tiers $t \geq 1$ to get chains of the form $E\to E\to \cdots E\to O$, where $E$ denotes an even number and $O$ denotes an odd number. Note that if $n$ has blue score $t$ for $t \leq k-2$ then so does $n-t$; to see this we just need to show that $m$ has blue score $> t$, and in fact it has blue score $k-1$ so this works. Furthermore, $m$ is the unique number of blue score $k-1$, and $1$ is the unique number of blue score $k$. In particular, each tier has an equal number of even and odd blue numbers except for $k-1, k$. Now when we draw edges for all the $t\geq 1$ tiers, we note that each vertex has indegree at most $1$, and so the graph is partitioned into some cycles and paths. We note that each path must go $E\to E\to \cdots \to E\to O$ since $E$'s have outdegree $1$, while the $O$'s have outdegree $0$ and indegree $1$. Now, say we pick the graph with the minimum number of cycles. We claim in fact that there are no cycles. Say our cycle is \[ E_1\to E_2\cdots \to E_u \to E_1. \]Since $v \geq 3$ one of the even numbers must have red score at most $k-2$. In particular, say $E_1$ is in tier at most $k-2$. Then, there is some $E_0$ in its same red tier so that $E_0\to O$ for some odd number $E_0$. Say $E_0$'s path was \[ E_{-v}\to E_{-v+1}\to\cdots \to E_0 \to O. \]We see that since $E_1, E_0$ are in the same red tier, and $O, E_2$ are in the same associated blue tier, we can remove the $E_1\to E_2$ and $E_0\to O$ edges and replace them with $E_1\to 0$ and $E_0\to E_2$ edges. Thus we fuse the two connected components and get \[ E_{-v}\to E_{-v+1}\to\cdots \to E_0 \to E_2\to \cdots \to E_u \to E_1 \to O \]and we have removed a cycle, contradiction as we assumed we were already at the minimum number of cycles. Thus there cannot have been cycles at all. Thus we have some paths \[ E_1\to E\to\cdots \to O_1, \]\[ E_2\to E\to \cdots \to O_2, \]\[ \vdots, \]\[ E_{\frac m4} \to E\to \cdots \to O_{\frac m4} \]where $E_{i}$ are the starting points of these paths, and are precisely the $\frac m4$ numbers with blue score $0$. Now for the $P_1, \ldots, P_{\frac m4}$ odd numbers with blue score zero, we can draw $P_i \to E_i$, and so we get \[ P_i \to E_i \to E \to \cdots \to E \to O_i, \]and now we just draw $O_i\to P_{i+1}$ to finish. $\blacksquare$
01.09.2020 05:09
We first show that the existence of the permutation implies that $n$ is prime. Indeed, half of the $a_i$s are odd, so exactly half of $1,\ldots,n-1$ are not squares mod $n$. Claim: The number of square mod $n$ in $1,\ldots,n-1$ is not $\frac{n-1}{2}$ if $n$ is not prime. Proof: It suffices to show the result for $n=p^2$ and $n=pq$ where $p$ and $q$ are distinct odd primes, since any composite $n$ has a factor of one of those two forms, and projecting down to those preserves the property of being a square. If $n=pq$, then there are \[\frac{p+1}{2}\cdot\frac{q+1}{2} -1 < \frac{n-1}{2}\]squares, and if $n=p^2$, there are \[\frac{p^2-p}{2}<\frac{n-1}{2}\]squares. This completes the proof. $\blacksquare$ Thus, the existence of the permutation implies that $n$ is prime. Now suppose that $n$ is prime. We will construct a permutation that satisfies the problem requirement. Consider the directed graph $G$ with vertex set $[n-1]$ and edge $x\to y$ if and only if there is some integer $g$ such that \[g^x\equiv y\pmod{n}.\]It suffices to show that this graph has a Hamiltonian cycle. Let \[A_i=\{x\in[n-1]: v_2(x) = k-i\}\]and \[B_i=\{x\in[n-1]: \mathrm{ord}_p(x) = i\}.\]Note that $|A_i|=|B_i|=2^i$, and both $A_0\sqcup\cdots\sqcup A_k$ and $B_0\sqcup\cdots\sqcup B_k$ are partitions of $[n-1]$. Furthermore, $1\in A_k$ and $1\in B_0$, so \[A_0\sqcup\cdots\sqcup A_i = B_0\sqcup\cdots\sqcup B_i\iff i=k.\]It is easy to check that the edges of $G$ are of the following form: if $x\in A_i$ and $b\in B_j$, then we have an edge $x\to y$ if and only if $i\ge j$. The problem now follows from the following general claim. In the statement and proof of the claim, drop all notations introduced so far. Claim: Consider some finite vertex set $V$ and two partitions $A_0\sqcup\cdots\sqcup A_k$ and $B_0\sqcup\cdots\sqcup B_k$ of it such that $|A_i| = |B_i|$ for all $i$ and \[A_0\sqcup\cdots\sqcup A_i = B_0\sqcup\cdots\sqcup B_i\iff i=k.\]Construct a directed graph $G$ with vertex set $V$ and edges as follows: if $x\in A_i$ and $b\in B_j$, then we have an edge $x\to y$ if and only if $i\ge j$. Then, $G$ has a Hamiltonian cycle. Proof: We claim the following statement is true for $-1\le i\le k-1$: There exists a subgraph of $G$ which is a disjoint collection of paths of length at least $2$ such that the set of all vertices with outdegree $1$ is $A_0\sqcup\cdots\sqcup A_i$ and the set of all vertices with indegree $1$ is $B_0\sqcup\cdots\sqcup B_i$. We prove this by induction on $i$, with $i=-1$ being vacuoulsy true. Now suppose the statement is true for $i-1$, and consider the subgraph that satisfies the conditions. We describe an algorithm to turn this subgraph into a valid subgraph for $i$. Consider $A_i\cup B_i$. Add the vertices in $A_i\cup B_i$ not already in the subgraph to the subgraph. Color all element of $A_i$ blue, and all elements of $B_i$ red, where vertices can have multiple colors. In any existing path, only the head can be read, since all non-heads are in $B_0\sqcup\cdots\sqcup B_{i-1}$, and only the tail can be blue, since all non-tails are in $A_0\sqcup\cdots\sqcup A_{i-1}$. Temporarily collapse all existing paths down to single vertices, and color them based on if their heads and tails are colored (so a path with just a red head will be colored red, but one with red head and blue tail will be colored red/blue). In this collapsed setting, if all vertices are either uncolored or are red/blue, then actually in the uncollasped setting, the vertex set of the subgraph is $A_0\sqcup\cdots\sqcup A_i = B_0\sqcup\cdots\sqcup B_i$, which can't happen. Thus, in the collapsed setting, there is at least one vertex colored just red, and at least one vertex colored just blue (as the number of red and blue vertices is the same). At this point, chain together all the red/blue vertices with directed edges from the blue head to the read tail if the vertex corresponds to a collapsed path, and add a pure blue vertex to the head (again directed from blue tail to red head if the blue vertex was a collapsed path), and similarly add a pure red vertex to the tail. Now, pair up the rest of the pure colored vertices with blue pointing to red. At this point, uncollapse all paths. By construction, the new configuration is still a collection of disjoint paths. The vertices with outdegree $1$ are vertices that originally had outdegree $1$, i.e. elements of the set $A_0\sqcup\cdots\sqcup A_{i-1}$, along with vertices that were colored blue, which are elements of the set $A_i$. Thus, in this new subgraph, the vertices with outdegree $1$ are exactly the elements of the set $A_0\sqcup\cdots\sqcup A_i$. A similar analysis shows that the vertices with indegree $1$ are exactly the elements of the set $B_0\sqcup\cdots\sqcup B_i$. This completes the induction. Now, apply the same algorithm to the state given by $i=k-1$. The only difference now is that in the collapsed setting, all the vertices are red/blue. Simply chain them together in a cycle and uncollapse to create a full Hamiltonian cycle. This completes the proof of the claim. $\blacksquare$ Applying the claim in the obvious way completes the proof. Remark: The construction of the Hamiltonian cycle may be a bit difficult to follow, so here is an example with $k=4$ and $n=17$. The sets $A_i$ and $B_i$ are given by \begin{align*} A_0 = \{16\}\quad,&\quad B_0=\{1\} \\ A_1 = \{8\}\quad,&\quad B_1=\{16\} \\ A_2 = \{4,12\}\quad,&\quad B_2=\{4,13\} \\ A_3 = \{2,6,10,14\}\quad,&\quad B_3=\{2,8,9,15\} \\ A_4 = \{1,3,5,7,9,11,13,15\}\quad,&\quad B_4=\{3,5,6,7,10,11,12,14\}. \end{align*}We now present a possible run of the algorithm. Here, a boxed vertex indicates blue, and a circled vertex indicates red.
08.09.2020 18:05
14.09.2021 08:16
Nice arrows problem! Note that the number after an even number is a QR, so there are $2^{k-1}$ QR's, which by CRT can be shown to imply that $n$ is a prime, so assume $n$ is prime now. Let $a_i = 3^{b_i}$, which is possible since $3$ is a primitive root. Now, consider a complete graph with $2^k$ vertices, corresponding to each $a_i$ with two numbers written on each vertex, in blue color as $v_2(a_i)$ and other in red color as $v_2(b_i)$. It suffices to show that there exists a hamiltonian cycle such that the blue number of each vertex is equal to the red number of the next. This is because we want $g^{k_i(3^{b_i})} \equiv g^{b_{i+1}} \pmod {2^k + 1} \implies 3^{b_i}k_i \equiv b_{i+1} \pmod {2^k}$, which is just saying $v_2(3^{b_i}) \le v_2(b_{i+1})$ Consider the greedy algorithm, start with any thing with red number as $0$, say its blue number is $x$, then next go to a vertex with red number $x$ and keep repeating until stuck, so suppose ur stuck, then say the latest vertex has $zy$ (red,blue), then y must also have been the red number we started with (0) since for every other thing, it's appeared the same number of times in blue and red before this, so $y = 0$, connect this vertex to the initial vertex now since we cant extend the cycle, there are no more 0's left and so every $0$ must appear in it and this means every odd number appears in the cycle. Similarly, we can show that every number can appear in at most one cycle. Now, observe that $3^x$ covers all the $v_2$'s from $1$ to $k$ and note that except for $k-1$, If $v_2(3^x) = z$, then so is $v_2(3^{-x})$, and at least one of them is odd, so $v_2(b_{2k+1})$ spans all numbers except $k-1$, so we have that the cycle formed must have every number apart from $2^k$, but this means the $2^k$ vertex must have both red and blue numbers equal to $2^k$, or $v_2(3^{2^k}) = 2^k$, not true since $3^{2^k} \equiv 1 \pmod {2^k + 1}$, therefore the cycle formed must be a hamiltonian cycle and therefore we are done. $\blacksquare$
14.09.2021 19:05
L567 wrote: we want $g^{k_i(3^{b_i})} \equiv g^{b_{i+1}} \pmod {2^k + 1} \implies 3^{b_i}k_i \equiv b_{i+1} \pmod {2^k}$, which is just saying $v_2(3^{b_i}) \le v_2(b_{i+1})$ I didn't understood this part , how can u append $a_i = 3^{b_i}$ at the exponent as both are equal $mod p$ , not $mod (p-1)$ ?
15.09.2021 09:55
Oops I probably should have mentioned, I'm letting $g_i = 3^{k_i}$, so $g_i^{a_i} \equiv a_{i+1}$ is just saying $(3^{k_i})^{3^{b_i}} \equiv 3^{b_{i+1}} \pmod {2^k + 1}$ $\implies 3^{k_i(3^{b_i})} \equiv 3^{b_{i+1}} \pmod {2^k + 1}$ $\implies k_i(3^{b_i}) \equiv b_{i+1} \pmod {\phi(2^k + 1)}$ $\implies k_i(3^{b_i}) \equiv b_{i+1} \pmod {2^k}$ $\implies v_2(3^{b_i}) \le v_2(b_{i+1})$
15.09.2021 11:59
U are first saying that $a_i \equiv 3^{b_i} mod p$ L567 wrote: Let $a_i = 3^{b_i}$, which is possible since $3$ is a primitive root. Then saying $g_i^{a_i} \equiv (3^{k_i})^{3^{b_i}} mod p$ i.e $a_i \equiv 3^{b_i} (mod p-1) $ L567 wrote: $g_i^{a_i} \equiv a_{i+1}$ is just saying $(3^{k_i})^{3^{b_i}} \equiv 3^{b_{i+1}} \pmod {2^k + 1}$ ??
05.01.2022 16:15
Solved with rama1728. First, assume $k > 1,$ otherwise it's trivial. If $n$ is not a prime number, such a permutation does not exist because there are less than $\frac{n-1}{2}$ nonzero quadratic residues, but there are $\frac{n-1}{2}$ even numbers. If $n$ is a prime number, let $r$ be a primitive root $\pmod{2^k+1}.$ Create a directed graph on $k+1$ vertices labeled $0$ to $k.$ For each integer $b$ from $1$ to $2^k,$ join $v_2(a)$ to $v_2(b)$ where $g^a \equiv b \pmod{2^k+1}$ and label this edge with $b.$ If $b_1$ goes into the node that $b_2$ goes out of, then $b_1$ can be followed by $b_2$ in the desired permutation. So it suffices to find an Eulerian Cycle in this graph. It is enough to prove each node has equal in or out degree, and the graph is strongly connected (for any two nodes $A,B$ you can find a path from $A$ to $B$ or from $B$ to $A$). The first part follows from that fact that $g^1,g^2, \dots , g^{2^k} \pmod{2^k+1}$ forms a permutation of $1,2, \dots , 2^k.$ For the second part, consider that $2^k$ joins $k-1$ to $k$ and $1$ joins $k$ to $0.$ Take any integer $1 \le m \le k-2;$ one of $2^{2^{m}}, 2^{2^{m}+2^{k-1}} \equiv -2^{2^m}$ is an odd residue modulo $2^k+1.$ So $0$ joins to $m.$ Also, note that $3$ is a primitive root (since it is a quadratic nonresidue) but $2$ is not. So then, $3 \cdot 2^{m}$ is a primitive root residue as well, and since it is less than $2^k,$ it has $v_2$ of $m.$ So $0$ joins to $m.$ So our graph is strongly connected, which is enough. $\square$
26.04.2023 18:36
Let $ n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_m^{\alpha_m} $ be the prime facrorization of $n$. Define $rad(n) = p_1 p_2 \dots p_m$. Asume that there exsits permutation $(a_i)$ and a sequnce $(g_i)$ such that: $\forall i < n: g_i^{a_i} \equiv a_{i + 1} mod (n)$ ($a_0 = a_{n-1}, a_n = a_1$). Let $f$ be a function such that $f(a_i) = i $, for all $a_i$. Now we have 2 cases: Case 1: n > rad(n): Which mean that $\exists p | n: \nu_{p} (n) > 1 = \nu_{p} (rad(n)) $ .Notice that the following is also true: $ n > 2rad(n)$. Let $i = f(rad(n))$ and $j = f(2rad(n))$. Then: $ g_{i-1}^{a_{i-1}} \equiv rad(n) \text{ } mod(n)$. So $rad(n) | g_{i-1} $ and $\nu_p(g_{i-1}^{a_{i-1}}) = 1 \Rightarrow a_{i-1} = 1$ . Similarly we get $a_{j-1} = 1$, which is a contradiction, because $i \neq j$. Case 2: n = rad(n): Then $n = p_1 p_2 \dots p_m $. Notice that we have exactly $2^{k-1}$ even numbers, so we must have the same number of quadratic residues in $\{1, 2, \dots , n - 1 \}$ (we call $r$ a quadratic residue for n if $r$ is qadratic residue for all the primes dividing $n$ ( $\forall i \leq m: \left( \frac {r} {p_i} \right) \neq -1$)). For each $p_i$ we have exactly $\frac {p_i + 1} {2}$ quadratic residues (including $0$). By chinese reminder theorem we get $\prod_{i=1}^m \frac {p_i + 1} {2}$ quadratic residues for $n$, which includes $0$. So we get: $$ \prod_{i=1}^m \frac {p_i + 1} {2} - 1 = 2^{k-1} $$If $m > 1$ (if $n$ is not a prime): \begin{align*} 2 &< (p_{m-1} - 1)(p_{m} - 1) \\ 1 + p_{m-1} + p_{m} &< p_{m-1}p_{m} \\ (p_{m - 1} + 1)(p_{m} - 1) &< 2p_{m-1}p_{m} \\ \frac {p_{m - 1} + 1} {2} \cdot \frac {p_{m} + 1} {2} &< \frac {1} {2} \cdot p_{m-1} p_{m} \end{align*}So we get: $$ 2^{k-1} = \prod_{i=1}^m \frac {p_i + 1} {2} - 1 = \prod_{i=1}^{m - 2} \frac {p_i + 1} {2} - 1 \cdot \frac {p_{m - 1} + 1} {2} \cdot \frac {p_{m} + 1} {2} - 1< \prod_{i=1}^{m - 2} \cdot \frac{p_{m-1}p_{m}} {2} - 1 = \frac {2^{k} + 1} {2} - 1 = 2^{k-1} - \frac {1} {2} < 2^{k-1} $$Which is a contradiction. Then $m = 1$, so $n$ is a prime number. Constraction for $n = p:$ Devide $S = \{1, 2, \dots , p -1 \}$ in to subsets $A_1, \dots, A_k$, such that $x \in A_t$ iff $\nu_2(x) = t$. Similarly devide $S$ into subsets {B_1, B_2, \dots , B_k} such that $x \in B_t$ iff $t \cdot ord_p(x) = 2^k$. Notice that $\forall t \leq k: |A_t| = |B_t|$, beacause of the exsistance of primitice root of $p$. Then let $a_1 = 1$ and if $a_{i} \in A_t$ choose $a_{i + 1}$ from $B_t$ (so that we have no duplicates). We can always choose a such number (when $i \neq n - 1$, because $|A_t| = |B_t|$. So we are done!
25.08.2023 20:52
If $n$ is composite, then there are at most $2^{k-1}$ quadratic nonresidues, but there are more than $2^{k-1}$ even residues, which contradicts the existence of a cycle as in the problem. Assume $n>17$ prime henceforth, as $n=3, 5$ are easy to see. Fix a primitive root $g$ modulo $2^k+1$. Construct a directed multigraph $G$ on $1, \dots, k$, where we append an edge $\nu_2(a) \rightarrow \nu_2(b)$ labeled $b$ where $a$ and $b$ are positive integers in $\{0, 1, \dots, 2^k+1\}$ such that $g^a \equiv b \pmod{2^k+1}$. Thus the problem reduces to show that $G$ has an Eulerian cycle. Lemma: $3$ is a primitive root modulo $2^k+1$. Proof. This is equivalent to showing that $3$ is a quadratic nonresidue modulo $2^k+1$. Note that $k$ is even by modulo 3 reasons. We have \[ \left(\frac{3}{2^k+1}\right) = \left(\frac{2^k+1}{3} \right) = \left(\frac{2}{3} \right) = -1, \]so we are done. Claim: Each vertex $v$ of $G$ has the same indegree as outdegree. Proof. Note that $\{g^1, g^2, \dots, g^{2^k}\}$ is also the set of nonzero residues modulo $2^k+1$. Denote $\sigma$ by the permutation mapping $[1, \dots, 2^k]$ to $[g^1, \dots, g^{2^k}]$. Fix $0 \le j \le k$. For every $1 \le a \le 2^k$ where $\nu_2(a)=j$, the outdegree of $j$ is the number of distinct values taken by $\nu_2(\sigma(a))$ and since $\sigma$ is a bijection, this is also the indegree of $j$, as desired. Claim: The graph $G$ is strongly connected. Proof. We will now show that (i) $k-1 \rightarrow k \rightarrow 0$, and (ii) $0$ connects to every vertex $1 \le j \le k-2$ in both directions; clearly this is sufficient. (i) Since $g^{2^k} \equiv 1 \pmod{2^k+1}$, there is an edge $k \rightarrow 0$. Similarly, since $g^{2^{k-1}} \equiv -1 \equiv 2^k \pmod{2^k+1}$, there is also an edge $k-1 \rightarrow k$. (ii) Choose some $1 \le j \le k-2$. Clearly $3 \cdot 2^j < 2^k+1$ is a quadratic nonresidue modulo $2^k+1$, as $2^j$ is a quadratic residue and $3$ is not per the Lemma. Thus, $3 \cdot 2^j \equiv g^a \pmod{2^k+1}$ for some odd $a$, so there is an edge $0=\nu_2(a) \rightarrow \nu_2(3 \cdot 2^j) = j$. Since either $g^{2^j}$ or $g^{2^j + 2^{k-1}}$ are odd residues modulo $2^k+1$, and both $2^j$ and $2^j + 2^{k-1}$ have a $\nu_2$ of $j$, there is an edge $j \rightarrow 0$, so we are done. The above two claims imply that $G$ has an Eulerian cycle, and we conclude.
17.10.2023 17:25
This problem will become a lot easier when we prove there are only finitely fermat primes. We can manually check the result holds for $k = 1, 2$. Else, suppose $k \ge 3$. Claim: No such permutation exists if $n$ is not prime. Proof. Suppose that $n > p$ for prime $p \mid n$. Then there are $\frac{n-1}{2} = 2^{k-1}$ even numbers in $a_i$ yet at most $n \cdot \frac{p-1}{2p}$ quadratic residues, contradiction as the mapping $a_i \mapsto g_i^{a_i}$ must be unique $\pmod{n}$. $\blacksquare$ Now, suppose $n$ is prime. Then $n$ has a primitive root $g$ with $g^{2^k} \equiv 1 \pmod{n}$. Let $k = 2^a$ by virtue of being a Fermat prime. Partition $\{1, \dots, n-1\}$ as residues into $A_0 \sqcup A_1 \sqcup A_2 \sqcup \dots \sqcup A_{k}$ based on the largest $i \le k$ for which they can be expressed as $g^{2^i \cdot c} \pmod{2^k+1}$ for odd $c$. Similarily, partition $\{1, \dots, n-1\}$ into $T_0 \sqcup T_1 \sqcup T_2 \sqcup \dots \sqcup T_k$ based off $\nu_2$. Then the maps from $T_i \to A_i$ must be bijective. Claim: For $i \le k - 2$ and $i = k$, $A_i$ contains an element of $T_{0}$. Proof. Note that $g$ must be odd, giving the result for $i = 2^k$. For $i \le k - 2$, it follows that $g^{2^i \cdot c}$ and $g^{2^{k-1} + 2^i \cdot c}$ are both in $A_i$ and are opposite signed, giving the result. $\blacksquare$ Claim: Such a permutation exists. Proof. Naively take matchings $T_i \mapsto A_i$. Consider the cycles $C_1, C_2, \dots, C_n$. Then, whenever the matching $T_i \to A_i$ has multiple cycles $a_1 \mapsto b_1$ and $a_2 \mapsto b_2$, we can modify the pairing to become $a_2 \mapsto b_2$ and $a_2 \mapsto b_1$ to combine the two cycles. By repeating this, this eventually means that only one cycle goes through the entire matching $T_i \mapsto A_i$. Since $A_i \cap T_{0}$ is nonempty, this cycle must go through all o f $T_i \mapsto A_i$ for all $i \ne k-1$. Then, since $A_{k-1} = \{2^k\}$, it must also contain the final matching. $\blacksquare$
06.12.2024 01:42
First I will prove that if $n$ is composite that it does not satisfy that property. To see this note that $n$ is odd, and is composite. Thus we have $\frac{n-1}{2}$ even values and thus must have at least $\frac{n-1}{2}$ quadratic residues. However note that amongst the non coprime residues, they must have even $\nu_p$ for all $p$ and so be subtracting one from each $nu_p$ we get a unique value which is not a quadratic residue and is not coprime. Amongst the coprime values there is at most the number of coprime terms divided by $2$, however we can find a value that is a QR modulo one prime dividing $n$ and not a $QR$ modulo another so we have less than $\frac{n-1}{2}$. Now to prove that when $n$ is prime such a permutation exists. Note that as $n-1=2^k$ we have that the possible orders are $1, 2, 4, \dots 2^k$. Now take a primitive root, we find that there are an equal number of values that have order $2^i$ for $i\in 1, \dots, k$ and such that $\nu_2(m)=i$. Let the sets $A_0$, $A_2$, \dots, $A_k$ be the set of values such that they have order $2^k$, $2^{k-1}$, \dots, $1$. Let the sets $B_0$, $B_1$, \dots $B_k$ such that $\nu_2$ of values in $B_0$ is $0$, etc. Now note that of the values in $A_i$ for $i\neq k, k-1$ that at least half of the values in each of those sets must be odd and half must be even as we can multiply any value by $-1$ and keep the order the same. As $A_k$ contains just $1$, we get that the maximum sum of the even values from $A_i$ to $A_k$ is $2^{k-i}-1$ so one of the values in $B_i$ has order lower than $i$ as $B_i$ contains $2^{k-i}$ values. Now define an algorithm where we start with the the highest order odd value that is left, and after that we take the order of the previous value call it $i$, and take the term remaining in $B_i$ with highest order. Thus we only ever decrease the order if we only have terms in $B_i$ with order less than $i$. Also because we always have a value in $B_i$ with order less than $i$ we eventually have to decrease, we stop when we get to a point where we have an even value that is a primitive root at the end. Thus we can always do this algorithm as long as we have an even value. When we stop we get a bunch of ordered chains that end with a primitive root even value and start with an odd value. We can put these chains together and add any remaining primitive root odd values in between to get a hamiltonian cycle.
14.12.2024 00:27
If Part: Suppose FTSOC $n$ was composite then first if it wasn't square free consider a prime $p$ with $p^2 \mid n$ then consider some $a_{j+1}=p$ then $p^2 \mid g_j^{a_j}-p$ which means that $\nu_p(g_j^{a_j})=1$ therefore $a_j=1$ but notice that you can also make this for some $a_{i+1}=2p$ which would gives $a_i=1$ for $i \ne j$ therefore the permutation condition is violated. Now if $n$ was squarefree let it be $n=\prod_{i=1}^{k} p_i$ for primes $p_1, \cdots, p_k$ and $k \ge 2$, notice that for an $a_i$ even we get that $a_{i+1}$ is a QR $\pmod n$ however this implies there is at least $\frac{n-1}{2}$ QRs $\pmod n$ that are not $0$, but from CRT we have that there must be $\prod_{i=1}^{k} \left(\frac{p_i+1}{2} \right) -1 < \prod_{i=1}^{k} \left(\frac{2p_i}{3} \right)-1=\left(\frac{2}{3} \right)^k n -1 \le \frac{4n}{9}-1$ such QRs which is obviously a lot less than $\frac{n-1}{2}$ thus we are done. Only If Part: Now suppose that $p=2^k+1$ was a prime, then $k=2^{\ell}$ or else if $k$ had an odd prime factor then $2^k+1$ would not be prime trivially, also assume $\ell \ge 2$ as the other two cases can be checked by hand trivially. Now from here notice that $3$ is a primitive root $\pmod p$ because $\left(\frac{3}{2^{2^{\ell}}+1} \right)=\left(\frac{2^{2^{\ell}}+1}{3} \right)=\left(\frac{2}{3} \right)=-1$ which shows that $3$ is an NQR which is enough to conclude thanks to the fact that if $p \mid a^n-1, a^m-1$ then $p \mid a^{\gcd(m,n)}-1$ so if we had that $\text{ord}_p(3) \ne p-1$ then if it was odd we would get $p \mid 3^{\frac{p-1}{2}}-1$, a clear contradiction, and if this order was even then we would get that it actually has to be a power of $2$ that will therefore forcefully divide $\frac{p-1}{2}$ and then same thing. So now fix a primitive root $g$ of $p$ and consider a directed multi-graph $G$ with vertices labeled as $\{0, 1 \cdots ,2^{\ell} \}$ and we connect $\nu_2(\kappa) \to \nu_2(l)$ for every time it happens that $g^{\kappa} \equiv l \pmod p$ (for any such $l$, a unique $\kappa$ exists), so now the problem is reduced to finding a directed eulerian cycle in $G$ which happens if the indegree and outdegree of each vertex is equal and the graph is strongly connected, the latter is true as first notice that we trivially get $2^{\ell}-1 \to 2^{\ell}$ from the fact that $g^{2^{2^{\ell}-1}} \equiv -1 \equiv 2^{2^{\ell}} \pmod p$ but now also $2^{\ell} \to 0$ from Fermat's Little Theorem, now trivially from odd exponents we connect with all NQRs $\pmod p$, so remember when we proved that $3$ was NQR?, from Jacobi symbol one trivially gets that $3 \cdot 2^j$ for $0 \le j \le 2^{\ell}$ is also an NQR and thus we have that $0 \to j$ exists, and to prove the reverse (which is that from any $j$ in the given range we can connect it to $0$ in the other direction), we notice that one of $g^{2^i}, g^{2^i+2^{2^{\ell}-1}}$ is odd $\pmod p$ for $\nu_2(i) \le 2^{\ell}-2$ because if the first one was even the second one is odd minus even (odd), and for the last two $\nu_2$'s we got the covered at the beggining. Now to prove that for each vertex their indegree and outdegree are equal, we notice that the family of values $\pmod p$ spanned from $g^i$ for some $\nu_2(i)$ fixed are different from each other and thus are $2^{2^{\ell}-\nu_2(i)-1}$ for $\nu_2(i) \le 2^{\ell}-1$ and $1$ for $i=2^{2^{\ell}}$, so now we need to compute the number of exponents of $g$ that reach some value with $\nu_2(i)$ fixed on $\pmod p$, for the biggest one the assertion is clearly true, so for the rest note that from the property of $g$ being primitive root they are mapped to a unique exponent which means that we are counting all numbers $i$ with $\nu_2(i)$ fixed between $1$ and $2^{2^{\ell}}$ which gives the same count as above, thus this thing is also proven. Now with both needed conditions proven we have that such Eulerian circuit exists thus we are done .