Good Permutations in Modulo n

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Good Permutations in Modulo n

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: BMO 2025 P1

The post below has been deleted. Click to close.

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

16 posts

swynca

#1 h Apr 27, 2025, 2:03 PM • 2 Y

Y by dangerousliri, megarnie

An integer $n > 1$ is called $\emph{good}$ if there exists a permutation $a_1, a_2, a_3, \dots, a_n$ of the numbers $1, 2, 3, \dots, n$ , such that:
$(i)$ $a_i$ and $a_{i+1}$ have different parities for every $1 \leq i \leq n-1$ ;
$(ii)$ the sum $a_1 + a_2 + \cdots + a_k$ is a quadratic residue modulo $n$ for every $1 \leq k \leq n$ .
Prove that there exist infinitely many good numbers, as well as infinitely many positive integers which are not good.

This post has been edited 2 times. Last edited by swynca, Apr 27, 2025, 4:15 PM

Z K Y

The post below has been deleted. Click to close.

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

92 posts

#2 h Apr 27, 2025, 2:51 PM • 2 Y

Y by lksb, Assassino9931

We prove that any prime $p\equiv 3\mod 4$ works.
We have $\left(\frac{-1}{p}\right)=-1$ , so we can split $1, 2, ..., p-1$ into $\frac{p-1}{2}$ pairs $(r_i, s_i)$ such that $r_i+s_i=p$ , $\left(\frac{r_i}{p}\right)=1$ and $\left(\frac{s_i}{p}\right)=-1$ .
Order the pairs such that, for all $1\leq i\leq k$ , $r_i$ is odd and, for all $k+1\leq i\leq \frac{p-1}{2}$ , $r_i$ is even.
Now just consider the permutation $r_1, s_1, r_2, s_2, ..., r_k, s_k, p, r_{k+1}, s_{k+1}, ..., r_{\frac{p-1}{2}}, s_{\frac{p-1}{2}}$ .
Modulo $2$ this will be $1, 0, 1, 0, ..., 1, 0, 1, 0, 1, ..., 0, 1$ , so $(i)$ is achieved.
At any point the sum $a_1+...+a_m\mod p$ will be either $0$ or $r_i$ , for a $1\leq i\leq \frac{p-1}{2}$ , so a quadratic residue.

Now, for the second part, just choose $n=2^k, k\geq 2$ .
We will prove that there don't exist two quadratic residues with difference equal to $2$ , hence such a permutation wouldn't exist, since there must exist $a_i=2$ in the permutation.
Suppose there existed $a, b$ such that $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)=1$ and $b-a\equiv 2\mod 2^k$ .
Since $b-a\equiv 2\mod 2^k$ , we have two cases:
1. $\{a,b\}\equiv \{0,2\}\mod4$ , in which case there should exist a perfect square $m^2\equiv 2\mod 4$ , impossible.
2. $\{a,b\}\equiv \{1,3\}\mod4$ , in which case there should exist a perfect square $m^2\equiv 3\mod 4$ , impossible.
So such permutation doesn't exist for all $n=2^k$ .

This post has been edited 2 times. Last edited by Double07, Apr 27, 2025, 6:56 PM
Reason: Deleted a mistake

Z K Y

The post below has been deleted. Click to close.

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

62 posts

DensSv

#3 h Apr 27, 2025, 3:02 PM

Y by

Does anyone know the proposer?

Z K Y

The post below has been deleted. Click to close.

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

28 posts

#5 h Apr 27, 2025, 3:24 PM

Y by

The (i) condition adds a small twist to the problem.
I believe the problem looks also complete and interesting to solve without the (i) condition.

-- To construct such a permutation, it is natural to look for a sequence with pairs that add up to 0 mod $p$ .
The next desire is to pair a residue with a non-residue and also for them to alternate.
Choosing $p \equiv 3 \pmod 4$ solves this, as Double07 showed in his/her post.

-- When we need to prove that no such sequence exists. We can choose $n=2k$ , then
the last sum is a number that we can compute: $k(2k+1)\equiv k \pmod{2k}$ . If there exists $x^2 \equiv k \pmod{2k}$ ,
then $x^2 = 2k\cdot s + k = k (2s +1)$ . Choosing $k = 2m^2$ assures that no such $x$ exists.

This post has been edited 2 times. Last edited by Ivan_Borsenco, Apr 27, 2025, 3:25 PM
Reason: -

