Movatterモバイル変換

Jump to content

Divisor

From Wikipedia, the free encyclopedia

(Redirected fromDivisible)

Integer that is a factor of another integer

This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(June 2015) (Learn how and when to remove this message)

This article is about an integer that is a factor of another integer. For a number used to divide another number in a division operation, seeDivision (mathematics). For other uses, seeDivisor (disambiguation).

"Divisible" redirects here. For divisibility of groups, seeDivisible group.

The divisors of 10 illustrated withCuisenaire rods: 1, 2, 5, and 10

Inmathematics, adivisor of an integer $n, {\displaystyle n,}$ also called afactor of $n, {\displaystyle n,}$ is aninteger $m {\displaystyle m}$ that may be multiplied by some integer to produce $n . {\displaystyle n.}$ ^[1] In this case, one also says that $n {\displaystyle n}$ is amultiple of $m . {\displaystyle m.}$ An integer $n {\displaystyle n}$ isdivisible orevenly divisible by another integer $m {\displaystyle m}$ if $m {\displaystyle m}$ is a divisor of $n {\displaystyle n}$ ; this implies dividing $n {\displaystyle n}$ by $m {\displaystyle m}$ leaves no remainder.

Definition

Aninteger $n {\displaystyle n}$ is divisible by a nonzero integer $m {\displaystyle m}$ if there exists an integer $k {\displaystyle k}$ such that $n=km.$ This is written as

m\mid n.

This may be read as that $m {\displaystyle m}$ divides $n, {\displaystyle n,}$ $m {\displaystyle m}$ is a divisor of $n, {\displaystyle n,}$ $m {\displaystyle m}$ is a factor of $n, {\displaystyle n,}$ or $n {\displaystyle n}$ is a multiple of $m . {\displaystyle m.}$ If $m {\displaystyle m}$ does not divide $n, {\displaystyle n,}$ then the notation is $m\not \mid n.$ ^[2]^[3]

There are two conventions, distinguished by whether $m {\displaystyle m}$ is permitted to be zero:

With the convention without an additional constraint on $m, {\displaystyle m,}$ $m\mid 0$ for every integer $m . {\displaystyle m.}$ ^[2]^[3]
With the convention that $m {\displaystyle m}$ be nonzero, $m\mid 0$ for every nonzero integer $m . {\displaystyle m.}$ ^[4]^[5]

General

Divisors can benegative as well as positive, although often the term is restricted to positive divisors. For example, there are six divisors of 4; they are 1, 2, 4, −1, −2, and −4, but only the positive ones (1, 2, and 4) would usually be mentioned.

1 and −1 divide (are divisors of) every integer. Every integer (and its negation) is a divisor of itself. Integers divisible by 2 are calledeven, and integers not divisible by 2 are calledodd.

1, −1, $n {\displaystyle n}$ and $-n$ are known as thetrivial divisors of $n . {\displaystyle n.}$ A divisor of $n {\displaystyle n}$ that is not a trivial divisor is known as anon-trivial divisor (or strict divisor^[6]). A nonzero integer with at least one non-trivial divisor is known as acomposite number, while theunits −1 and 1 andprime numbers have no non-trivial divisors.

There aredivisibility rules that allow one to recognize certain divisors of a number from the number's digits.

Examples

Plot of the number of divisors of integers from 1 to 1000.Prime numbers have exactly 2 divisors, andhighly composite numbers are in bold.

7 is a divisor of 42 because $7\times 6=42,$ so we can say $7\mid 42.$ It can also be said that 42 is divisible by 7, 42 is amultiple of 7, 7 divides 42, or 7 is a factor of 42.
The non-trivial divisors of 6 are 2, −2, 3, −3.
The positive divisors of 42 are 1, 2, 3, 6, 7, 14, 21, 42.
Theset of all positive divisors of 60, $A=\{1,2,3,4,5,6,10,12,15,20,30,60\},$ partially ordered by divisibility, has theHasse diagram:

Further notions and facts

There are some elementary rules:

If $a\mid b$ and $b\mid c,$ then $a\mid c;$ that is, divisibility is atransitive relation.
If $a\mid b$ and $b\mid a,$ then $a=b$ or $a=-b.$ (That is, $a {\displaystyle a}$ and $b {\displaystyle b}$ areassociates.)
If $a\mid b$ and $a\mid c,$ then $a\mid (b+c)$ holds, as does $a\mid (b-c).$ ^[a] However, if $a\mid b$ and $c\mid b,$ then $(a+c)\mid b$ doesnot always hold (for example, $2\mid 6$ and $3\mid 6$ but 5 does not divide 6).
$a\mid b\iff ac\mid bc$ for nonzero $c {\displaystyle c}$ . This follows immediately from writing $ka=b\iff kac=bc$ .

If $a\mid bc,$ and $\gcd(a,b)=1,$ then $a\mid c.$ ^[b] This is calledEuclid's lemma.

If $p {\displaystyle p}$ is a prime number and $p\mid ab$ then $p\mid a$ or $p\mid b.$

A positive divisor of $n {\displaystyle n}$ that is different from $n {\displaystyle n}$ is called aproper divisor or analiquot part of $n {\displaystyle n}$ (for example, the proper divisors of 6 are 1, 2, and 3). A number that does not evenly divide $n {\displaystyle n}$ but leaves a remainder is sometimes called analiquant part of $n . {\displaystyle n.}$

An integer $n>1$ whose only proper divisor is 1 is called aprime number. Equivalently, a prime number is a positive integer that has exactly two positive factors: 1 and itself.

Any positive divisor of $n {\displaystyle n}$ is a product ofprime divisors of $n {\displaystyle n}$ raised to some power. This is a consequence of thefundamental theorem of arithmetic.

A number $n {\displaystyle n}$ is said to beperfect if it equals the sum of its proper divisors,deficient if the sum of its proper divisors is less than $n, {\displaystyle n,}$ andabundant if this sum exceeds $n . {\displaystyle n.}$

The total number of positive divisors of $n {\displaystyle n}$ is amultiplicative function $d(n),$ meaning that when two numbers $m {\displaystyle m}$ and $n {\displaystyle n}$ arerelatively prime, then $d(mn)=d(m)\times d(n).$ For instance, $d(42)=8=2\times 2\times 2=d(2)\times d(3)\times d(7)$ ; the eight divisors of 42 are 1, 2, 3, 6, 7, 14, 21 and 42. However, the number of positive divisors is not a totally multiplicative function: if the two numbers $m {\displaystyle m}$ and $n {\displaystyle n}$ share a common divisor, then it might not be true that $d(mn)=d(m)\times d(n).$ The sum of the positive divisors of $n {\displaystyle n}$ is another multiplicative function $\sigma (n)$ (for example, $\sigma (42)=96=3\times 4\times 8=\sigma (2)\times \sigma (3)\times \sigma (7)=1+2+3+6+7+14+21+42$ ). Both of these functions are examples ofdivisor functions.

If theprime factorization of $n {\displaystyle n}$ is given by

n=p_{1}^{\nu _{1}}\,p_{2}^{\nu _{2}}\cdots p_{k}^{\nu _{k}}

then the number of positive divisors of $n {\displaystyle n}$ is

d(n)=(\nu _{1}+1)(\nu _{2}+1)\cdots (\nu _{k}+1),

and each of the divisors has the form

p_{1}^{\mu _{1}}\,p_{2}^{\mu _{2}}\cdots p_{k}^{\mu _{k}}

where $0\leq \mu _{i}\leq \nu _{i}$ for each $1\leq i\leq k.$

For every natural $n, {\displaystyle n,}$ $d(n)<2{\sqrt {n}}.$

Also,^[7]

d(1)+d(2)+\cdots +d(n)=n\ln n+(2\gamma -1)n+O({\sqrt {n}}),

where $\gamma$ isEuler–Mascheroni constant.One interpretation of this result is that a randomly chosen positive integern has an averagenumber of divisors of about $\ln n.$ However, this is a result from the contributions ofnumbers with "abnormally many" divisors.

In abstract algebra

Ring theory

Main article:Divisibility (ring theory)

Division lattice

Main article:Division lattice

