## 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 numbers#### Sibling 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`.

**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.**

*Proof:***Theorem:**Divisor divides multiples

If `a div b`, then `a div nb` for all `n in ZZ`.

**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`.**

*Proof:***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`.

**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`.**

*Proof:***Theorem:**Divisors are transitive

If `a div b and b div c`, then `a div c`.

**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`.**

*Proof:***Theorem:**Divisors are not greater

For `a,b in NN`, if `a div b`, then `a<=b`.

**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`.**

*Proof:*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.