IMO 1999 SL N4

Origin: FRA | Category: Number Theory

Problem

Denote by S the set of all primes p such that the decimal representation of 1/p has its fundamental period divisible by 3. For every p \inS such that 1/p has its fundamental period 3r one may write 1/p = 0.a1a2 . . . a3ra1a2 . . . a3r . . . , where r = r(p); for every p \inS and every integer k \geq1 define f(k, p) by f(k, p) = ak + ak+r(p) + ak+2r(p). (a) Prove that S is infinite. (b) Find the highest value of f(k, p) for k \geq1 and p \inS.

Solution

(a) The fundamental period of p is the smallest integer d(p) such that p | 10d(p) −1. Let s be an arbitrary prime and set Ns = 102s + 10s + 1. In that case Ns \equiv3 (mod 9). Let ps ̸= 37 be a prime dividing Ns/3. Clearly ps ̸= 3. We claim that such a prime exists and that 3 | d(ps). The prime ps exists, since otherwise Ns could be written in the form Ns = 3 \cdot 37k \equiv 3 (mod 4), while on the other hand for s > 1 we have Ns \equiv1 (mod 4). Now we prove 3 | d(ps). We have ps | Ns | 103s−1 and hence d(ps) | 3s. We cannot have d(ps) | s, for otherwise ps | 10s −1 ⇒ps | (102s + 10s + 1, 10s −1) = 3; and we cannot have d(ps) | 3, for otherwise ps | 103 −1 = 999 = 33 \cdot 37, both of which contradict ps ̸= 3, 37. It follows that d(ps) = 3s. Hence for every prime s there exists a prime ps such that d(ps) = 3s. It follows that the cardinality of S is infinite. (b) Let r = r(s) be the fundamental period of p \inS. Then p | 103r −1, p ∤10r −1 ⇒p | 102r + 10r + 1. Let xj = 10j−1 p and yj = {xj} = 0.ajaj+1aj+2 . . . . Then aj < 10yj, and hence f(k, p) = ak + ak+r + ak+2r < 10(yk + yk+r + yk+2r) . We note that xk + xk+s(p) + xk+2s(p) = 10k−1Np p is an integer, from which it follows that yk + yk+s(p) + yk+2s(p) \inN. Hence yk + yk+s(p) + yk+2s(p) \leq2. It follows that f(k, p) < 20. We note that f(2, 7) = 4 + 8 + 7 = 19. Hence 19 is the greatest possible value of f(k, p).