91. Two squares or not two squares | TWOSQRS

simple one, after you get to know about the Fermat’s Theorem…. and also if n = 4*k + 3, it can never be a sum of two squares.

even^2 + even^2 = 4*k

odd^2 + even^2 = 4*k + 1

odd^2 + odd^2 = 4*k + 2

Fermat’s Theorem: A number n is a sum of two squares if and only if all prime factors of n of the form 4m+3 have even exponent in the prime fatorization of n.

https://gist.github.com/f60255f89c7aed4c1262

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s