Maths Olympiad Prep

Library / /33 of 53

Number theory Difficulty 6.4 National olympiad Prove it China

Let pp be a prime number greater than 33. Prove that there exist integers a1,a2,,ata_1, a_2, \dots, a_t that satisfy the following conditions:

a.
p2<a1<a2<<atp2, -\frac{p}{2} < a_1 < a_2 < \cdots < a_t \le \frac{p}{2},

b.
pa1a1pa2a2patat=3m, \frac{p-a_1}{|a_1|} \cdot \frac{p-a_2}{|a_2|} \cdot \cdots \cdot \frac{p-a_t}{|a_t|} = 3^m,
where mm is a positive integer.

Solution

Proof By the Division Algorithm, there exist unique integers qq and rr such that p=3q+rp = 3q + r, where 0<r<30 < r < 3.
Taking b0=rb_0 = r, then
pb0b0=3c0b1b0, where 3b1 and 0<b1<p2. \frac{p-b_0}{|b_0|} = \frac{3^{c_0} \cdot b_1^*}{|b_0|}, \text{ where } 3 \nmid b_1^* \text{ and } 0 < b_1^* < \frac{p}{2}.
Taking b1=±b1b_1 = \pm b_1^* such that b1p(mod3)b_1 \equiv p \pmod{3}, then
pb1b1=3c1b2b1, where 3b2 and 0<b2<p2. \frac{p-b_1}{|b_1|} = \frac{3^{c_1} \cdot b_2^*}{b_1^*}, \text{ where } 3 \nmid b_2^* \text{ and } 0 < b_2^* < \frac{p}{2}.
Taking b2=±b2b_2 = \pm b_2^* such that b2p(mod3)b_2 \equiv p \pmod{3}, then
pb2b2=3c2b3b2, where 3b3 and 0<b3<p2. \frac{p-b_2}{|b_2|} = \frac{3^{c_2} \cdot b_3^*}{b_2^*}, \text{ where } 3 \nmid b_3^* \text{ and } 0 < b_3^* < \frac{p}{2}.
Repeating this process, we get b0,b1,,bpb_0, b_1, \dots, b_p.
Since these p+1p+1 integers are in the interval (p2,p2)(-\frac{p}{2}, \frac{p}{2}), a certain integer occurs twice. Suppose bi=bjb_i = b_j, i<ji < j, and bib_i, bi+1b_{i+1}, ..., bj1b_{j-1} are distinct. So,
pbibipbi+1bi+1pbj1bj1=3cibi+1bi3ci+1bi+2bi+13cj1bjbj1. \frac{p-b_i}{|b_i|} \cdot \frac{p-b_{i+1}}{|b_{i+1}|} \cdots \frac{p-b_{j-1}}{|b_{j-1}|} = \frac{3^{c_i} \cdot b_{i+1}^*}{b_i^*} \cdot \frac{3^{c_{i+1}} \cdot b_{i+2}^*}{b_{i+1}^*} \cdots \frac{3^{c_{j-1}} \cdot b_j^*}{b_{j-1}^*}.
Since bi=bjb_i = b_j, then bi=bjb_i^* = b_j^*. So the above expression equals to
3ci+ci+1++cj1=3n,n>0. 3^{c_i+c_{i+1}+\cdots+c_{j-1}} = 3^n, \quad n > 0.
Put bi,bi+1,,bj1b_i, b_{i+1}, \dots, b_{j-1} in ascending order, as desired.

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.