Problem 11864
(American Mathematical Monthly, Vol.122, October 2015) Proposed by Bakir Farhi (Algeria).
Letp be a prime number, and let {un}n≥0 be the sequence given byun = n for 0 ≤ n ≤ p − 1 and byun = pun+1−p+ un−pforn ≥ p. Prove that for each positive integer n, the greatest power of p dividingun is the same as the greatest power ofp dividing n.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
Let νp(n) be the greatest power of p dividing a positive integer n.
We will show a more general statement: if s = νp(n) then un≡ n (mod ps+1).
From the generating function of the sequence {un}n≥0 we obtain
un = [xn]
Pp−1 k=1kxk 1 − (pxp−1+ xp)=
p−1
X
k=1
k[xn−k]X
j≥0
(pxp−1+ xp)j
=
p−1
X
k=1
kX
j≥0
[xn−k−pj](1 + p/x)j=
p−1
X
k=1
kX
j≥0
j
pj + k − n
ppj+k−n.
If n = qp + r with 1 ≤ r ≤ p − 1 then pj + k − n = 0 iff j = q and k = r, hence un≡ r ≡ n (mod p).
If n = aps with s ≥ 1 and gcd(a, p) = 1 then pj + k − n ≥ 0 iff j ≥ ⌈(n − k)/p⌉ = aps−1 and, by letting i = j − aps−1, we have
un=
p−1
X
k=1
kX
i≥0
aps−1+ i pi + k
ppi+k.
Then, for i ≥ 1 and 1 ≤ k ≤ p − 1,
νp((pi + k)!) = νp((pi)!) = i + νp(i!) ≤ i + ν2(i!) = i +
⌊ln2(i)⌋
X
j=1
⌊i/2j⌋ < i +
∞
X
j=1
i/2j= 2i,
which implies that νp((pi + k)!) ≤ 2i − 1. Hence
νp
kaps−1+ i pi + k
ppi+k
≥ νp(aps−1) − νp((pi + k)!) + pi + k ≥ (s − 1) − (2i − 1) + pi + 1 = s + 1
where in the last step we used the fact that p ≥ 2. Finally
un≡
p−1
X
k=1
kaps−1 k
pk = aps−1
p−1
X
k=1
aps−1− 1 k − 1
pk≡ aps= n (mod ps+1).
