The equation x2 - My2 = 1, where M is an integer, is called Pell's equation.
Equation: x2 - y2 = 1
If M ≤ -2, the only solutions are (±1, 0), because -My2 > 1 for all y ≠ 0 and M ≤ -2. For M = -1 the equation becomes x2 + y2 = 1 which has solutions (±1, 0) and (0, ±1).
If M is a square, then M = r2 for some r &in &integers and the equation factors as (x - ry)(x + ry) = 1. For any solution, both terms in the product are units in the integers, so the only possibilities are x - ry = x + ry = 1 or x - ry = x + ry = -1. Adding the equations (x - ry) + (x + ry) = &pm1 + &pm1 yields 2x = &pm2. Thus (x, y) = (&pm1, 0) are the only solutions.
This case is slightly complicated. In this case there is always a nontrivial solution. The smallest non trivial solution can be found by brute force and all other solutions are generated by it. See chapter 20 of Dudley, Elementary Number Theory (book online) for details.