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.
  

• 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.