Divisibility 3

For discussing Olympiad Level Number Theory problems
yo79
Posts:53
Joined:Mon Feb 04, 2013 1:01 am
Divisibility 3

Unread post by yo79 » Mon Feb 25, 2013 11:21 pm

Let x,y be two nonnegative integers with $x^2+y^2=n^2y^2+1$, where n is a natural number, n>1. Prove that n|xy.

User avatar
Fm Jakaria
Posts:79
Joined:Thu Feb 28, 2013 11:49 pm

Re: Divisibility 3

Unread post by Fm Jakaria » Sun Nov 02, 2014 6:14 pm

We are done if $xy = 0$. So let $x,y$ be positive integers.

Rewrite as
$x^2 – (n^2 – 1)y^2 = 1….(i)$, where $d = (n^2 – 1) $ is a nonsquare positive integer.
We now know from the theory of pell’s equations that
(i) has a nontrivial solution (x,y) in positive integers. Let $x_0 + y_0\sqrt{d}$ be the minimal solution.

For $i \geqslant 0$, define $(x_{i+1} , y_{i+1}) = ({x_i}{x_0} + d{y_i}{y_0}, {x_i}{y_0} + {y_i}{x_0})$.
Then $(x_i,y_i) $are precisely all the nontrivial positive integer solutions $ (x,y) $
to $(i) $.

Note that,
$x_{i+1}y_{i+1} = x_0y_0(x_i^2 + dy_i^2) + x_iy_i(x_0^2 + dy_0^2) $.
This actually concludes an inductive proof of the problem statement if we proof it is true for $(x,y) = (x_0, y_0) $
.

Simply note that ${x_i}$ and ${y_i}$ are both strictly increasing sequence of positive integers. Our final fact is
$ (x,y) = (n,1) $ is a solution of $ (i) $. This implies $ (x_0, y_0) = (n,1) $. Obviously $n$ divides $x_0y_0 = n$.
You cannot say if I fail to recite-
the umpteenth digit of PI,
Whether I'll live - or
whether I may, drown in tub and die.

Post Reply