Factors And Multiples
$7\,$ is a factor of $\,$56\,$ while $56\,$ is a multiple of $7.\,$ Both mean that $7\,$ divides $56\,$ or which is again the same that $56\,$ is divisible by $7.\,$ More generally, for any two integers $P\,$ and $Q,\,$ the following statements express exactly the same fact about $P\,$ and $Q:\,$
$ P\,$ divides $Q,\,\,$
$ Q\,$ is divisible by $P,\,$
$ P\,$ is a factor of $Q,\,$
$ Q\,$ is a multiple of $P.$
The words "factor" and "divisor" are synonymous. A mathematical shorthand for "$P \,$is a factor of $Q\,$" is $P|Q.$
$1\,$ divides every number and, therefore, is a factor of every integer: $1|Q,\,$ for every integer $Q.\,\,$ Every integer is a multiple of $1.\,$ Also, every integer is its own multiple and a factor: $P|P.\,$ If $P\,$ is a factor and also a multiple of $Q\,$ (i.e., if $P|Q\,$ and $Q|P)\,$ then $P = Q.\,\,$ Factors different from 1 and the number itself are said to be non-trivial.
Factors come in pairs: if $P\,$ is a factor of $Q,\,$ i.e., if $P\,$ divides $Q\,$ there is an integer $R\,$ (the quotient) such that $Q \div P = R.\,$ In other words, $P \times R = Q\,$ so that $R\,$ is a factor of $Q\,$ and $Q\,$ is a multiple of $R.\,$ (If $Q\,$ is a square, $Q = P^2 = P\times P,\,$ then its factor $P\,$ is paired with itself.)
If $P\,$ is a factor of $Q\,$ and $Q\,$ is a factor of $S\,$ then $P\,$ is a factor of $S.$
Theorem
If $P|Q\,$ and $Q|S\,$ then $P|S.$
Proof
Since $P|Q\,$ there is $R\,$ such that $P\times R = Q.\,$ Since $Q|S\,$ there is $T\,$ such that $Q \times T = S.\,$ Substitute the expression for $Q\,$ found earlier:
$S = (P \times R) \times T = P \times (R \times T).$
In words: a multiple of a mulitple is a multiple or, which is the same, a factor of a factor is a factor.
$P|Q\,$ is a partial order on the set of positive integers which is reflexive $(P|P),\,$ transitive and, like the relation "$\le$", antisymmetric: $P|Q\,$ and $Q|P\,$ imply $P = Q.$
You may wonder why several ways are needed to describe such a simple fact as $P|Q.\,$ The reason is that the same fact has several aspects and can be looked at from different angles. For example, sometimes it is necessary to find all factors of a given number $Q.\,$ Each integer has a finite number of factors. Some factors are prime, some are not. Prime number decomposition is an important part of elementary Number Theory. Every number $P\,$ has an infinite number of multiples: $P = 1\cdot P, 2P, 3P, \ldots\,$ The Sieve of Eratosthenes is an algorithm for finding prime numbers that removes the multiples of successive integers.
Two integers $P\,$ an $Q\,$ always have a common factor $1.\,$ In theory and practice, there is often a need to identify all common, but non-trivial, factors of two or more integers. An integer is a common factor of a number of integers if it divides each one of them. For example, $3\,$ is a common factor of $21,\,$ $36,\,$ and $240.$
Since every integer only has a finite number of factors, two (or more) integers may only have in common a finite number of factors. There is always the largest in a finite set of numbers. The largest number in the set of common factors of two (or more) integers is said to be their Greatest Common Factor or their Greatest Common Divisor, for which abbreviations differ: GCF, GCD, gcf, gcd are all in use. Euclid's algorithm is one way to find the greatest common divisor of two integers.
Two or more integers always have common multiples, i.e., numbers divisible by each one of them. For example, $3,\,$ $5\,$ and $7\,$ have $105,\,$ $210,\,$ $315\,$ ... as common multiples. The product of two integers is a multiples of them both. The theorem that was proved above tells us that "a factor of a factor is a factor" which is in fact the same as saying that "a multiple of a multiple is a multiple." In particular, a multiple of a common multiple is a common multiple. It follows that the number of common multiples is always infinite. There is no point in looking for the largest common multiple. But, among the positive multiples of two (or more) integers, there is always the smallest one. The smallest positive common multiple of two or more numbers is called exactly that: Least Common Multiple, and is denoted LCM or lcm. There are several ways for finding the least common multiples. You may use the factor trees or the onion algorithm. There are also more elementary ways.
|Contact| |Front page| |Contents| |Arithmetic|
Copyright © 1996-2018 Alexander Bogomolny71533978