Z K Y

The post below has been deleted. Click to close.

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

5610 posts

#7 h Apr 27, 2025, 4:11 PM

Y by

Part 1) Prove that there are infinitely many good numbers.
Fix any prime $p \equiv 3 \pmod 4$ . Let $n = p$ . Choose values for these odd indices of the sequence $a_1, a_3, a_5,\ldots, a_{2k - 1}$ so that they consist of all the even quadratic residues modulo $p$ exactly once and $a_{2k - 1} = 0$ . Now, choose the values of these even indices of the sequence $a_{2k}, a_{2k + 2}, a_{2k + 4} , \ldots, a_{p - 1}$ so that they consist of all the odd quadratic residues modulo $p$ exactly once. Now, for any index $i$ , if $a_i$ is a nonzero QR mod $p$ , then choose $a_{i + 1} = p - a_i$ . One can check that this sequence works.
Part 2) Prove that there are infinitely many numbers that are not good.
Let $n = 8k + 4$ . We compute $a_1 + a_2 + \cdots + a_n = 1 + 2 + \cdots + n = \frac{n(n+1)}{2} = (4k + 2)(8k +5) \equiv 4k + 2 \pmod{8k + 4}$ . Anything that is $4k + 2\pmod{8k + 4}$ must also be $2 \pmod 4$ , so it cannot be a perfect square, as desired.

Z K Y

The post below has been deleted. Click to close.

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

71 posts

EVKV

#8 h Apr 27, 2025, 5:53 PM

Y by

Claim 1 : All primes $p \equiv 3$ mod $4$ are good

Proof 1 :

Claim 1.1 : If a is a QR mod p then p-a is not where a $\neq$ pk for some integer k

Proof 1.1 : FTSOC assume for some integer x,y $x^{2} +y^{2} \equiv a +p-a \equiv 0$ mod $p$
Which is nonsense by Fermat's christmas theorem

Defination 1.1 : We define $a_{i}$ as the odd numbers which are QR mod p and lesser than p. . Here
$1 \leq i \leq r$ where r is the amount of odd numbers which are QR mod p and lesser than p.

Defination 1.2 : We define $b_{i}$ as the even numbers which are QR mod p and lesser than p. . Here
$1 \leq i \leq k$ where k is the amount of even numbers which are QR mod p and lesser than p.

Also clearly $a_{i}$ and $p-a_{i}$ have different parity so do $b_{i}$ and $p-b_{i}$

Now we already know there are $\frac{p-1}{2}$ non-zero quadratic residues mod p. So, $a_{i}$ and $p-a_{i}$ and $b_{i}$ and $p-b_{i}$ form $\frac{p-1}{2}$ pairs and as none of them include p ( all are non zero quadratic residues)
we will get all numbers $\leq p$ in the following sequence which will also satisfy the other conditions clearly as at any point it will be either 0, $a_{i}$ , $b_{i}$ which are all QRs

$a_{1}$ , $p-a_{1}$ , $\cdots$ , $a_{r}$ , $p-a_{r}$ , $p$ , $b_{1}$ , $p-b_{1}$ , $\cdots$ , $b_{k}$ , $p-b_{k}$ ,

Claim 2 : All numbers of the form $4K$ where K is odd are not good (They are bad)

Proof 2 : Obviously If x is a QR mod $4K$ it is a QR mod 4
So, All $\sum_1 ^{k} a_{i}$ $\equiv$ $0,1$ mod 4
Now as $0+2$ and $1+2$ are not QRs mod 4
Thus we can never have $a_{i+1} \equiv 2$ mod 4 for all $i \leq 4K-1$ but that is nonsense as for all $r \leq 4K$ there is an $a_{g} = r$

QED

Remark : A very very tasty problem which i never expected to be able to solve. Had so much fun tho had fake solved once lol.

I rate it d6

Solved : 27/4/25

This post has been edited 4 times. Last edited by EVKV, Apr 28, 2025, 7:38 PM

Z K Y

The post below has been deleted. Click to close.

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

932 posts

#9 h Apr 27, 2025, 6:46 PM • 3 Y

Y by bsf714, NO_SQUARES, Achilleas

One of the best Number Theory problems on Olympiads. I will show my solution in some details another way how it could be done since I think most likely it would be hard someone to thought of this.

As before to show that there are infinitely non good numbers we take $n=4^m$ .

