# Divisibility

The ends justify the means. -- after Matthew Prior

## 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

### Divisibility

Divisibility among the integers and natural numbers

#### Contents:

Definition of divisor [tags: 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 [tags: 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 [tags: 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 [tags: GCD divisor]
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 [tags: 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 [tags: LCM multiple]
For `x,y in ZZ-{0}`, `t` is the least common multiple (LCM) of `x` and `y` if:
1. `t` is a positive common multiple of `x` and `y`, and
2. Every positive common multiple of `x` and `y` is greater than or equal to `t`.
Note that if `x=0` or `y=0`, the least common multiple is defined to be zero. The least common multiple of `x` and `y` is written `LCM(x,y)`.
Theorem: Nonzero integers have LCM [tags: multiple 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 [tags: divisor multiple]
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 [tags: divisor multiple]
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 [tags: divisor]
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 [tags: divisor]
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 [tags: divisor]
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 [tags: divisor]
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 [tags: divisor]
If `a div b and b div a`, then `|a|=|b|`.
Hypothesis: Product of divisors [tags: divisor]
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 [tags: odd divisor]
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 [tags: GCD divisor]
If `t` is a common divisor of `x` and `y`, then `t div GCD(x,y)`.
Hypothesis: Product of relative primes [tags: prime GCD]
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 [tags: GCD 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.