0
$\begingroup$

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.

1 Answers 1

4

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$.

  • 0
    thank you very much for your explanation of what is being asked, it makes more sense to me now, and thank you for the hints too. i will look more into it and tell you what i have later.2012-10-02
  • 0
    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?2012-10-04
  • 0
    @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$.2012-10-05
  • 0
    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?2012-10-05
  • 0
    @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.2012-10-05
  • 0
    So I am guessing here what you mean by two-digit starting point is two-digit based p? For instance $7 \equiv 12 \pmod 5$ as two-digit starting point?2012-10-05
  • 0
    @finial: Yes, I meant base $p$. But not $1x$, since you don’t want that leading $1$.2012-10-05
  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/6037/discussion-between-finial-and-brian-m-scott)2012-10-05