Divisibility

Divisibility
Tag	`096PW7Q014`
URI	`m2://096PW7Q014`
Aliases	`divides`, `divisor`, `factor`, `multiple`
Kind	definition
Writing	W1 stated
MSC	11A05
Defines	Divisibility

Markdown · JSON · Edit

Definition

Let $a$ and $b$ be integers. The integer $a$ divides $b$ when there is an integer $k$ such that $b = a k$ . The notation $a \mid b$ means that $a$ divides $b$ , and $a \nmid b$ means that it does not. When $a \mid b$ , $a$ is a divisor (or a factor) of $b$ , and that $b$ is a multiple of $a$ .

Remarks

Each integer divides $0$ , because $0 = a \cdot 0$ . The integer $0$ divides only $0$ . The integers $1$ and $-1$ divide each integer. If $a \mid b$ and $b \mid c$ , then $a \mid c$ . On the natural numbers, divisibility is a partial order. If $a \mid b$ and $a \mid c$ , then $a \mid (x b + y c)$ for all integers $x$ and $y$ .

Explanations

L1 human

The integer $a$ divides $b$ when $b$ is in the list $\dots, -2a, -a, 0, a, 2a, \dots$ of the multiples of $a$ . For example, $3 \mid 12$ because $12 = 3 \cdot 4$ . But $5 \nmid 12$ , because no integer $k$ gives $5 k = 12$ .

What this node 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 node is. They do not measure its truth.

What depends on this

128 nodes use this node, directly or through other nodes.

