# Proof Explanation - Odd prime division

Prove that if $$p$$ is an odd prime, then $$p\mid \lfloor(2+\sqrt5)^p\rfloor - 2^{p+1}$$

The solution posted by another user is as follows:

Let $$𝑁=(2+\sqrt5)^p + (2-\sqrt5)^𝑝$$. Note that $$N$$ is an integer. There are various ways to see this. One can, for example, expand using the binomial theorem, and observe that the terms involving odd powers of $$\sqrt5$$ cancel.

Because $$(2−\sqrt5)^𝑝$$ is a negative number close to $$0$$, it follows that $$𝑁=⌊(2+\sqrt5)^𝑝⌋$$.

In the two binomial expansions, all the binomial coefficients $$\binom{p}{k}$$ apart from the first and last are divisible by $$p$$. The first term in each expansion is $$2^p$$. We conclude that $$N\equiv 2\cdot 2^p\pmod{p}$$, and the result follows.

Could someone explain this proof in more detail please? I don't understand the following:

1) How the odd powers of $$\sqrt5$$ cancel,

2) How $$N=\lfloor(2+\sqrt5)^p\rfloor$$ (I understand that $$(2-\sqrt5)^p$$ is negative),

3) How $$N\equiv 2\cdot 2^p\pmod{p}$$, and the result follows.

How would one go about generalising to a result about $$p^n$$?

Thanks

• could you provide the link to the older question? – Dr. Mathva Feb 12 '19 at 14:00
• $1)$: $\binom{p}{j}2^{(p-j)}(\sqrt{5}^j)+\binom{p}{j}2^{(p-j)}(-\sqrt{5})^j=0$ for odd $j$ – Peter Melech Feb 12 '19 at 14:05
• math.stackexchange.com/questions/1666207/… – user437703 Feb 12 '19 at 14:09
• More generally see PV (Pisot–Vijayaraghavan) numbers. – Bill Dubuque Feb 12 '19 at 15:17
• I'd calculate by hand the numbers $(2 \pm \sqrt 5)^p$ for small odd primes up to maybe $p = 29$. A pattern would probably emerge. – Robert Soupe Feb 13 '19 at 3:31

## 2 Answers

1) We have
$$(2+\sqrt 5)^p=2^p+\binom p12^{p-1}\sqrt 5+\binom p22^{p-2}\sqrt 5^2+\binom p23^{p-3}\sqrt 5^3+...+\binom pp\sqrt 5^p$$, and $$(2-\sqrt 5)^p=2^p-\binom p12^{p-1}\sqrt 5+\binom p22^{p-2}\sqrt 5^2-\binom p23^{p-3}\sqrt 5^3+...-\binom pp\sqrt 5^p$$. When you add these together, all the odd terms are equal and opposite, so you get $$N=2\times2^p+2\times\binom p22^{p-2}\sqrt 5^2+...+2\times\binom p{p-1}2\sqrt 5^{p-1}$$.
Since this only has even powers of $$\sqrt 5$$, it is an integer.

2) As well as being an integer, $$N$$ is slightly less than $$(2+\sqrt 5)^p$$. In fact it is $$-(2-\sqrt 5)^p=(\sqrt 5-2)^p$$ less. Since $$0<(\sqrt 5-2)^p<1$$, $$N$$ is the integer between $$(2+\sqrt 5)^p$$ and $$(2+\sqrt 5)^p-1$$, i.e. it is $$\lfloor(2+\sqrt 5)^p\rfloor$$.

3) Going back to $$N=2\times2^p+2\times\binom p22^{p-2}\sqrt 5^2+...+2\times\binom p{p-1}2\sqrt 5^{p-1}$$, each term except the first has a factor of $$\binom pr$$ for some $$0. Writing this in factorial form, it is $$\frac{p!}{r!(p-r)!}$$. Since $$p$$ is prime, $$p$$ divides the top but not the bottom. This means every term except the first is a multiple of $$p$$, so $$N\equiv 2\times2^p$$ mod $$p$$.

• Thanks for the reply. How would you go about generalising for $p^n$? My initial idea would be to use induction. – user437703 Feb 14 '19 at 17:27

For 1), the sum of odd powers $$a^n + b^n$$ can be factored into $$(a+b)(a^{n-1}-a^{n-2}b+a^{n-3}b^2..........+b^{n-1})$$ so where binomials $$a$$ and $$b$$ contain the same negative and positive irrational, these two factors will always be integers as positive and negative quantities of the irrational will be equal.

Example: $$(2+\sqrt 5)^3 + (2 - \sqrt 5)^3 = (2+\sqrt 5+2 - \sqrt 5)((4 + 4\sqrt 5 + 5) - (4 - 5) + (4 - 4\sqrt 5 + 5)) = 4(19) = 76$$