# Let $p \ge 5$ be a prime number. Find the largest length of an arithmetic progression satisfying the following

Let $p \ge 5$ be a prime number. Find the largest length of an arithmetic progression, of positive ratio, of positive integers whose terms do not contain the digit $1$ in their p-adic expansion.

I suspect that ratio should be read as difference. If so, you’re being asked to determine the greatest possible length of a strictly increasing arithmetic sequence of positive integers, whose base $p$ representations do not contain the digit $1$. In base five, for instance, if you start out with $2,4$, you’re blocked, because $6=11_{\text{five}}$. If you start at $12=22_{\text{five}}$ with a common difference of $3$ you can do a little better: $22_{\text{five}},30_{\text{five}},33_{\text{five}}$. But the next number in the sequence is $41_{\text{five}}$, so you’re blocked again. And be starting at $14=24_{\text{five}}$, I can do better yet: $24_{\text{five}},32_{\text{five}},40_{\text{five}},43_{\text{five}}$. (I’ll leave it to you to verify that I’m blocked again.)
HINT: Look at the $1$’s digit, the least significant digit. Say that your sequence is $a,a+d,a+2d$, $a+3d$, and so on. If $b\ne 0$ is the $1$’s digit of $d$, what can you say about the numbers $d,2d,3d,\dots,pd$ modulo $p$? And you don’t have to worry about a difference $d$ that ends in $0$: the $1$’s digit remains constant throughout your sequence, and you might as well just throw it away. E.g., instead of looking at $242_{\text{five}},322_{\text{five}},402_{\text{five}},432_{\text{five}}$, with difference $d=30_{\text{five}}$, look at $24_{\text{five}},32_{\text{five}},40_{\text{five}},43_{\text{five}}$, with difference $d=3$.
• So I think I am aiming to find the largest possible n such that: $a+nd \equiv 1 \pmod p$ while it's clear that $pd \equiv 0 \pmod p$ Therefore I am guessing now the progression must somehow be blocked before the term $a+pd$ and so $p-1$ might be the largest $n$ that gets blocked? – fmat Oct 4 '12 at 23:53
• @finial: Yes, with a bit of work you should be able to show that you can’t get $p$ terms, but you can always get $p-1$. – Brian M. Scott Oct 5 '12 at 2:41
• So I proved (hopefully not faultly) that since $a+pd \equiv a \pmod p$ and $a+nd \neq a+md \pmod p$ for any $n,m \lt p, n\gt m$, we have that the first digit of each term mod p has to be different. Therefore can't get p terms, but the hard part to show that we can always have $p-1$ terms is that I realized we not only have to take care of the first digit, but EVERGY DIGIT, because once we contain 1 in any digit of the term, we are out. Any more suggestion? – fmat Oct 5 '12 at 5:05
• @finial: Use $d=1$ and a two-digit starting point just large enough to ensure that you don’t run into a $1$ before the $p$-th term. – Brian M. Scott Oct 5 '12 at 5:12