Square-free integer 004JW7A2N5
Sum of divisors 009QCP5T3Z
−1 is a square modulo p if and only if p is not 3 modulo 4 00DW862T78
Congruence is compatible with addition 00FWBN7F0Y
Modular multiplicative inverse 00GXTQMY8Z
Divergence of the sum of the reciprocals of the primes 00RA98X2CP
Hensel's lemma 010QVB71T2
Pythagorean triple 01G1WY1GVX
Legendre symbol 01J8AMV9RS
Integers modulo n 01N3AYAA6N
Diffie–Hellman key exchange 01TKKESHSB
Legendre's formula 01WPV9PHN7
Existence of prime factorization 020K0X7HVR
Euclid's theorem 0292EPPPT0
Fermat pseudoprime 02M2K4QH9P
Greatest common divisor 02WF878BH1
Gauss's lemma on quadratic residues 037ACYXB5Z
Generalized Euclid's lemma 03BAREW1Z5
Wilson's theorem 03KGGKTB2E
Fermat's theorem on sums of two squares 043B3ENSTY
Modulo operation 04FHQSJCQ5
Sum of two squares theorem 04NPWJMA6H
Chinese remainder theorem for non-coprime moduli 04SJTX9P4N
P-adic valuation 04VCPS30ZE
Multiplicativity of the divisor function 04WC36XKV6
Existence of primitive roots modulo a prime 04XGKK8WQW
Euclid's lemma 051VYKA1EX
Fermat numbers are pairwise coprime 05598J0Y8R
Lucas–Lehmer test 061BTYA0RN
Mersenne prime 06GPJF9V7M
Number of invertible residues modulo n 06RJWZCG95
Converse of Wilson's theorem 06WRV8HFDY
Congruence is compatible with multiplication 072D5G4SK6
Lcm of coprime integers 07CZYE06ZJ
Pépin's test 07HXA8KV6F
If 2^p − 1 is prime then p is prime 07MMWAXMYD
Möbius inversion formula 07Q4TBTFVB
Every integer is a square times a square-free integer 080Q3RPKY6
Number of prime factors counted with multiplicity 08420828EY
Fundamental theorem of arithmetic 084HH1NDCB
P-adic valuation of a product 0850JJMJYZ
Law of quadratic reciprocity 085MJS6907
Fermat's right triangle theorem 086BE0J3FZ
von Mangoldt function 087EMZTHWN
Liouville function 08RQAPXF1T
Discrete logarithm 09B4X51J09
Sum of the totient over the divisors 09JXE6XMCC
Cancellation in congruences 09RDZZGJZ9
Least common multiple 09S5SN35DJ
Divisibility by 11 09YBMJTNBM
Prime factorization 0AEKDFCYFA
Multiplicative function 0AP80TT660
The Möbius function is the inverse of the constant function 1 0ASC73QEQT
Totient of a prime power 0AVY8HKBGD
Number of divisors 0BKJT6WG96
Fermat's little theorem in the form a^p = a 0BMXWXDVJZ
Euler product formula 0C3PN4075R
Möbius function 0C8QENHYZW
Division algorithm 0CHQKZFK5S
Consecutive Fibonacci numbers are coprime 0D3PFXEAKF
Bézout's identity 0DQVHMYAGA
Primitive root theorem 0E0DNQK22P
Complete residue system 0E22JKS4W4
Fermat's Last Theorem for n = 4 0E741HSMJ1
A composite number has a prime factor at most its square root 0EB6BBMQMC
Primality test 0EGJZHZ02C
Prime number theorem 0EHBY5Y84N
Divisibility by 9 0ESHD7ZQDX
Divisors of a natural number 0FCWA16FZE
Bertrand's postulate 0FJTGZA4GS
Chinese remainder theorem 0FNN9B4W64
Multiplicativity of the totient function 0FSJA9M43W
Deficient number 0G01TS1RRP
Coprime integers 0GFKP8F8AG
Dirichlet's theorem on arithmetic progressions 0GNVN3CA2P
Completely multiplicative function 0GS27TKF1V
RSA cryptosystem 0HM584C465
Totient of a prime 0HY1MXMEN9
Reduced residue system 0J0QEN1DZR
Congruence is compatible with powers 0J5VGJYYC3
Lifting-the-exponent lemma 0JYF6PTKEW
Classification of Pythagorean triples 0KF3J2KAER
Dirichlet convolution 0KH1N66QWW
Primitive root modulo n 0KM2CJ80G7
Fermat's little theorem 0M25PRN3WQ
Existence of inverses modulo n 0M67FWZWPQ
Euler's criterion 0M7DEDKSYB
Irrationality of square roots of non-squares 0N10YRNNWV
Composite number 0N3ADXHNTQ
Fermat prime 0N9E4G2P97
Multiplicativity of the Legendre symbol 0NW1JP7TBR
First supplement to quadratic reciprocity 0PHBS78HKT
Farey sequence 0PN4QJE969
Dirichlet convolution of multiplicative functions is multiplicative 0PR88XHDMB
Residue class 0QRV8FPK5M
Integers modulo a prime form a field 0R8YXRC9AJ
Divisibility by 3 0R9D4CEJEB
Lucas's theorem 0RY4GGMEQG
Smallest prime factor 0S2SYHTWPY
Dirichlet convolution formula 0SAR26CKPS
Perfect number 0SB7Q8SYSF
Multiplicative order 0SBRX5CZ5R
Prime number 0SN0MAEKYX
Existence of a prime divisor 0SPBEDVNW1
The Gaussian integers form a Euclidean domain 0SPYEFH7H4
Quadratic residue 0SQDB87Z3T
Miller–Rabin primality test 0SZCSYHW60
Infinitely many primes congruent to 1 modulo n 0T1BSD7H3M
Carmichael number 0TA7WT68RK
Product of the gcd and the lcm 0TDY6JZHKS
Congruence modulo n 0TPW25CBN6
Frobenius coin problem 0V11FEXK08
Multiplicativity of the Möbius function 0VB9G5B034
Kummer's theorem 0VBWK9XYDG
Euler's theorem 0VC4DVE7DQ
If 2^n + 1 is prime then n is a power of 2 0VN4H8M12X
Abundant number 0VS0MP1P5H
Euler's totient function 0VV04M41AN
Euclid–Euler theorem 0WETJCKNRG
A prime is a Gaussian prime if and only if it is 3 modulo 4 0WMJSEFYFE
Jacobi symbol 0XDB5AW7M1
Prime-counting function 0XRJB5SSNE
Eisenstein's lemma 0XSDBCP4RZ
The order modulo p divides p − 1 0Y4B7P0GS8
Divisor function 0YEW47VJ0J
Number of distinct prime factors 0YVVXT3A0B
Quadratic reciprocity for the Jacobi symbol 0YY06KP3ZQ
Second supplement to quadratic reciprocity 0ZXW95S44M

Sources

Web https://en.wikipedia.org/wiki/Divisor, Definition

What links here

Used by

Square-free integer 004JW7A2N5
Greatest common divisor 02WF878BH1
Generalized Euclid's lemma 03BAREW1Z5
P-adic valuation 04VCPS30ZE
Euclid's lemma 051VYKA1EX
Sum of the totient over the divisors 09JXE6XMCC
Least common multiple 09S5SN35DJ
Division algorithm 0CHQKZFK5S
Divisors of a natural number 0FCWA16FZE
Prime number 0SN0MAEKYX
Existence of a prime divisor 0SPBEDVNW1
Congruence modulo n 0TPW25CBN6