You are getting overflow. An int is 32 bits. The random value picked for a is greater than 16 bits, so its square is greater than 32 bits. An int is also signed, so if you overflow a positive number, the left hand bit might be set and if it is, the number will be negative. That's what is happening here.
You need to constrain a to be less than 65536, ie 2^16.