For your equation $x^2+y^2=z^2$, $A$ can have $N/2$ numbers. For example, take all odd numbers $\le N$. This set does not have any solutions of your (Pythagorean) equation. For the new (Pell) equation, the set of even numbers will do the trick.
2 of 2
added 72 characters in body
user6976