23rd Korean Mathematical Olympiad Final Round

Let us denote by $a|b$ when a positive integer $a$ divides $b$. We write $p^c\nmid n$ when a positive integer $n$ is a multiple of $p^c$, but not of $p^{c+1}$ for a prime $p$.

Lemma 1. For a given prime $q$ and a positive integer $a$ such that $(a,q)=1$, let $s$ be the smallest positive integer $x$ satisfying $q|a^s-1$. Any positive integer $y$ such that $q|a^y-1$ must be a multiple of $s$. Proof. Put $y=qs+r_0$, where $q,r_0$ are integers and $0\le r_0<s$. Noting $q|a^y-1=(a^s-1)(a^{y-s}+a^{y-2s}+\cdots +a^{r_0})+a^{r_0}-1$ leads us to $q|a^{r_0}-1$. By the minimality of $s$, we get $r_0=0$. $\square$

1. The case of $p=2$ It is immediate to note that all $n_i$s are odd and greater than or equal to $3$. Let $q(\ge 3)$ be the smallest prime dividing one of $n_1,n_2,\dots ,n_k$. Without loss of generality, we assume $q|n_2$. Let $s\ge 2$ be the smallest positive integer $x$ satisfying $q|2^r-1$. Then by Fermat's little theorem and Lemma 1, we get $s|q-1$. Thus $s<q$. We realize that $s$ has a smaller prime factor than $q$, so it contradicts $q|2^{n_1}-1$, which implies $s|n_1$. We conclude that there does not exist $(n_1,n_2,\dots ,n_k)$ fulfilling conditions, hence $2$ is not a nice prime.

2. The case of prime $p\ge 3$ (1) In the case $k=1$: we prove that there does not exist a positive integer $n$ such that $n|p^n-1$ and $\left(\frac{p^n-1}{n},n\right)=1$. First, under the condition $n|p^n-1$, we show the smallest prime factor $q_1$ of $n$ must divide $p-1$. Let $n=q_1^{e_1}\cdots q_r^{e_r}$, $q_1<\cdots <q_r$. $n|p^n-1$ implies $q_1|p^n-1$. Let $s$ be the smallest positive integer $x$ such that $q_1|p^x-1$. Then it is obvious that $s\le q_1-1$ and $s|n$. If $s>1$, $s$ is a product of primes smaller than $q_1$, it violates that $n$ cannot have smaller prime factors than $q_1$. We obtain $s=1$ so $q_1|p-1$. Now let $n=q_1^{e_1}{n}_0$. In the expression $p^n-1=p^{q_1^{e_1}{n}_0}-1=(p^{n_0}-1){\prod }_{j=0}^{e_1-1}\frac{p^{q_1^j{n}_0}-1}{p^{q_1^{j-1}{n}_0}-1}$. We easily see the number of prime $q_1$ in $p^n-1$ is at least $e_1+1$. So we get $q_1|\left(\frac{p^n-1}{n},n\right)$ reducing to contradiction. In sum, for any given prime $p$, there does not exist a positive integer $n$ satisfying all conditions when $k=1$.

(2) In the case $k\ge 2$: we are always able to find sequences of positive integers $(n_1,n_2,\dots ,n_k)$ for infinitely many $k$. This proves that any odd primes are nice. There are various ways of taking the sequences and the proposed way below is one of them.

Lemma 2. For a positive integer $c$ and a prime $q$, $q^c|p-1$ implies $q^{c+d}|p^{q^d}-1$. Moreover, - When $q$ is odd or $(q=2,c\ge 2)$: the smallest positive integer $x$ such that $q^{c+d}|p^x-1$ is $q^d$ and $q^{c+d}||p^{q^d}-1$ holds. - When $(q=2,c=1)$: Let $c^{\prime }$ be the smallest positive integer such that $2^{c^{\prime }}||p^2-1$. Then the smallest positive integer $x$ satisfying $2^{c^{\prime }-d}||p^x-1$ is $2^{d+1}$ and $2^{c^{\prime }+d}||p^{2d+1}-1$ holds.