In definitions that allow the divisor to be 0, the relation of divisibility turns the set $\mathbb {N}$ ofnon-negative integers into apartially ordered set that is acomplete distributive lattice. The largest element of this lattice is 0 and the smallest is 1. The meet operation∧ is given by thegreatest common divisor and the join operation∨ by theleast common multiple. This lattice is isomorphic to thedual of thelattice of subgroups of the infinitecyclic group Z.

See also

Arithmetic functions
Euclidean algorithm
Fraction (mathematics)
Integer factorization
Table of divisors – A table of prime and non-prime divisors for 1–1000
Table of prime factors – A table of prime factors for 1–1000
Unitary divisor

Notes

^ $a\mid b,\,a\mid c$ $\Rightarrow \exists j\colon ja=b,\,\exists k\colon ka=c$ $\Rightarrow \exists j,k\colon (j+k)a=b+c$ $\Rightarrow a\mid (b+c).$ Similarly, $a\mid b,\,a\mid c$ $\Rightarrow \exists j\colon ja=b,\,\exists k\colon ka=c$ $\Rightarrow \exists j,k\colon (j-k)a=b-c$ $\Rightarrow a\mid (b-c).$
^ $\gcd$ refers to thegreatest common divisor.

Citations

^Tanton 2005, p. 185
^^a ^bHardy & Wright 1960, p. 1
^^a ^bNiven, Zuckerman & Montgomery 1991, p. 4
^Sims 1984, p. 42
^Durbin (2009), p. 57, Chapter III Section 10
^"FoCaLiZe and Dedukti to the Rescue for Proof Interoperability by Raphael Cauderlier and Catherine Dubois"(PDF).
^Hardy & Wright 1960, p. 264, Theorem 320

References

Durbin, John R. (2009).Modern Algebra: An Introduction (6th ed.). New York: Wiley.ISBN 978-0470-38443-5.
Guy, Richard K. (2004),Unsolved Problems in Number Theory (3rd ed.),Springer Verlag,ISBN 0-387-20860-7; section B
Hardy, G. H.; Wright, E. M. (1960).An Introduction to the Theory of Numbers (4th ed.). Oxford University Press.
Herstein, I. N. (1986),Abstract Algebra, New York: Macmillan Publishing Company,ISBN 0-02-353820-1
Niven, Ivan; Zuckerman, Herbert S.;Montgomery, Hugh L. (1991).An Introduction to the Theory of Numbers (5th ed.).John Wiley & Sons.ISBN 0-471-62546-9.
Øystein Ore, Number Theory and its History, McGraw–Hill, NY, 1944 (and Dover reprints).
Sims, Charles C. (1984),Abstract Algebra: A Computational Approach, New York: John Wiley & Sons,ISBN 0-471-09846-9
Tanton, James (2005).Encyclopedia of mathematics. New York: Facts on File.ISBN 0-8160-5124-0.OCLC 56057904.

v t e Divisibility-based sets of integers
Overview	Integer factorization Divisor Unitary divisor Divisor function Prime factor Fundamental theorem of arithmetic
Factorization forms	Prime Composite Semiprime Pronic Sphenic Square-free Powerful Perfect power Achilles Smooth Regular Rough Unusual
Constrained divisor sums	Perfect Almost perfect Quasiperfect Multiply perfect Hemiperfect Hyperperfect Superperfect Unitary perfect Semiperfect Practical Descartes Erdős–Nicolas
With many divisors	Abundant Primitive abundant Highly abundant Superabundant Colossally abundant Highly composite Superior highly composite Weird
Aliquot sequence-related	Untouchable Amicable (Triple) Sociable Betrothed
Base-dependent	Equidigital Extravagant Frugal Harshad Polydivisible Smith
Other sets	Arithmetic Deficient Friendly Solitary Sublime Harmonic divisor Refactorable Superperfect

v t e Fractions andratios
	Division and ratio	Dividend ÷Divisor =Quotient
	Fraction	⁠Numerator/Denominator⁠ = Quotient
	Algebraic Aspect Binary Continued Decimal Dyadic Egyptian Golden Silver Integer Irreducible Reduction Just intonation LCD Musical interval Paper size Percentage Unit

Retrieved from "https://en.wikipedia.org/w/index.php?title=Divisor&oldid=1263139365"

Hidden categories:

[8]ページ先頭

©2009-2025 Movatter.jp