Divisibility
Definition
Let and be integers. The integer divides when there is an integer such that . The notation means that divides , and means that it does not. When , is a divisor (or a factor) of , and that is a multiple of .
Remarks
Each integer divides , because . The integer divides only . The integers and divide each integer. If and , then . On the natural numbers, divisibility is a partial order. If and , then for all integers and .
Where this leads
161 pages build on this one.
- Square-free integer
- Sum of divisors
- −1 is a square modulo p if and only if p is not 3 modulo 4
- Congruence is compatible with addition
- Modular multiplicative inverse
- Divergence of the sum of the reciprocals of the primes
- Hensel's lemma
- Pythagorean triple
- Legendre symbol
- Integers modulo n
- Diffie–Hellman key exchange
- Legendre's formula
- Existence of prime factorization
- Euclid's theorem
- Fermat pseudoprime
- Greatest common divisor
- Gauss's lemma on quadratic residues
- Generalized Euclid's lemma
- Wilson's theorem
- Fermat's theorem on sums of two squares
- Modulo operation
- Sum of two squares theorem
- Chinese remainder theorem for non-coprime moduli
- P-adic valuation
- Multiplicativity of the divisor function
- Existence of primitive roots modulo a prime
- Euclid's lemma
- Fermat numbers are pairwise coprime
- Groups of prime order are cyclic
- Lucas–Lehmer test
- Mersenne prime
- Number of invertible residues modulo n
- Converse of Wilson's theorem
- Congruence is compatible with multiplication
- Lcm of coprime integers
- Pépin's test
- If 2^p − 1 is prime then p is prime
- Möbius inversion formula
- Every integer is a square times a square-free integer
- Number of prime factors counted with multiplicity
- Fundamental theorem of arithmetic
- P-adic valuation of a product
- Law of quadratic reciprocity
- Fermat's right triangle theorem
- von Mangoldt function
- Liouville function
- Discrete logarithm
- Sum of the totient over the divisors
- Cancellation in congruences
- Least common multiple
- Divisibility by 11
- Prime factorization
- Multiplicative function
- The Möbius function is the inverse of the constant function 1
- Totient of a prime power
- Number of divisors
- Fermat's little theorem in the form a^p = a
- Euler product formula
- Möbius function
- Division algorithm
- Consecutive Fibonacci numbers are coprime
- Bézout's identity
- Primitive root theorem
- Complete residue system
- Fermat's Last Theorem for n = 4
- A composite number has a prime factor at most its square root
- Primality test
- Prime number theorem
- Divisibility by 9
- Divisors of a natural number
- Bertrand's postulate
- Chinese remainder theorem
- Multiplicativity of the totient function
- Deficient number
- Coprime integers
- Dirichlet's theorem on arithmetic progressions
- Completely multiplicative function
- RSA cryptosystem
- Totient of a prime
- Reduced residue system
- Congruence is compatible with powers
- Lifting-the-exponent lemma
- Classification of Pythagorean triples
- Dirichlet convolution
- Primitive root modulo n
- Fermat's little theorem
- Existence of inverses modulo n
- Euler's criterion
- Irrationality of square roots of non-squares
- Composite number
- Fermat prime
- Multiplicativity of the Legendre symbol
- First supplement to quadratic reciprocity
- Farey sequence
- Dirichlet convolution of multiplicative functions is multiplicative
- Residue class
- Integers modulo a prime form a field
- Divisibility by 3
- Lucas's theorem
- Smallest prime factor
- Dirichlet convolution formula
- Perfect number
- Multiplicative order
- Prime number
- Existence of a prime divisor
- The Gaussian integers form a Euclidean domain
- Quadratic residue
- Miller–Rabin primality test
- Infinitely many primes congruent to 1 modulo n
- Carmichael number
- Product of the gcd and the lcm
- Congruence modulo n
- Frobenius coin problem
- Multiplicativity of the Möbius function
- Kummer's theorem
- Euler's theorem
- If 2^n + 1 is prime then n is a power of 2
- Abundant number
- Euler's totient function
- Euclid–Euler theorem
- A prime is a Gaussian prime if and only if it is 3 modulo 4
- Jacobi symbol
- Prime-counting function
- Eisenstein's lemma
- The order modulo p divides p − 1
- Divisor function
- Number of distinct prime factors
- Quadratic reciprocity for the Jacobi symbol
- Second supplement to quadratic reciprocity
- Lambert series
- Primitive polynomial over a finite field
- Cohn's irreducibility criterion
- Galois group of a prime degree polynomial with two nonreal roots
- Norm residue isomorphism theorem
- Artin reciprocity law
- Euclid's Elements
- Divisibility poset
- Bombieri–Vinogradov theorem
- Prime-factor FFT algorithm
- Euler product for multiplicative functions
- Vinogradov's theorem
- Non-vanishing of the zeta function on the line Re s = 1
- Cubic reciprocity
- Proof that groups of prime order are cyclic
- Hilbert class field
- Wiener–Ikehara theorem
- Congruent number problem
- Ax–Kochen theorem
- Hasse–Minkowski theorem
- Hardy–Littlewood circle method
- Fast Fourier transform
- Pseudo-spectral method
- Quartic reciprocity
- Chen's theorem
- Chebotarev's density theorem
- Siegel–Walfisz theorem
- Cohomological dimension of a field
- AKS primality test
- Bounded gaps between primes
- Integer factorization
- Lambert summation
Further reading
- Web https://en.wikipedia.org/wiki/Divisor, Definition
About this page
| Tag | 096PW7Q014 |
|---|---|
| URI | m2://096PW7Q014 |
| Aliases | divides, divisor, factor, multiple |
| Kind | definition |
| Writing | W1 stated |
| MSC | 11A05 |
| Defines | Divisibility |
Markdown · JSON · Edit on GitHub
What this page needs for W2
- edge instance_of in: one example (0 of 1)
- edge not_instance_of in: one non-example that fails one clause (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.