Modular arithmetic

Divisibility: Understanding divisibility tests and the concept of factors and multiples.

Euclid’s Algorithm: A quick and efficient way to find the greatest common divisor of two integers.

Congruence: An equivalence relation on integers that describes when two numbers have the same remainder when divided by another number.

Modular Arithmetic Operations: Familiarity with addition, subtraction, multiplication, and division in modular arithmetic.

Solving Equations and Inequalities: Learning how to solve modular arithmetic equations and inequalities systematically.

Application of Modular Arithmetic: Use of modular arithmetic in Cryptography, Computing, and other essential areas.

Chinese Remainder Theorem: A tool used for finding the solution of a system of congruences.

Primitive Roots: Understanding how and when to find primitive roots of a number.

Euler’s Totient Function: An important function used in solving some problems in number theory.

Fermat's Little Theorem: An important theorem used in finding the remainder when a number is raised to a power.

Wilson's Theorem: A theorem used to test if an integer is prime.

Quadratic Residues: A mathematical concept that describes whether or not an integer is a quadratic residue modulo a given prime.

Arithmetic Functions: An overview of Various arithmetic functions such as factors, divisors, and totients.

Number Theory in Cryptography: Applications of modular arithmetic in Cryptography and Cryptanalysis.

Related Fields: Familiarity with fields closely related to modular arithmetic, such as group theory and ring theory.

Modulo: The remainder obtained after division of two numbers is called modulo. For example, in 11 modulo 3, when 11 is divided by 3, the remainder is 2.

Clock arithmetic: Clock arithmetic is a type of modular arithmetic in which the integers are taken modulo 12. It is used to represent time, with 12 representing the hour after which it starts over.

Residue class: Under modulo n, the numbers 0, 1, 2, ..., n-1 make up a residue class. For example, under modulo 5, the residue class is {0, 1, 2, 3, 4}.

Congruence: A congruence is a relationship between two numbers that are equal modulo n. For example, 5 and 11 are congruent modulo 3, as they both have a remainder of 2 when divided by 3.

Linear congruence: A linear congruence is an equation of the form ax ≡ b (mod n), where a, b, and n are integers, and x is the unknown variable.

Chinese remainder theorem: The Chinese remainder theorem is a theorem that says that if you have a system of linear congruences of the form x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), ..., x ≡ aᵢ (mod nᵢ), where n₁, n₂, ..., nᵢ are pairwise relatively prime integers, then there is a unique solution modulo N = n₁n₂...nᵢ.

Primitive root: A primitive root modulo n is a number that generates all the residue classes under modulo n. For example, 2 is a primitive root modulo 7, as it generates the residue classes {1, 2, 4, 3, 6, 5}.

Euler's totient function: Euler's totient function φ(n) counts the number of positive integers less than n that are relatively prime to n. For example, φ(10) = 4, as there are four positive integers less than 10 that are relatively prime to 10: 1, 3, 7, and 9.

Fermat's little theorem: Fermat's little theorem states that if p is a prime number and a is an integer that is not divisible by p, then a^(p-1) ≡ 1 (mod p).

Wilson's theorem: Wilson's theorem states that if p is a prime number, then (p-1)! ≡ -1 (mod p).