Question related to Pell's Equation

[gonzo]

For $\alpha$ and $\beta$ odd integers and X,Y integers, we have the following (by collecting terms):

$$(\alpha + \beta \sqrt{5})^n = x + y \sqrt{5}$$

My question is how do we know that x and y are both divisible by exactly $2^{n-1}$? (no more and no less 2's in each)

I can show this with integer ring theory, but I wanted a more concrete and direct way to show this.

I'm looking for some inherrent numerical property rather than a proof by induction, if there is one that is easy to understand.

Thanks.

 

[Hurkyl]

Well, when I look at it, the intuitive content is that $\alpha + \beta \sqrt{5}$ is divisible by 2 exactly once. ($(\alpha + \beta \sqrt{5}) / 2$ is an algebraic integer, if $\alpha, \beta$ are odd!) So if you raise it to the n-th power, you should get something divisible by 2 exactly n times.

Of course, I don't remember if $\mathbb{Z}[(1 + \sqrt{5})/2]$ is a UFD. Maybe bad things can happen when we raise to powers. So, let's try using norms to prove it!

$$N(\alpha + \beta \sqrt{5}) = \alpha^2 - 5 \beta^2 \equiv 4 \mod 8$$

In particular 2 divides the norm exactly twice. So, if we raise to the n-th power, we get:

$$x^2 - 5 y^2 = N(x + y \sqrt{5}) = N((\alpha + \beta \sqrt{5})^n) = N(\alpha + \beta \sqrt{5})^n \equiv 2^{2n} \mod{2^{2n + 1}}$$

In particular, $x^2 \equiv 5 y^2 \mod{2^{2n}}$. 5 isn't a perfect square modulo 2^k unless k < 3. This proves that $x^2 \equiv y^2 \equiv 0 \mod{2^{2n - 2}}$. Thus, 2 divides each of x and y at least n-1 times. A quick exhaust of the four possibilities proves that neither can be divisible by 2^n.

 

[gonzo]

Right, I could see it with integer ring theory (I'm also mostly concerned when $(\alpha + \beta \sqrt{5}) / 2$ is a unit, which means raising it to a power is still a unit and has the same form).

But I was looking for something inherent in the binomial expansion maybe, leavign out norms and rings.

 

[Hurkyl]

D'oh! I thought that was "inherent numerical property".

Okay, forget norms are involved, and pretend someone suggested "multiply by the conjugate". That's something you learned to try way back in calculus, or even before that! I would have considered $(\alpha - \beta \sqrt{5})^n$, even long before I knew anything about algebraic number theory. The only problem is that I would have first tried adding the conjugates (trace), rather than multiplying. (norm)

 

[gonzo]

I guess I'm looking for a lower level understanding of this result. You can think of it as confirming the results of using norms and units and such.

But maybe I'm looking for something that just isn't available? Happens sometimes.

 

[Hurkyl]

The way I see this example (and a great many other examples) is that the proof really is entirely elementary: norms and such simply gives you the idea.

Algebraic number theory told me that $(\alpha^2 - 5 \beta^2)^n = (x^2 - 5 y^2)^n$ might be a useful identity. Once I knew that, the proof was entirely elementary. If I wanted, I could even give an elementary proof of the identity: that $(\alpha - \beta \sqrt{5})^n = x - y \sqrt{5}$ is something I would have immediately known long before I knew anything about algebraic number theory... just from my experience with binomial expansions!

 

[robert Ihnot]

I have my own way of looking at this. Take the form a+b*, where for the sake of writing b* =bsqrt(5), and a, b odd. Then it is clear for the first term, a+b*, it is not divisible by 2, since it would have to divide both terms. The second term is (a^2+5b^2) + (2ab)*. Obviously the second term is divisible by 2^1.

Now the third term is interesting and the form is going to be:
a(a^2+15b^2)+b*(3a^2+5b^2). I look at this Mod 2^4, where a and b can only have the values 1 or 9. If they both have the same value, then a^2 +15b^2 is divisible by 16, but 3a^2+5b^2 is divisible by 8, and so in this case the third term is divisible by 2^3.

However if the terms are such that a==9 and b==1, then the first term inside the parenthesis is 24=8x3, and the second term equals 32, this causes the term with sqrt5 to now be even after division by 8, where as before it was the other way. Reversing the values a=1, b=9 produces 136=8*17 inside the parenthesis for the first term and the sqrt(5) term gives 48 = 3x16.

So that in above case, the general result is still true for the third term, it is divisiible by 2^3, but which term after this divison is even or odd changes from the first case where both terms are the same. (And in either case by employing Mod 16, we know that 8 is the highest term to divide it.)

So the cases so far is n=1, divisor is 2^0; n=2, divisor is 2^1; n=3, divisor is 2^3.

Since at n=3 the general form is (2^3)(2u+v*). In this case, I have chosen the first part to be even, but it does not matter. Then clearly multiplying: (2^3)(2u+v*)(a+b*) will give us one odd term and so there is no increase in powers of two for n=4.

But, in the case of n=5, we have (2^3)(2u+v*)(a+b*)^2, the last term in parenthesis is, as before, a^2+5b^2 +(2ab)*, this adds exactly one power of 2 so that n=5 gives division by 2^4.

Now in the case for n=6 we have 2^6(2u+v*)^2. In this case, examing the squared term, we will arrive at an odd term on sqrt5, therefor reversing the even odd situation, but supplying no change in the powers of 2, and not changing the situation for n=7 and n=8, from what happened with n=4 and n=5.

The only case now to consider for the induction is the case for a power of 3 where we have (2U+V*)(S+2T*), but this again will result in one term in the product, which is odd and so supplying no more powers of two, and not effecting the following two cases.

Thus we have the result on the powers of 2: If it is of the form 3N, then the highest power of 2 dividing is 2^(3N). In the case of 3N+1, the highest power is 2^3N, and in the case of 3N+2, the result is divisible by 2^(3N+l).

 

[robert Ihnot]

I think I have the ambiguity in this case figured out. According to my book, a quadratic integer where D is of the form 1+4k, which includes 5, is of this form: $$\frac{a+b\sqrt5}{2}$$ where a and b have the same parity.

So that in the case from the standpoint of a quadratic integer, we want the form for a, b, chosen odd and divided by 2 to be as the form in the above equation shows.

Now the problem occurs that when we have a case of 3N, we can divide all the powers of 2 out, but what is left lacks the same parity, so the correct form is: $$\frac{2m+2s\sqrt5}{2}$$

So from the standpoint of a QUADRATIC INTEGER we have a perfectly symmetric case, raising it to the Nth power allows us division by 2^N, with the stipulation that the final answer has a denominator of 2, and the terms show parity.

According to my book, the most general form without regard for parity is of the form
s+t(u), where $$u=\frac{1+\sqrt 5}{2}$$