I think the second problem is wrong. for example when x = y = 3 and n = 9
1. Then x=qk+r for some integer k. Then x^n = (qk+r)^n. Expand it. 19^n+39^n=3^n+(-1)^n. Since phi(8)=4, you only need to check n up to 4.
2. Quadratic residues modulo 4 are only 0 and 1. So x^2-y^2 can only be 1,0,-1 modulo 4. While 2n=2 (mod 4) if n is odd. #