Maths Olympiad Prep

Library / /76 of 86

Number theory Difficulty 6.9 National olympiad Prove it Estonia

Let pp be a fixed prime number. Juku and Miku play the following game. One of the players chooses a natural number aa such that a>1a > 1 and aa is not divisible by pp, his opponent chooses any natural number nn such that n>1n > 1. Miku wins if the natural number written as nn ones in the positional numeral system with radix aa is divisible by pp, otherwise Juku wins. Which player has a winning strategy if:

a. Juku chooses the number aa, tells it to Miku and then Miku chooses the number nn;

b. Juku chooses the number nn, tells it to Miku and then Miku chooses the number aa?

Solution

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

The positional representation with radix aa consisting of nn ones denotes the sum an1+an2++a+1a^{n-1} + a^{n-2} + \dots + a + 1 which equals an1a1\frac{a^n-1}{a-1}.

a. Let a1(modp)a \equiv 1 \pmod{p}. If p>2p > 2 or a1(mod4)a \equiv 1 \pmod{4} then, by the lifting-the-exponent lemma, the exponent of the prime pp in the canonical representation of an1a1\frac{a^n-1}{a-1} equals that in the canonical representation of nn. Thus to win, Miku may choose any number nn that is divisible by pp. If p=2p = 2 and a1(mod4)a \equiv -1 \pmod{4} then the exponent of the prime 2 in the canonical representation of a1a-1 is 1, while that in the canonical representation of a21a^2-1 is larger as a21(mod4)a^2 \equiv 1 \pmod{4}. Thus to win, Miku may choose n=2n = 2.

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

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

Let a1(modp)a \equiv 1 \pmod{p}. If p>2p > 2 or a1(mod4)a \equiv 1 \pmod{4} then, by the lifting-the-exponent lemma, the exponent of pp in the canonical representation of an1a1\frac{a^n-1}{a-1} equals that in the canonical representation of nn. As pp does not divide 2p12p-1, it does not divide an1a1\frac{a^n-1}{a-1} either. If p=2p = 2 and a1(mod4)a \equiv -1 \pmod{4} then an1(mod4)a^n \equiv -1 \pmod{4}, whence 2 does not divide an1a^n-1. Therefore 2 does not divide an1a1\frac{a^n-1}{a-1}.

Let now a≢1(modp)a \not\equiv 1 \pmod{p}. By Fermat's little theorem, ap11(modp)a^{p-1} \equiv 1 \pmod{p} and apa(modp)a^p \equiv a \pmod{p}, giving an=a2p1a(modp)a^n = a^{2p-1} \equiv a \pmod{p}. Thus an≢1(modp)a^n \not\equiv 1 \pmod{p}. As pp does not divide the numerator of the fraction an1a1\frac{a^n-1}{a-1}, it cannot divide the value of the fraction either.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.