Quadratic Residues

Quadratic residue mod p: If congruence x² ≡ n (mod p) has no solution, then n is quadratic nonresidue mod p denoted by (nR̅p).

Jacobi symbol: If P is a positive odd integer with prime factorization
                                P = ∏p_i^ai, i = 1, 2, ... , r.
              Then Jacobi symbol (n/P) for all integer is 
                             (n/P) = ∏p_i^ai, i = 1, 2, ... , r
             where (n/p_i) is Legendre symbol and (n/1) = 1.

Reduced residue system modulo m: It is a set of ∅(m) integers, incongruent modulo m, each of which is relatively prime to m.
          Here ∅(m) is Euler's totient.

• Chinese remainder theorem: Assume m₁, m₂, … , m_r arepositive integers, relatively prime in pairs : (m_i , m_k) = 1 if i ≠ k.

         Let b₁, b₂, … , b_r be arbitrary integers. Then the system of congruences

                          x ≡ b₁ (mod m₁)

                          .

                          .

                          .

                         x ≡ b_r (mod m_r)

         has exactly one solution modulo the product m₁, m₂, … , m_r .

• Assume m₁, m₂, … , m_r are relatively prime in pairs. Let b₁, b₂, … , b_r be arbitrary integers and let a₁, a₂, … , a_r  satisfy (a_k , m_k) = 1 for k = 1, 2, ... , r. Then the linear system of congruences

                       a₁x ≡ b₁ (mod m₁)

                        .

                        .

                        .

                      a_rx ≡ b_r (mod m_r)

        has exactly one solution modulo m₁, m₂, … , m_r .

• Let f be a polynomial with integer coefficients, let m₁, m₂, … , m_r be positive integers relatively prime in pairs and let m =  m₁ m₂ …  m_r. Then the congruence

                    f(x) ≡ 0 (mod m)                                                   ... (i)

         has a solution iff each of the congruences,                                              f(x) ≡ 0 (mod m_i), i = 1, 2, ... , r                          ... (ii)

         has a solution. Moreovere if v(m) and v(m_i) denote the number of solutions of (i) and (ii) respectively, then                                  v(m) = v(m₁) v(m₂) ... v(m_r).

• The set of lattice points in the plane visible from the origin contains arbitrarily large square gaps. That is, given any integer k > 0, there exist a lattice point (a, b) such that none of the lattice point,                                                        (a + r, b + s), 0 < r ≤ k, 0 < s ≤ k

          is visible from the origin.