Number Theory: Structures, Examples, and Problems

1.7. Numerical Systems
239
Problem 1.7.14.
Let p
≥
5
be a prime and choose k
∈ {
0
, . . . ,
p
−
1
}
. Find the
maximum length of an arithmetic progression none of whose elements contain the
digit k when written in base p.
(1997 Romanian Mathematical Olympiad)
Solution.
We show that the maximum length is
p
−
1 if
k
=
0 and
p
if
k
=
0.
In a
p
-term arithmetic progression, the lowest nonconstant digit takes all values
from 0 to
p
−
1. This proves the upper bound for
k
=
0, which is also a lower
bound because of the sequence 1
, . . . ,
p
−
1. However, for
k
=
0, it is possible
that when 0 occurs, it is not actually a digit in the expansion but rather a leading
zero. This can occur only for the first term in the progression, so extending the
progression to
p
+
1 terms would cause an honest zero to appear. Thus the upper
bound for
k
=
0 is
p
, and the sequence 1
,
p
+
1
, . . . , (
p
−
1
)
p
+
1 shows that it
is also a lower bound.