|
.: Math Note: If you cannot view some of the math on this page, you may need to add MathML support to your browser. If you have Mozilla/Firefox, go here and install the fonts. If you have Internet Explorer, go here and install the MathPlayer plugin. Math
> Number theory
> Divisibility
DivisibilityDivisibility among the integers and natural numbersSibling topics:Contents:
Definition of divisor
Given `x,y in ZZ` with `x != 0`, `x` is a divisor of `y` if there exists an integer `t` such that
`x*t=y`.
`(EE t in ZZ)(x*t=y)`
If `x` is a divisor of `y`, we can also say "`x` divides `y`", and we write "`x div y`". 0 is not a divisor of
any integer, but all nonzero integers are divisors of zero, and of course 1 is a divisor of every integer. A
proper divisor of `y` is a divisor `x` such that `x != y`.
Similarly, given `a,b in NN`, `a div b` if `(EE u in NN)(a*u=b)`. If `y` is not zero, then there are only finitely many divisors, because by Divisors are not greater, `|x|<=|y|`.
Definition of multiple
For `n in ZZ`, the set of multiples of `n` is
`{n*t:t in ZZ}`
The set of multiples of `n` can be abbreviated `nZZ`. Each element of this set is called a multiple
of `n`.
Definition of common divisor
For `x,y in ZZ`, `t` is a common divisor of `x` and `y` if `t div x and t div y`.
Every pair of integers has at least one common divisor, because 1 divides every integer. If `x` or `y` is nonzero, then there are only finitely many common divisors. (See the definition of divisor.)
Definition of GCD
For `x,y` in ZZ`, `t` is the greatest common divisor (GCD) of `x` and `y` if:
`t div x and t div y and (AA u in ZZ)(u div x and u div y => u <= t)
This definition says that `t` is the GCD of `x` and `y` if it is a common divisor of `x` and `y`, and every other
common divisor is less than or equal to `t`. The greatest common divisor of `x` and `y` is written `GCD(x,y)`.
If `x` or `y` is nonzero then a GCD exists because there are only finitely many common divisors (see the definition of common divisor), and one of them is the greatest. If `x` and `y` are both zero, then there is no GCD because there are infinitely many common divisors. The GCD is always positive because 1 is a common divisor of every pair of integers, and 1 is greater than all nonpositive integers.
Definition of common multiple
For `x,y in ZZ`, `t` is a common multiple of `x` and `y` if `t` is a multiple of `x` and `t` is a
multiple of `y`.
Definition of LCM
For `x,y in ZZ-{0}`, `t` is the least common multiple (LCM) of `x` and `y` if:
Theorem: Nonzero integers have LCM Given `x,y in Z-{0}`, there exists a positive common multiple of `x` and `y`. Proof:
Let `z=xyc`, where `c in {-1,1}`. If `xy` is negative, let `c=-1`. Otherwise, let `c=1`. Then, `z>0`, and since
`z=xyc`, `z` is a multiple of both `x` and `y`. Therefore, every pair of nonzero integers `x` and `y` has a
positive common multiple. Furthermore, since the set of possible positive common multiples is bounded from
below (by zero), there exists a common multiple that is less than or equal to all others. So every pair
of nonzero integers has a least common multiple.
Theorem: Divisor divides multiples If `a div b`, then `a div nb` for all `n in ZZ`. Proof:
If `a div b`, then there exists an integer `m` such that `am=b`. Given any integer `n`, `n*b=n*am=a*nm`, and
clearly `a div a*nm`. Therefore, `a div nb`.
Hypothesis: Divisors of a product If `a div b and c div d`, then `a div bd and c div bd and ac div bd`. Theorem: Divisor of a sum If `a div b and b div c`, then `a div b+c and a div b-c`. Proof:
If `a div b` and `a div c`, then there exist integers `m` and `n` such that `am=b` and `an=c`. Then
`b+c=am+an=a(m+n)`. Clearly, `a div a(m+n)`, so `a div b+c`. Similarly, `a div b-c`.
Theorem: Divisors are transitive If `a div b and b div c`, then `a div c`. Proof:
If `a div b` and `b div c`, then by definition there exist integers `m` and `n` such that `am=b` and `bn=c`.
Substituting `am` for `b` in `bn=c`, we get `amn=c`. Because there exists an integer `mn` such that
`a*mn=c`, `a div c`.
Theorem: Divisors are not greater For `a,b in NN`, if `a div b`, then `a<=b`. Proof: By
the definition of
divisor, there exists a natural number `m` such that `am=b`. By
Product of natural number factors is not less, we know that `a<=am`, and since `am=b`, `a<=b`.
This can be extended to the integers because the absolute value of a nonzero integer is a natural number. For `x,y in ZZ` where `y != 0`, if `x div y` then `|x|<=|y|` Corollary (of
Divisors are not greater):
Proper divisors are not greater than half For `a,b in NN`, if `a div b and a!=b`, then `a<=b/2`. Corollary (of
Divisors are not greater):
Symmetric divisors have the same magnitude If `a div b and b div a`, then `|a|=|b|`. Hypothesis: Product of divisors For `a,b,c in NN`, if `a div b and b div c and a<=sqrt(c) and b<=sqrt(c)`, then `ab div c`. Hypothesis: Odd numbers have odd divisors If `b` is odd and `a div b`, then `a` is odd.
This basically says that all divisors of odd numbers are themselves odd.
Hypothesis: Common divisors divide GCD If `t` is a common divisor of `x` and `y`, then `t div GCD(x,y)`. Hypothesis: Product of relative primes If `GCD(a,b)=1` (ie, `a` and `b` are relatively prime) and `t!=0`, then `GCD(at,bt)=|t|`.
If `a` and `b` are relatively prime, then their sets of divisors have nothing in common except 1. So if we
multiply both numbers by `t`, the sets of divisors of the resulting products will have nothing in common except
1 and `|t|`, so the GCD of the products will be `|t|`.
Hypothesis: Relationship between GCD and LCM `LCM(x,y)=(xy)/(GCD(x,y))`
If `d=GCD(x,y)` then `d div x and d div y`. By definition, there exist integers `m` and `n` such that `x=md` and
`y=nd`. Then `xy=md*nd`. We can divide `xy` by `d`, producing `(xy)/d=mnd`. This quantity is still a common
multiple of `x` and `y` (because it's equal to both `nx` and `my`). Because `d=GCD(x,y)`, `m` and `n` are
the smallest possible numbers such that `x=md` and `y=nd`. That is to say, `mnd=(xy)/d` is the least common
multiple.
|