We are going to prove that $n=2p$ is a good number where $p$ is a prime number such that $p\equiv 5\pmod6$ . To do that with some manipulation we can prove $x^3$ is a complete residue for $x=1,2,...,2p$ modulo $2p$ . After that we have for every $i=1,2,...,2p$ there exist a unique $x_i\in\{1,2,...,2p\}$ such that $i\equiv x_i^3\pmod{2p}$ and we have that $i$ and $x_i$ have same parities. Now to finish the problem we use the identity,
$1^3+2^3+...+k^3=\left(\frac{k(k+1)}{2}\right)^2.$

This post has been edited 3 times. Last edited by dangerousliri, Apr 27, 2025, 7:19 PM

Z K Y

The post below has been deleted. Click to close.

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

1545 posts

#10 h Apr 28, 2025, 1:19 AM

Y by

For the first part just notice that taking $n$ as a prime $p \equiv 3 \pmod 4$ just works as $-1$ is NQR mod $p$ and as a result we have that $k(p-k) \equiv -k^2 \pmod p$ which is an NQR by multiplicativiness of the Legendre Symbol and therefore we can split in $\frac{p-1}{2}$ pairs $(q_i,n_i)$ for which $q_i+n_i=p$ and one is a QR and the other is NQR, and the idea for the parity part is just to put $1$ first then $p-1$ and then another odd one and so on until you run out of odd ones then add zero and add even ones and then their pair to finish.
Now to see infinitely many $n$ that fail we pick $n=2^k$ for $k$ large and the reason for this pick is that clearly we can't have two QRs that are consecutive by $2$ as it leads to a contradiction $\pmod 4$ but at some point we have to add $2$ to the sum so that gives a contradiction for it working, thus done.

Z K Y

The post below has been deleted. Click to close.

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

67 posts

#11 h May 2, 2025, 2:38 PM • 2 Y

Y by missionjoshi.65, Bergo1305

For the first part, we take $n$ as a prime $p \equiv 3 \pmod 4$ . Note that if $i$ is a QR, then $p-i$ is NQR, and vice versa. Then we start pairing the terms as follows:

Let $s_2, s_3, \cdots, s_{\frac{p-1}2}$ be all quadratic residues mod $p$ not including $1$ .

- First pair $(1, p-1)$ .
- Then for $i > 1$ , keep on pairing $(a_i, a_{i+1}) = (s_i, p-s_i)$ where $s_i$ is odd, till we run out of odd QR's.
- Then we let the next term be $p$ .
- Finally pair $(a_i, a_{i+1}) = (s_i, p-s_i)$ where $s_i$ is even, till we run out of them.

It is clear that this pairing works.

For the second part, we let $n = 4p$ for an odd prime $p$ . Then, note that $t^2 \equiv \sum a_i = 2p(4p+1) \equiv 2p \pmod {4p}.$

Then, we get a contradiction as

$4p \mid t^2 - 2p \implies 2p \mid t^2 \implies 4p^2 \mid t^2 \implies 4p \mid t^2 \implies 4p \mid 2p.$

This post has been edited 5 times. Last edited by Thapakazi, May 2, 2025, 4:07 PM

Z K Y

The post below has been deleted. Click to close.

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

optimusprime154

23 posts

optimusprime154

#12 h May 16, 2025, 1:13 PM

Y by

first we prove that every prime of the form $4k+3$ is good. we know that if $a$ is a quadratic residue $mod$ $p$ then $p - a$ wont be a quadratic residue $mod$ $p$ this means that we can divide the residues into two groups, $b_1, b_2, \ldots , b_t$ and $c_1, c_2 \ldots, c_m$ where the first are odd residues and the second are even residues. we begin by creating a construction: $b_1, p - b_1, b_2, p - b_2, \ldots b_t, p-b_t, p, c_1, p - c_1, \ldots c_m, p - c_m$ which clearly satisfies both conditions.
now for the second part, i claim all numbers of the form $4^k$ are not good, by taking the sum $a_1+a_2 \cdots +a_n$ is the same as $\frac{n(n+1)}{2} = (2^{2k-1})(4^k + 1) \equiv (2^{2k-1}) mod 4^k$ , but $2k-1$ is odd therefore $2^{2k-1}$ can not be a quadratic residue.

Z K Y

The post below has been deleted. Click to close.

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

129 posts

MR.1

#13 h May 16, 2025, 6:17 PM

Y by

trash sol

:wallbash_red:

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a