# Showing $64$ divides $5^n-8n^2+4n-1$ without induction

I want to show that for all positive integer values of $$n$$, the number $$5^n-8n^2+4n-1$$ is divisible by $$64$$. Of course, I can easily do it by induction, but are there any number theoretic ways I can utilise to prove the divisibility?

Thanks in advance for any help.

• n=1 is a counterexample. Is that the right equation? – user458276 Feb 27 '19 at 5:39
• No. For n=1, the number is exactly equal to 0, and 0 is divisible by 64. – See Hai Feb 27 '19 at 5:41

## 3 Answers

It seems to me that the simplest way is to use the binomial expansion \begin{aligned} 5^n&=(4+1)^n=1+\binom n 1 4+\binom n2 4^2+\text{terms divisible by 4^3}\\ &\equiv 1+4n+8n(n-1)\pmod{64}\\ &=1-4n+8n^2. \end{aligned}

• Oh, that is indeed something I did not think of! It is pretty nice. Thanks for your help. – See Hai Feb 27 '19 at 6:01
• Does the above imply there is some recent change on your position about answering (dupe) FAQs? – Bill Dubuque Mar 11 '19 at 16:48

Write $$a_n=5^n-8n^2+4n-1 = 5^n+(-8n^2+4n-1)1^n$$.

Then $$a_n$$ satisfies a linear recurrence implied by $$(x-5)(x-1)^3$$: $$a_{n+4} = 8a_{n+3}- 18a_{n+2} + 16a_{n+1} - 5a_{n}$$

The particular expression for the recurrence is not important, except that it has integer coefficients.

Bottom line: It suffices to prove that $$64$$ divides $$a_n$$ for $$n=0,1,2,3$$. This is immediate because $$a_0=a_1=a_2=0$$ and $$a_3=64$$.

• Well, this is a proof by induction, but not the expected one, I guess. – lhf Feb 27 '19 at 12:18
• A nice piece of reverse engineering :-) – Jyrki Lahtonen Feb 27 '19 at 15:30

Just try them all. We know $$5^{32} \equiv 1 \pmod {64}$$ so if you check $$[0,63]$$ you are done.

• Hmm, I thought of that too, but isn't this extremely tedious? – See Hai Feb 27 '19 at 5:50
• I'm not sure what is the significance of Euler's theorem $5^{32}\equiv 1 \pmod {64}$ in this situation, but in fact $5^{16}\equiv 1 \pmod {64}$ – J. W. Tanner Feb 27 '19 at 5:54
• A spreadsheet is your friend. Use the fill command to make a column with the numbers from $0$ to $63$. Write the equation and copy down. Less than a minute. – Ross Millikan Feb 27 '19 at 5:56
• @J.W.Tanner: It justifies that we only need to look at numbers in the range $[0,63]$ because the exponent divides $64$.. – Ross Millikan Feb 27 '19 at 5:57
• I get it now, @RossMillikan. Thank you for explaining – J. W. Tanner Feb 27 '19 at 5:58