Coprime integers

Two integers are coprime if their greatest common divisor is 1. They share no prime factor, though either integer may itself be composite.

Greatest common divisor: The greatest positive integer that divides each of two or more integers. Coprimality is defined by this value being 1.
Modular multiplicative inverse: An integer that multiplies a given residue to 1 modulo a specified modulus. An inverse modulo n exists exactly when the integer and n are coprime.
RSA: A public-key cryptosystem whose security relies on the difficulty of factoring a product of large primes. RSA chooses an exponent coprime to the totient of its modulus so decryption can invert it.
Relatively prime polynomials: Polynomials whose only common divisors are nonzero constants. This extends the no-common-factor idea from integers to polynomials.
Prime factorization: The expression of an integer greater than 1 as a product of primes. Two integers are coprime precisely when their prime factorizations have no prime in common.
Reduced fraction: A fraction whose numerator and denominator have greatest common divisor 1. Reducing a fraction removes common factors until its terms are coprime.
Modular exponentiation: The computation of powers while reducing intermediate values modulo an integer. Coprimality determines when exponentiation can be reversed modulo the modulus.
Coprime in pairs: A relation requiring each pair in a collection to be coprime. For three or more integers, pairwise coprimality is stronger than a common gcd of 1.
Divisibility: The relation in which one integer is an exact multiple of another. Common divisors are the basis of the coprimality test.
Chinese remainder theorem: A theorem that solves simultaneous congruences with pairwise coprime moduli. Coprime moduli guarantee a unique solution modulo their product.

Linked from 22 pages