Problems & Puzzles: Puzzles

Puzzle 153.  Espinosa's puzzle

José Espinosa, from Santiago de Chile, posed the following problem

• Let p be a prime number greater than 3 and q a prime number.
• Let g(n)=2^(2+n(p-1))+3^(3+n(p-1))+5^(5+n(p-1))+7^(7+n(p-1))+...+ q^(q+n(p-1))
• Let f(n)=48g(n)-(n-5)(n-7)g(13)+4(n-5)(n-13)g(7)-3(n-7)(n-13)g(5)

Prove that for every integer non-negative n: f(n) is divisible by p^3.

He also sent to me a hint that I will provide to those of you who need it.

But maybe can help enough to know that Mr. Espinosa currently maintains a math site devoted to the mathematical induction.

Jan van Delden wrote:

Focus on the effect f has on one term of g:

Consider one term t(n,r)=r^(r+n*(p-1))
And h(n,r):=48*t(n,r)-(n-5)(n-7)t(13,r)+4(n-5)(n-13)t(7,r)-3(n-7)(n-13)t(5,r)

We then have g(n)= t(n,2)+t(n,3)+t(n,5)..+t(n,q), and f(n)=h(n,2)+h(n,3)+h(n,5)+..h(n,q).

If we can prove that for every prime r: h(n,r)=0 mod p^3 we're done.

As suggested we use induction on n.

n=0:

h(0,r)=r^r [48-(n-5)(n-7) r^(13(p-1))+4(n-5)(n-13)r^(7(p-1))-3(n-7)(n-13)r^(5(p-1))]

r^(p-1)=1 mod p if (r,p)=1 i.e. we can write r^(p-1)=Ap+1, for some A integer if (r,p)=1.

h(0,r)=r^r [48-(n-5)(n-7)(Ap+1)^13+4(n-5)(n-13)(Ap+1)^7-3(n-7)(n-13)(Ap+1)^5]

It is now straightforward to show (use binomal of Newton, a bit awkward) that the terms between the brackets corresponding to p^0,p^1 and p^2 are 0, so
h(0,r)=0 mod p^3.

If (r,p)>1 and because r,p are prime we have r=p. We then have:

h(0,r) = h(0,p)= p^p [48 + extra terms each at least=0 mod p^(5(p-1)].

So h(0,r)=0 mod p^3, if p>=3.

[Actually 48=2^4*3. With p=3: p^(5(p-1))=0 mod p^10 and with p=2: p^(5(p-1))=0 mod p^5, so h(0,3)=0 mod 3^4 and h(0,2)=0 mod 2^6]

n+1: Induction step

h(n+1,r)-h(n,r) = 48 [t(n+1,r)-t(n,r)]+(11-2n)t(13,r)+4(2n-17)t(7,r)+3(19-2n)t(5,r)

= r^r {48 r^(n*(p-1)) [r^(p-1)-1] + (11-2n) r^(13(p-1))+4(2n-17)r^(7(p-1))+3(19-2n)r^(5(p-1))}

If (r,p)=1, we proceed as before and find that h(n+1,r)-h(n,r)=0 mod p^3.
If (r,p)=p we see that the term p (or r if you will) is even more abundant as a factor compared with the h(0,r) case! [Also for p=2 or p=3]

Assuming h(n,r)=0 mod p^3, using the above we have h(n+1,r)=0 mod p^3.

Hence

h(n,r)=0 mod p^3 with p>=2.
 

***