Proof. Let us show only the first case. When $d=0$, it is true by definition. Let us assume the statement is true when $d=d_0$ and try to show when $d=d_0+1$. We need to find the smallest positive integer $x$ such that $q^{c+d_0+1}||p^x-1$. Since $q^{c+d_0}||p^x-1$ also holds, by the assumption, $x$ is a multiple of $q^{d_0}$ and we set $x=q^{d_0}u$. From the equation $p^x-1=p^{q^{d_0}u}-1=(p^{q^{d_0}}-1)(p^{(u-1)q^{d_0}}+p^{(u-2)q^{d_0}}+\cdots +1)$, $p^{q^{d_0}}-1$ is already a multiple of $q^{c+d_0}$, so it is enough to have $p^{(u-1)q^{d_0}}+p^{(u-2)q^{d_0}}+\cdots +1$ a multiple of $q$. $p^{(u-1)q^{d_0}}+p^{(u-2)q^{d_0}}+\cdots +1\equiv 1+\cdots +1\equiv u(\mathrm{mod}q)$ implies $q\nmid u$ and conversely, we easily check $p^x-1$ is really a multiple of $q^{c+d_0+1}$ when $q$ divides $u$. Thus $x=q^{d_0}u$ is a multiple of $q^{d_0+1}$. On the other hand, $\frac{p^{q^{d_0}}-1}{p^{q^{d_0}-1}}=p^{(q-1)q^{d_0}}+p^{(q-2)q^{d_0}}+\cdots +1$ is only a multiple of $q$ not of $q^2$, whose proof is presented below. In conclusion, we obtain $q^{c+d}||p^{q^d}-1$ by induction. The reason for $q||p^{(q-1)q^{d_0}}+p^{(q-2)q^{d_0}}+\cdots +1$: Let $v$ be a positive integer such that $p^{q^{d_0}}=1+qv$. Then, $p^{(q-1)q^{d_0}}+p^{(q-2)q^{d_0}}+\cdots +1=(1+qv{)}^{q-1}+(1+qv{)}^{q-2}+\cdots +(1+qv)+1\equiv 1+(q-1)qv+1+(q-2)qv+\cdots +(1+qv)+1=q+\frac{(q-1)q^2}{2}v\equiv q(\mathrm{mod}{q}^2)$. In the case $(q=2,c=1)$, we are not able to guarantee the term $\frac{(q-1)q^2}{2}v$ in the almost last equation is a multiple of $q^2$ so we separate the case. $\square$

Now we define $S=\{q|q$ a prime dividing $p-1\}$ and let $q\in S$. Take $n_1=p-1$ and let $c_{q,1}$ be an integer such that $q^{c_{q,1}}||p-1$ for $q\in S$. Similarly, we define $c_{q,2}$ as an integer satisfying $q^{c_{q,2}}||p^{n_1}-1=p^{n_1-1}-1$. Inductively for $q\in S,i\ge 1$, let $c_{q,i+1}$ be an integer such that $q^{c_{q,i+1}}||p^{n_i}-1$ and $n_{i+1}:={\prod }_{q\in S}{q}^{c_{q,i+1}}$. We define $c_{q,i}$ and $n_i$ in this way accordingly as $i$ gets increased one by one, then we notice that $c_{q,i}$ also gets large as $i$ does so. Fix $q_0\in S$ and put $c:=c_{q_0,1}$. (When $q_0=2,c_{q_0,1}=1$, let $c=c^{\prime }-1$, where $c^{\prime }$ is in Lemma 2.(ii).) Since there exists an integer $i$ such that $q_0^{c_{q_0,i}}>p-1$, we call such $i$ $i_0$. Moreover, there exists a positive integer $k_0$ such that $\frac{p^{k_0}-1}{(p-1)q_0^{k_0}}\ge \frac{p+1}{2}$, which is justified by that the left hand side is a function divergent when $k_0$ goes to infinity. Now let $k$ be any integer greater than $1+\max \{i_0,k_0,3\}$. Except the case $q_0=2,c_{q_0,1}=1$, we can, in fact, define $k$ to be any integer greater than $\max \{i_0,k_0,3\}$. We apply the above definition of $c_{q,i+1}$ and $n_{i+1}$ till $i<k-2$ and let $n_{k-1}:=q_0^{c_{q_0,k-1}}$. It is easy to observe $n_{k-1}\ge p-1\ge \frac{p-1}{2}$. From our choices of sequences $\{n_i\}$, it is clear to verify the following for $1\le i<k-1$ $$-1,n_1=p-1\ge \frac{p+1}{2},n_{i+1}=p-1\ge \frac{p+1}{2}$$ $$-2,n_{i+1}|p^{n_i}-1,\left(\frac{p^{n_i-1}}{n_{i-1}},n_{i+1}\right)=1$$ The first one comes from $c_{q,i+1}>c_{q,i}\ge 1$. From Lemma 2, we even know $c_{q,i+1}=c_{q,i}+c_{q,i}$ holds when $q$ is odd or $c_{q,i}\ge 2$. Finally, let $n_k:=\frac{p^{n_k}-1}{q_0^{c_{q_0,k-1}}{\prod }_{q\in S}{q}^{c_{q,q}}}=\frac{p^{n_k}-1}{q_0^{c_{q_0,k-1}}(p-1)}$, then $(n_k,q_0)=1$ follows from Lemma 2, hence it satisfies the second condition $(n_k,\frac{p^{n_k}-1}{n_k})=1$ for $n_k$. We also obtain the first condition $n_k\ge \frac{p+1}{2}$ from $\frac{p^{n_k}-1}{(p-1)q_0^{c_{q_0,k-1}}}\ge \frac{p+1}{2}$. Noting $(p-1,\frac{p^{n_k}-1}{p-1})=(p-1,n_k)$ for this $n_k$ and $(q,n_k)=1$ for $q\in S$, we establish $(p-1,n_k)=1$. $\square$