Estonian Math Competitions

Answer: (a) Miku; (b) Juku.

The positional representation with radix $a$ consisting of $n$ ones denotes the sum $a^{n-1}+a^{n-2}+\cdots +a+1$ which equals $\frac{a^n-1}{a-1}$.

a. Let $a\equiv 1(\mathrm{mod}p)$. If $p>2$ or $a\equiv 1(\mathrm{mod}4)$ then, by the lifting-the-exponent lemma, the exponent of the prime $p$ in the canonical representation of $\frac{a^n-1}{a-1}$ equals that in the canonical representation of $n$. Thus to win, Miku may choose any number $n$ that is divisible by $p$. If $p=2$ and $a\equiv -1(\mathrm{mod}4)$ then the exponent of the prime 2 in the canonical representation of $a-1$ is 1, while that in the canonical representation of $a^2-1$ is larger as $a^2\equiv 1(\mathrm{mod}4)$. Thus to win, Miku may choose $n=2$.

Let now $a\not\equiv 1(\mathrm{mod}p)$. By Fermat's little theorem, $a^{p-1}\equiv 1(\mathrm{mod}p)$. Hence $a^n\equiv 1(\mathrm{mod}p)$ whenever $n$ is a multiple of $p-1$. Then the numerator of the fraction $\frac{a^n-1}{a-1}$ is divisible by $p$ while the denominator is not, whence the value of the fraction is divisible by $p$. Consequently, Miku can win by choosing any multiple of $p-1$ greater than 1 as $n$.

b. We show that Juku wins by choosing $n=2p-1$. Let $a$ be the number chosen by Miku.

Let $a\equiv 1(\mathrm{mod}p)$. If $p>2$ or $a\equiv 1(\mathrm{mod}4)$ then, by the lifting-the-exponent lemma, the exponent of $p$ in the canonical representation of $\frac{a^n-1}{a-1}$ equals that in the canonical representation of $n$. As $p$ does not divide $2p-1$, it does not divide $\frac{a^n-1}{a-1}$ either. If $p=2$ and $a\equiv -1(\mathrm{mod}4)$ then $a^n\equiv -1(\mathrm{mod}4)$, whence 2 does not divide $a^n-1$. Therefore 2 does not divide $\frac{a^n-1}{a-1}$.

Let now $a\not\equiv 1(\mathrm{mod}p)$. By Fermat's little theorem, $a^{p-1}\equiv 1(\mathrm{mod}p)$ and $a^p\equiv a(\mathrm{mod}p)$, giving $a^n=a^{2p-1}\equiv a(\mathrm{mod}p)$. Thus $a^n\not\equiv 1(\mathrm{mod}p)$. As $p$ does not divide the numerator of the fraction $\frac{a^n-1}{a-1}$, it cannot divide the value of the fraction either.