Divisor: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Greg Woodhouse
(proper divisors)
imported>Sébastien Moulin
(finally adding ''d'' non zero again, as it seems to be a common and useful convention)
Line 1: Line 1:
Given two [[integer]]s ''d'' and ''a'', d is said to ''divide a'', or ''d'' is said to be a ''divisor'' of ''a'', if and only if  there is an integer ''k'' such that ''dk = a''. For example, 3 divides 6 because 3*2 = 6. Here 3 and 6 play the roles of ''d'' and ''a'', while 2 plays the role of ''k''.  Though any number divides itself (as does its negative), it is said not to be a ''proper divisor''. The number 0 is not considered to be a divisor of ''any'' integer.
Given two [[integer]]s ''d'' and ''a'', where ''d'' is nonzero, d is said to ''divide a'', or ''d'' is said to be a ''divisor'' of ''a'', if and only if  there is an integer ''k'' such that ''dk = a''. For example, 3 divides 6 because 3*2 = 6. Here 3 and 6 play the roles of ''d'' and ''a'', while 2 plays the role of ''k''.  Though any number divides itself (as does its negative), it is said not to be a ''proper divisor''. The number 0 is not considered to be a divisor of ''any'' integer.


More examples:
More examples:
Line 27: Line 27:
===Related Concepts===
===Related Concepts===


(If <math>d</math> is a divisor of <math>a</math> (<math>d | a</math>), we say <math>a</math> is a [[multiple]] of <math>d</math>. For example, since <math>4 | 12</math>, 12 is a multiple of 4. If both <math>d_1</math> and <math>d_2<math>are divisors of <math>a</math>, we say <math>a</math> is a common multiple of <math>d_1</math> and <math>d_2</math>. Ignoring the sign (i.e., only considering nonnegative integers), there is a unique [[greatest common divisor]] of any two integers <math>a</math> and <math>b</math> written <math>gcd(a, b)</math> or, more commonly, <math>(a, b)</math>. The greatest common divisor of 12 and 8 is 4, the greatest common divisor of 15 and 16 is 1. Two numbers with a greatest common divisor of 1 are said to be [[relatively prime]]. Complementary to the notion of greatest common divisor is [[least common multiple]]. The least common multiple of <math>a</math> and <math>b</math> is the smallest (positive) integer <math>m</math> such that <math>a | m</math> and <math>b | m</math>. Thus, the least common multiple of 12 and 9 is 36 (written <math>[12, 9] = 36</math>).
(If <math>d</math> is a divisor of <math>a</math> (<math>d | a</math>), we say <math>a</math> is a [[multiple]] of <math>d</math>. For example, since <math>4 | 12</math>, 12 is a multiple of 4. If both <math>d_1</math> and <math>d_2</math>are divisors of <math>a</math>, we say <math>a</math> is a common multiple of <math>d_1</math> and <math>d_2</math>. Ignoring the sign (i.e., only considering nonnegative integers), there is a unique [[greatest common divisor]] of any two integers <math>a</math> and <math>b</math> written <math>gcd(a, b)</math> or, more commonly, <math>(a, b)</math>. The greatest common divisor of 12 and 8 is 4, the greatest common divisor of 15 and 16 is 1. Two numbers with a greatest common divisor of 1 are said to be [[relatively prime]]. Complementary to the notion of greatest common divisor is [[least common multiple]]. The least common multiple of <math>a</math> and <math>b</math> is the smallest (positive) integer <math>m</math> such that <math>a | m</math> and <math>b | m</math>. Thus, the least common multiple of 12 and 9 is 36 (written <math>[12, 9] = 36</math>).


===Further Reading===
===Further Reading===

Revision as of 03:42, 1 April 2007

Given two integers d and a, where d is nonzero, d is said to divide a, or d is said to be a divisor of a, if and only if there is an integer k such that dk = a. For example, 3 divides 6 because 3*2 = 6. Here 3 and 6 play the roles of d and a, while 2 plays the role of k. Though any number divides itself (as does its negative), it is said not to be a proper divisor. The number 0 is not considered to be a divisor of any integer.

More examples:

6 is a divisor of 24 since . (We stress that 6 divides 24 and 6 is a divisor of 24 mean the same thing.)
5 divides 0 because . In fact, every integer except zero divides zero.
7 is a divisor of 49 since .
7 divides 7 since .
1 divides 5 because .
-3 divides 9 because
-4 divides -16 because
2 does not divide 9 because there is no integer k such that . Since 2 is not a divisor of 9, 9 is said to be an odd integer, or simply an odd number.
  • When d is non zero, the number k such that dk=a is unique and is called the exact quotient of a by d, denoted a/d.
  • 0 can never be a divisor of any number. It is true that for any k, however, the quotient 0/0 is not defined, as any k would work. This is the reason 0 is excluded from being considered a divisor.


Notation

If is a divisor of a (we also say that d divides , this fact may be expressed by writing . Similarly, if does not divide , we write . For example, but .

Related Concepts

(If is a divisor of (), we say is a multiple of . For example, since , 12 is a multiple of 4. If both and are divisors of , we say is a common multiple of and . Ignoring the sign (i.e., only considering nonnegative integers), there is a unique greatest common divisor of any two integers and written or, more commonly, . The greatest common divisor of 12 and 8 is 4, the greatest common divisor of 15 and 16 is 1. Two numbers with a greatest common divisor of 1 are said to be relatively prime. Complementary to the notion of greatest common divisor is least common multiple. The least common multiple of and is the smallest (positive) integer such that and . Thus, the least common multiple of 12 and 9 is 36 (written ).

Further Reading

  • Scharlau, Winfried; Opolka, Hans (1985). From Fermat to Minkowski: Lectures on the Theory of Numbers and its Historical Development. Springer-Verlag. ISBN 0-387-90942-7. 
  • Ash, Avner; Gross, Robert (2006). Fearless Symmetry: Exposing the Hidden Patterns of Numbers. Princeton University Press. ISBN 0-691-12492-6.