Maths Olympiad Prep

Library / /28 of 63

Number theory Difficulty 6.7 National olympiad Prove it Japan

Determine the number of tuples of integers (a1,a2,,a17)(a_1, a_2, \dots, a_{17}) which satisfy 2ai202 \le a_i \le 20 for all i=1,,17i = 1, \dots, 17 and
a1a2a16a17a2a3a17a171(mod17). a_1^{a_2} \cdots a_{16}^{a_{17}} \equiv a_2^{a_3} \cdots a_{17}^{a_{17}} \equiv 1 \pmod{17}.
Here the exponential is calculated in order from upper right two numbers.

Solution

20421914\boxed{2042 \cdot 19^{14}}

First we show the following lemma.

Lemma. Let a,b,ca, b, c be integers satisfying a0(mod17)a \neq 0 \pmod{17}, b1b \ge 1, c4c \ge 4. Then abc1(mod17)a^{b^c} \equiv 1 \pmod{17} holds if and only if a1(mod17)a \equiv 1 \pmod{17} or bb is even.

Proof. If a1(mod17)a \equiv 1 \pmod{17}, obviously abc1(mod17)a^{b^c} \equiv 1 \pmod{17} holds. If bb is even, c4c \ge 4 shows bcb^c is divisible by 1616. By Fermat's little theorem a161(mod17)a^{16} \equiv 1 \pmod{17} holds thus abc1(mod17)a^{b^c} \equiv 1 \pmod{17}. We show the converse. If abc1(mod17)a^{b^c} \equiv 1 \pmod{17} holds, we can take minimum positive integer dd satisfying ad1(mod17)a^d \equiv 1 \pmod{17}. If a1(mod17)a \neq 1 \pmod{17} then d1d \neq 1. Assume bcb^c is not divisible by dd, then bcb^c can be written in the form bc=sd+tb^c = sd + t with a non-negative integer ss and an integer tt satisfying 1t<d1 \le t < d hence
at(ad)sat=abc1(mod17), a^t \equiv (a^d)^s \cdot a^t = a^{b^c} \equiv 1 \pmod{17},
which contradicts to the minimality of dd. Therefore bcb^c is divisible by dd. Similarly 1616 is divisible by dd and d1d \neq 1 shows dd is even. Hence bcb^c is even and thus bb is even. ■

If a10(mod17)a_1 \equiv 0 \pmod{17} or a20(mod17)a_2 \equiv 0 \pmod{17} then the condition is not satisfied. From here we assume a10(mod17)a_1 \neq 0 \pmod{17} and a20(mod17)a_2 \neq 0 \pmod{17}. Let
c1=a3a4a5a6a7,c2=a4a5a6a7, c_1 = a_3^{a_4^{a_5^{a_6^{a_7}}}}, \quad c_2 = a_4^{a_5^{a_6^{a_7}}},
then c122=4c_1 \ge 2^2 = 4, c222=4c_2 \ge 2^2 = 4 holds. We have two cases; when a2a_2 is odd and when it is even.

* When a2a_2 is odd.

Lemma shows a1a2c11(mod17)a_1^{a_2^{c_1}} \equiv 1 \pmod{17} if and only if a11(mod17)a_1 \equiv 1 \pmod{17}. Since a218a_2 \neq 18, we have a21(mod17)a_2 \neq 1 \pmod{17} and then lemma shows a2a3c21(mod17)a_2^{a_3^{c_2}} \equiv 1 \pmod{17} if and only if a3a_3 is even. Therefore the number of tuples satisfying the condition is 18101914=8019141 \cdot 8 \cdot 10 \cdot 19^{14} = 80 \cdot 19^{14}.

* When a2a_2 is even.

We have a10(mod17)a_1 \neq 0 \pmod{17} then lemma shows a1a2c11(mod17)a_1^{a_2^{c_1}} \equiv 1 \pmod{17}. By lemma, a2a3c21(mod17)a_2^{a_3^{c_2}} \equiv 1 \pmod{17} holds if and only if a21(mod17)a_2 \equiv 1 \pmod{17} or a3a_3 is even. Therefore the number of tuples satisfying the condition is 1811915+189101914=1962191418 \cdot 1 \cdot 19^{15} + 18 \cdot 9 \cdot 10 \cdot 19^{14} = 1962 \cdot 19^{14}.

Hence the total number of tuples satisfying the condition is 801914+19621914=2042191480 \cdot 19^{14} + 1962 \cdot 19^{14} = 2042 \cdot 19^{14}.

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.