a+b=0 mod n and a^2+b^2=0 mod n^2 So, a=-b mod n and 2ab=0 mod n^2 Suppose that n is divisible by 2^k, but not divisible by 2^{k+1}. Let’s |a|_2=t, where t is less than k. Then, since a=-b mod 2^k, |b|_2=t. So, |2ab|_2=2t+1. It means that 2t+1>=2k, thus t>=k and ab is divisible by n^2. If a is divisible by 2^k, then b is divisible by 2^k and ab is divisible by n^2. In both cases we got that ab is divisible by n^2. Let’s prove by induction problem’s statement Base: m=1,2 it’s true by condition Step: m-1,m->m+1 a^{m+1}+b^{m+1}=(a+b)(a^m+b^m)-ab(a^{m-1}+b^{m-1}) By induction’s assumption and condition (a+b)(a^m+b^m) is divisible by n^{m+1} By induction’s assumption and reasoning above ab(a^{m-1}+b^{m-1}) is divisible by n^{m+1} Therefore, a^{m+1}+b^{m+1} is divisible by n^{m+1}. Step is proven.