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
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|`.
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.)
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.
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|`
Divisibility
Divisibility among the integers and natural numbersSibling topics:
Contents:
- Common divisors divide GCD
- Divisor divides multiples
- Divisor of a sum
- Divisors are not greater
- Divisors are transitive
- Divisors of a product
- Definition of GCD
- Definition of LCM
- Nonzero integers have LCM
- Odd numbers have odd divisors
- Product of divisors
- Product of relative primes
- Proper divisors are not greater than half
- Relationship between GCD and LCM
- Symmetric divisors have the same magnitude
- Definition of common divisor
- Definition of common multiple
- Definition of divisor
- Definition of multiple
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:
- `t` is a positive common multiple of `x` and `y`, and
- Every positive common multiple of `x` and `y` is greater than or equal to `t`.
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.