9
$\begingroup$

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.

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

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

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

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

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

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

$\endgroup$
6
  • 1
    $\begingroup$ Hmm, I thought of that too, but isn't this extremely tedious? $\endgroup$ – See Hai Feb 27 '19 at 5:50
  • $\begingroup$ 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}$ $\endgroup$ – J. W. Tanner Feb 27 '19 at 5:54
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Feb 27 '19 at 5:56
  • $\begingroup$ @J.W.Tanner: It justifies that we only need to look at numbers in the range $[0,63]$ because the exponent divides $64$.. $\endgroup$ – Ross Millikan Feb 27 '19 at 5:57
  • $\begingroup$ I get it now, @RossMillikan. Thank you for explaining $\endgroup$ – J. W. Tanner Feb 27 '19 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.