Maths Olympiad Prep

Library / /4 of 7

Number theory Difficulty 8.8 Shortlist Prove it China

A positive integer NN is called a *good number* if the decimal representation of NN can be divided into at least 5 segments of digits, each segment containing at least one non-zero digit, and these segments (ignoring any leading zeros) can be viewed as positive integers which can be divided into two groups, with each group forming a geometric sequence in the appropriate order. (If a group has only one or two positive integers, it is also considered a geometric sequence.)
For example, 20240327 is a good number. In fact, it can be divided into 202403272|02|403|2|7, a total of 5 segments of digits, with the two groups of positive integers (2, 2, 2) and (7, 403) each forming a geometric sequence.
Let p=1+a+a2++amp = 1 + a + a^2 + \dots + a^m be a prime number, where a>1a > 1 and m>2m > 2 are integers. Prove that 10p11p\frac{10^{p-1}-1}{p} is a good number.

Solution

Let p=1+a+a2++amp = 1 + a + a^2 + \cdots + a^m be a prime number, where a>1a > 1 and m>2m > 2 are integers. Prove that 10p11p\frac{10^{p-1}-1}{p} is a good number.

*Proof*. Since p=1+a++am=am+11a1p = 1 + a + \cdots + a^m = \frac{a^{m+1}-1}{a-1} is a prime number, q=m+1q = m + 1 must be a prime number. Given q=m+1>3q = m + 1 > 3, we have q5q \ge 5. Note that p=aq1a1p = \frac{a^q-1}{a-1} divides aq1a^q-1 and does not divide a1a-1, so the order of aa modulo pp is exactly qq. Therefore, qp1q \mid p-1. Let p1=qLp-1 = qL.

Consider the remainder tt of 10L=10(p1)/q10^L = 10^{(p-1)/q} modulo pp, which satisfies tq1(modp)t^q \equiv 1 \pmod{p}. By Lagrange's theorem, the solutions to the congruence equation xq10(modp)x^q - 1 \equiv 0 \pmod{p} are exactly {1,a,a2,,aq1}\{1, a, a^2, \cdots, a^{q-1}\}. Thus, we can assume t=art = a^r, where rD={0,1,,q1}r \in D = \{0, 1, \cdots, q-1\}. Furthermore, 10kL10^{kL} modulo pp is akra^{\langle kr \rangle}, where \langle \cdot \rangle denotes the remainder modulo qq, taking values in D={0,1,,q1}D = \{0, 1, \cdots, q-1\}.

Consider N=10p11p=10qL1p=10qL1pN = \frac{10^{p-1}-1}{p} = \frac{10^{qL}-1}{p} = \lfloor \frac{10^{qL}-1}{p} \rfloor as a p1p-1 digit number, with leading zeros if necessary. Divide NN into segments of length LL from left to right (the leftmost segment may contain leading zeros), forming qq segments corresponding to integers x0,x1,,xq1x_0, x_1, \cdots, x_{q-1}:
x0=10Lp=10Larp,x1=102Lp10Lx0=102La2rp10L10Larp=ar10La2rp,\multicolumn2cxk=akr10La(k+1)rp,k=1,2,,q1. \begin{align*} x_0 &= \lfloor \frac{10^L}{p} \rfloor = \frac{10^L - a^r}{p}, \\ x_1 &= \lfloor \frac{10^{2L}}{p} \rfloor - 10^L \cdot x_0 = \frac{10^{2L} - a^{\langle 2r \rangle}}{p} - 10^L \cdot \frac{10^L - a^r}{p} = \frac{a^r \cdot 10^L - a^{\langle 2r \rangle}}{p}, \\ \multicolumn{2}{c}{\dots \dots \dots} \\ x_k &= \frac{a^{\langle kr \rangle} \cdot 10^L - a^{\langle (k+1)r \rangle}}{p}, \quad k = 1, 2, \cdots, q-1. \end{align*}
If r=0r=0, then x0=x1==xq1=10L1px_0 = x_1 = \cdots = x_{q-1} = \frac{10^L-1}{p} can be divided into two groups, each forming a geometric sequence.

If r{1,2,,q1}r \in \{1, 2, \cdots, q-1\}, then {krk=0,1,,q1}={0,1,2,,q1}\{\langle kr \rangle \mid k = 0, 1, \cdots, q-1\} = \{0, 1, 2, \cdots, q-1\}. Let
A={kDkr=0,1,,qr1},B={kDkr=qr,,q1}. A = \{k \in D \mid \langle kr \rangle = 0, 1, \cdots, q-r-1\}, \quad B = \{k \in D \mid \langle kr \rangle = q-r, \cdots, q-1\}.
When kAk \in A, (k+1)r=kr+r\langle (k+1)r \rangle = \langle kr \rangle + r, and when kBk \in B, (k+1)r=kr+rq\langle (k+1)r \rangle = \langle kr \rangle + r - q. Thus,
{xkkA}=10Larp{1,a,a2,,aqr1} forms a geometric sequence, \{x_k \mid k \in A\} = \frac{10^L - a^r}{p} \cdot \{1, a, a^2, \cdots, a^{q-r-1}\} \text{ forms a geometric sequence,}
{xkkB}=10Larqp{aqr,aqr+1,,aq1}=aqr10L1p{1,a,,ar1} \{x_k \mid k \in B\} = \frac{10^L - a^{r-q}}{p} \cdot \{a^{q-r}, a^{q-r+1}, \cdots, a^{q-1}\} = \frac{a^{q-r} \cdot 10^L - 1}{p} \cdot \{1, a, \cdots, a^{r-1}\}
also forms a geometric sequence. This completes the proof. \square

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.