Congruences

Concepts

• Modular congruence from Discrete mathematics 10 exercisesTwo integers a and b are congruent modulo a positive integer m if m divides their difference; equivalently, they leave the same r…
• Complete residue system 10 exercisesA complete residue system modulo m is a set of m integers that contains exactly one representative from each congruence class mod…
• Modular inverse 10 exercisesThe modular inverse of an integer a modulo m is an integer b whose product with a is congruent to 1 modulo m.
• Linear congruence 10 exercisesA linear congruence is a first-degree congruence in one unknown x, with integer coefficients a, b and modulus m; its solutions ar…
• Chinese remainder theorem 10 exercisesThe Chinese remainder theorem states that a system of linear congruences with pairwise coprime moduli has a unique solution modul…
• Fermat's little theorem 10 exercisesFermat's little theorem states that if p is a prime number and a is an integer not divisible by p, then a^p-1≡ 1 pmodp. It is a b…
• Euler's totient function 10 exercisesEuler's totient function φ assigns to each positive integer n the number of integers between 1 and n that are coprime to n.
• Euler's theorem 10 exercisesEuler's theorem states that if a and n are coprime, then a^φ(n) ≡ 1 pmodn, generalizing Fermat's little theorem to composite modu…
• Wilson's theorem 10 exercisesFor a prime number p, (p-1)! leaves remainder -1 when divided by p.