CN-TST 2023 Problem 7

Given the integer $n\geq 2$ and a integer ${a}$ , which is coprime with ${n}$ . A country has ${n}$ islands $D_1$ , $D_2$ , $\cdots$ , $D_n$ . For any $1\leq i\neq j\leq n$ , there is a one-way ferry $D_i$ to $D_j$ if and only if $ij\equiv ia\pmod n$ . A tourist can initially fly to any of the islands, and then he can only take a one-way ferry. What is the maximum number of islands he can visit?

Created by Zhenhua Qu