5 and 7

1. Sep 12, 2007

mathslover

guys,

From the solutions of the Pell's equation x*x-2*y*y=-1,
how can we prove that whenever y ends in digit 5, then 7 | x ?

-Mathslover

Perhaps I should clarify a bit,x*x-2*y*y=-1 has solution
x=1, 7, 41, 239, 1393, 8119, 47321, 275807,.....
y=1, 5, 29, 169, 985, 5741, 33461, 167305,...
and the general solution is (xn+yn*sqrt(2))=(1+sqrt(2))^(2*n+1)
Apart from induction,how can we prove whenever 5|y then 7|x ?

Last edited: Sep 13, 2007
2. Sep 12, 2007

bel

3. Sep 12, 2007

CRGreathouse

For y = 15 there are no solutions, since sqrt(449) isn't an integer... right?

4. Sep 12, 2007

D H

Staff Emeritus
The first solution pair (x,y) is (1,1). Develop a recursive relationship for the nth such pair (xn, yn) in terms of previous pair(s). The relation you want to prove will fall right out.

5. Sep 13, 2007

Kummer

Do you the general solution to this Pellian equation? I think that is the way to approach this problem. Followed by induction.

6. Sep 20, 2007

ramsey2879

$$(1 +\sqrt{2})^n$$ gives $$X_{n}\sqrt{2} + Y_{n}$$ where $$X_{n}$$ and $$Y_{n}$$ for odd $$n$$ are solutions.

thus the first 3 solutions pairs X,Y are
1,1
5,7
29,41

from this one might notice that 5 = 3*1+2*1 and 29 = 3*5+2*7 and also notice that
7 = 4*1 + 3*1 and that 41=4*5+3*7.
Or simply multiply $$(X\sqrt{2} + Y)*(1+\sqrt{2})^2$$ and put back into the same X,Y form to find the new X and Y.

So prove that if X and Y are a solution pair then (3X+2Y) and (4X+3Y) are the next solution pair then consider X mod 5 and Y mod 7 and you can follow the rest by induction.

7. Sep 21, 2007

ramsey2879

Since $$(1+\sqrt{2})^2 = 3+2\sqrt{2}$$ and since $$(1+\sqrt{2})^3 = 7+5\sqrt{2}$$ then
$$X_{n} = 0 \mod 5$$ implies that $$n = 0 \mod 3$$
but $$X_{n}$$ is only a solution for odd n so we calculate $$(1 + \sqrt{2})^6 = 99 + 70\sqrt{2}$$ so the next solution after n = 3 (x=5, y = 7) is
$$X_{n+6} = 70*Y_{n} + 99*X_{n} \| Y_{n+6} = 70*2*X_{n} + 99*Y_{n}$$
From inspection of the above formula it can be seen that
$$X_{n} = 0 \mod 5$$ if and only if $$X_{n+6} = 0 \mod 5$$ and
$$Y_{n}=0 \mod 7$$ if and only if $$Y_{n+6} = 0 \mod 7$$
So our proof is complete