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.