Fermat Theorem: Number Theory

Any number which is a perfect square gives remainder either 0 or 1, when divided by 4. Even numbers would give 0 remainder and odd would give remainder as 1.

  Proof:

  Even number can be represented as : 2*n. 

  Square of even number = (2n)^2 = 4n^2 

  4n^2 mod 4 = 0

  Odd number can be represented as 2*n + 1.

  Square of odd number = (2*n+1)^2 = 4n^2 + 1 + 4n

  Mod with 4 gives 1.

Representing a number with Sum of squares of two numbers

If m,n are expressible as a sum of two squares, then so is m*n.

  Proof:

  Let m = x^2 + y^2

  Let n = z^2 + w^2

  m*n = (x^2 + y^2) * (z^2 + w^2)

  m*n = (xz)^2 + (xw)^2 + (yz)^2 + (yw)^2

  // adding and subtracting 2wxyz gives,

  m*n = (xz + yw)^2 + (xw - yz)^2

  Hence, proved.

If n = 3(mod 4), then it cannot be expressed as a sum of two squares.

  As we have seen above, 
  an even perfect square = 0(mod 4);
  a odd perfect square = 1(mod 4);
  and if a = r1(mod 4) and b = r2(mod 4), then a + b = (r1 + r2)(mod 4)

  To express a number c as a^2 + b^2, (sum of two squares), there are four possibilities:

  Case 1: {c is even}
  Both a^2 and b^2 are even
  Here, c = 0(mod 4)

  Case 2: {c is even}
  Both a^2 and b^2 are odd
  Here, c = 2(mod 4)

  Case 3: {c is odd}
  One is even and other odd
  Here, c = 1(mod 4)

  Thus, we never see 3 as an remainder.

🔥

Thus, any number of the form 4m + 3 cannot be represented as a sum of two squares.

Any prime of the form 4m + 1 or p = 1(mod 4) can be represented as sum of two squares.
Lemma: For a prime p = 1(mod 4), there exists a x that belongs to Z(integer number), such that p divides (x^2 + 1) or x^2 + 1 = kp for k in range (0,p].

💡

Quadratic Residue: c is called a quadratic residue mod p if x^2 = c(mod p), c ranging from 1 to p-1 for any integer x. We do not consider 0 as quadratuc residue.
```
  We know that if an odd prime p ≡ 1 (mod 4), 
  then -1 is a quadratic residue modulo p 
  (i.e., there exists an integer x such that x^2 ≡ -1 (mod p)).
  {-1 means p-1 is remainder}
```
Wilson's theorem:

If p is prime, then (p-1)!/p = -1(mod p), i.e. (p-1)! on division by p gives remainder p-1.
Fermat's Little Theorem:

If p is a prime number and a is an integer with no common factors with p (a is not divisible by p, gcd(p,a) = 1), then a^(p-1) = 1 (mod p).
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 factorization of n.
No three positive integers x, y, z satisfy x^n + y^n = z^n for n > 2.