Easy complete system of residues problem in Taiwan TST

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

Easy complete system of residues problem in Taiwan TST

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2025 Taiwan TST Round 1 Independent Study 1-N

The post below has been deleted. Click to close.

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

13 posts

Fysty

#1 h Mar 5, 2025, 6:10 AM

Y by

Find all positive integers $n$ such that there exist two permutations $a_0,a_1,\ldots,a_{n-1}$ and $b_0,b_1,\ldots,b_{n-1}$ of the set $\lbrace0,1,\ldots,n-1\rbrace$ , satisfying the condition
$ia_i\equiv b_i\pmod{n}$ for all $0\le i\le n-1$ .

Proposed by Fysty

Z K Y

The post below has been deleted. Click to close.

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

960 posts

#2 h Mar 5, 2025, 7:06 AM • 3 Y

Y by Want-to-study-in-NTU-MATH, megarnie, truongphatt2668

This should work... (writeup converted to LaTeX by ChatGPT, I hope there's no errors)
We replace $a_i$ and $b_i$ with $\sigma(i)$ and $\tau(i)$ respectively. Then the condition is
$i\sigma(i) \equiv \tau(i) \pmod{n}, \quad i = 0,1,\dots,n-1.$
\textbf{Claim 1:} $\gcd(\sigma(i),n) = \gcd(\tau(i),n) = \gcd(i,n)$ .

\textbf{Proof:} Strong induction on $\gcd(\tau(i),n)$ , letting it vary over divisors of $n$ .

For example, the base case is when $\gcd(\tau(i),n) = 1$ . Then it is true that $\gcd(i\sigma(i),n) = 1$ , implying
$\gcd(i,n) = \gcd(\sigma(i),n) = 1,$ as desired.

In particular, this provides a bijection between $i, \sigma(i)$ , and $\tau(i)$ coprime to $n$ .

Now, if $\gcd(\tau(i),n) = d$ , then $\gcd(i,n)$ and $\gcd(\sigma(i),n)$ divide $d$ .

But from the induction hypothesis that for all $c < d$ with $c \mid d$ ,
$\gcd(i,n) = c \iff \gcd(\sigma(i),n) = c \iff \gcd(\tau(i),n) = c,$ we must have
$\gcd(i,n) = \gcd(\sigma(i),n) = d.$ Again, we get this to be an equivalence, i.e.,
$\gcd(i,n) = d \iff \gcd(\sigma(i),n) = d \iff \gcd(\tau(i),n) = d.$ $\square$

\textbf{Claim 2:} $n$ is square-free.

\textbf{Proof:} Assume $p^2 \mid n$ for some prime $p$ . Choosing $i = p$ , we get
$\gcd(\tau(i),n) = \gcd(\sigma(i),n) = p.$ So $p^2 \mid i\sigma(i)$ but $p^2 \nmid \tau(i)$ , a contradiction to them being equivalent modulo $p^2$ . $\square$

\textbf{Claim 3:} $p \mid n \Rightarrow p = 2$ .

\textbf{Proof:} For any $p \mid n$ , let
$A_p \overset{\text{def}}{=} \{ i \in \{1, 2, \dots, n-1\} : \gcd(i,n) = n/p \}.$
$= \left\{ \frac{n}{p}, \frac{2n}{p}, \dots, \frac{(p-1)n}{p} \right\}.$ Note that $i \in A_p \iff \sigma(i) \in A_p \iff \tau(i) \in A_p$ .

Now, we have
$\prod_{i \in A_p} i\sigma(i) \equiv \prod_{i \in A_p} \tau(i) \pmod{n}.$ Since $\sigma$ and $\tau$ are bijections over $A_p$ , we get
$\prod_{i \in A_p} i\sigma(i) \equiv \left( \prod_{i \in A_p} i \right)^2 \equiv \left(\left( \frac{n}{p} \right)^{p-1} (p-1)!\right)^2 \pmod{n}.$ Similarly,
$\prod_{i \in A_p} \tau(i) \equiv \prod_{i \in A_p} i \equiv \left( \frac{n}{p} \right)^{p-1} (p-1)! \pmod{n}.$ Thus,
$\left(\left( \frac{n}{p} \right)^{p-1} (p-1)!\right)^2 \equiv \left( \frac{n}{p} \right)^{p-1} (p-1)! \pmod{n}.$ In particular, this equivalence also holds modulo $p$ .
Simplifying using Fermat's and Wilson's theorems (noting that $n$ is squarefree),
$(1 \cdot (-1))^2 \equiv 1 \cdot -1 \implies 1 \equiv -1 \implies 2 \equiv 0 ,$ where congruences are modulo $p$ . Thus $p \mid 2 \implies p = 2$ .

From Claims 2 and 3, we have $n \in \{1,2\}$ .

For $n = 1$ , consider $\sigma(0) = 0, \tau(0) = 0$ .

For $n = 2$ , consider $\sigma(0) = 0, \tau(0) = 0$ , $\sigma(1) = \tau(1) = 1$ .

Thus, $n = 1, 2$ are the only solutions. $\blacksquare$

This post has been edited 3 times. Last edited by AshAuktober, Mar 5, 2025, 8:10 AM

Z K Y

The post below has been deleted. Click to close.

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

5553 posts

#3 h Mar 6, 2025, 5:26 PM • 3 Y

Y by AshAuktober, imagien_bad, shafikbara48593762

The answer is $n = 1$ and $n = 2$ . To show these work, set $a_i = i$ for each $0 \le i \le n - 1$ . Now assume $n > 2$ . We will show that $n$ doesn't work.

Claim: $\gcd(a_i, n) = \gcd(b_i, n)$ for each $0 \le i \le n -1$ .
Proof: For $i \in [0,n-1]$ , let $f(i) = \gcd(b_i, n) - \gcd(a_i,n)$ . Since $b_i \equiv i a_i \pmod n$ , $\gcd(b_i, n) = \gcd(i a_i, n) \ge \gcd(a_i, n)$ , implying $f(i) \ge 0$ . However, since $(a_i)_{i=0}^{n-1}, (b_i)_{i=0}^{n-1}$ are permutations of the same set, summing the equality $f(i) = \gcd(b_i, n) - \gcd(a_i, n)$ over $0 \le i \le n - 1$ gives $\sum_{i=0}^{n-1} f(i) = 0$ . Since $f$ is always nonnegative, $f$ must be identically zero, as desired. $\square$

Claim: $\gcd(i, n) = \gcd(b_i, n)$ for each $0 \le i \le n -1$ .
Proof: For $i \in [0,n-1]$ , let $g(i) = \gcd(b_i, n) - \gcd(i,n)$ . Since $b_i \equiv i a_i \pmod n$ , $\gcd(b_i, n) = \gcd(i , n) \ge \gcd(i, n)$ , implying $g(i) \ge 0$ . However, since $(i)_{i=0}^{n-1}, (b_i)_{i=0}^{n-1}$ are permutations of the same set, summing the equality $g(i) = \gcd(b_i, n) - \gcd(i, n)$ over $0 \le i \le n - 1$ gives $\sum_{i=0}^{n-1} g(i) = 0$ . Since $g$ is always nonnegative, $g$ must be identically zero, as desired. $\square$

Thus, we can conclude $\gcd(i,n) = \gcd(a_i, n) = \gcd(b_i, n)$ for each $i$ .

Claim: $n$ is squarefree.
Proof: If $p^2 \mid n$ , then if we set $i = p$ , note that $\gcd(i, n) = \gcd(a_i, n) = \gcd(b_i, n) = p$ , but then $\gcd(i a_i, n)$ is a multiple of $p^2$ , so $p^2$ must divide $b$ , a contradiction. $\square$

Claim: $n$ is a power of $2$ .
Proof: Assume not. Let $p$ be an odd prime dividing $n$ and $S$ be the set of all integer $0 \le x \le n - 1$ so that $\gcd(x,n) = \frac np$ . We note that $S = \left \{ \frac np, 2 \cdot \frac np, \ldots, (p-1) \cdot \frac np \right \}$ .

For each $i \in S$ , let $c_i = \frac{a_i p}{n}$ and $d_i = \frac{b_i p}{n}$ . Note that $i c_i \equiv d_i \pmod p$ and $(c_i)_{i \in S}$ and $(d_i)_{i \in S}$ are permutations of $1, 2, \ldots, p - 1$ .

Multiplying the congruences together over all $i \in S$ gives that $\prod_{i \in S} i \prod_{i \in S} c_i \equiv \prod_{i\in S} d_i \pmod p$ Since $(c_i)_{i\in S}$ and $(d_i)_{i\in S}$ are permutations of $1, 2, \ldots, p - 1$ , we have $\prod_{i\in S} c_i \equiv \prod_{i \in S} d_i \equiv (p-1)! \equiv -1 \pmod p$ by Wilson's Theorem.

We can also compute $\prod_{i\in S} i = \left( \frac np \right)^{|S|} \cdot 1 \cdot 2 \cdot \cdots (p-1) = \left( \frac np \right)^{p - 1} \cdot (p-1)!$ . Since $n$ is squarefree, $p \nmid \frac np$ , so this evaluates to $1 \cdot (p-1)! \equiv -1 \pmod p$ by FLT and Wilson's Theorem.

Hence $(-1) \cdot (-1) \equiv -1 \pmod p$ , which implies $p \mid 2$ , a contradiction because $p$ is odd. $\square$

Combining the two claims gives that $n \in \{1,2\}$ , as desired.

Z K Y

The post below has been deleted. Click to close.

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

270 posts

#4 h Mar 7, 2025, 1:01 AM • 1 Y

Y by megarnie

The answer is $n=1$ and $n=2$ ; taking $a_i = i$ suffices.

Claim. $d \mid a_i \iff d \mid b_i \iff d \mid i$ for all $d \mid n$ .

Proof. Let $d$ be a divisor of $n$ . Notice that there are exactly $n/d$ $b_i$ which are divisible by $d$ , and these are given by $b_{d i}$ for $0 \le i < n/d$ . This establishes $d \mid b_i \iff d \mid i$ . In particular, $d \mid a_i$ implies $d \mid ia_i = b_i$ implies $d \mid i$ , hence the $n/d$ values of $a_i$ that are divisible by $d$ are also given by $a_{di}$ . We are done.

Corollary. $a_{di}$ is a permutation of $d[n/d] - d$ .

Now let $n$ have an odd prime divisor $p$ . Let $m = n/p$ , and note that the sequences $c_i = a_{mi}/m$ and $d_i = b_{mi}/m$ are well defined and permutations of $[n]-1$ . In particular,
$\begin{align*} mi a_{mi} &\equiv b_{mi} \pmod{n} \\ mi c_i &\equiv d_i \pmod{p}. \end{align*}$ Taking a product over $1 \le i \le p-1$ gives
$m^{p-1} (p-1)!^2 \equiv (p-1)! \pmod p \implies m^{p-1} \equiv -1 \pmod{p}.$ Clearly this is impossible.

Now let $4 \mid n$ , and replace $p$ with $4$ above. Then, note that $\{c_0, c_2\} = \{d_0, d_2 \} = \{0, 2\}$ , hence $\{c_1,c_3 \} = \{d_1, d_3 \} = \{1, 3\}$ , so $m^2 \cdot 3 \cdot 3 \equiv 3 \pmod{4}, \qquad m^2 \equiv 3 \pmod{4},$ absurd. This proves that all $n > 3$ fail.

Notational Abuse

This post has been edited 3 times. Last edited by popop614, Mar 7, 2025, 1:05 AM
Reason: adfsafsd

Z K Y

The post below has been deleted. Click to close.

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

340 posts

#5 h Mar 7, 2025, 1:37 AM

Y by

This is here

This post has been edited 1 time. Last edited by hectorleo123, Mar 29, 2025, 8:02 PM

Z K Y

The post below has been deleted. Click to close.

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

1 post

#6 h Mar 30, 2025, 7:23 AM

Y by

megarnie wrote:

Claim: $n$ is a power of $2$ .
Proof: Assume not. Let $p$ be an odd prime dividing $n$ and $S$ be the set of all integer $0 \le x \le n - 1$ so that $\gcd(x,n) = \frac np$ . We note that $S = \left \{ \frac np, 2 \cdot \frac np, \ldots, (p-1) \cdot \frac np \right \}$ .

For each $i \in S$ , let $c_i = \frac{a_i p}{n}$ and $d_i = \frac{b_i p}{n}$ . Note that $i c_i \equiv d_i \pmod p$ and $(c_i)_{i \in S}$ and $(d_i)_{i \in S}$ are permutations of $1, 2, \ldots, p - 1$ .
.

Why $(c_i)_{i \in S}$ and $(d_i)_{i \in S}$ are permutations of $1, 2, \ldots, p - 1$ ?

This post has been edited 1 time. Last edited by AllenZhuang, Mar 30, 2025, 7:24 AM
Reason: Grammar issue

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a