| | |
$\require{AMSsymbols}$When we divide one integer, $b$, by some other integer, $a \neq 0$, the result is either an integer or its not. If the result is an integer, say $q$, then we have $$\frac{b}{a} = q$$ or equivalently, $$b = aq$$ Consequently, when $b = aq$ for some integer $q$, we say that "$a$ divides $b$", writing $a \mid b$. Equivalently, we might say that "$a$ is a divisor of $b$", "$b$ is a multiple of $a$", or "$a$ is a factor of $b$".
If no such integer $q$ exists, we say that "$a$ does not divide $b$", and write $a \nmid b$. Not surprisingly, we may equivalently say that "$a$ is not a divisor of $b$", "$b$ is not a multiple of $a$", or "$a$ is not a factor of $b$".
For the moment, let us presume that $a$ and $b$ are positive...
In the case that $a$ does not divide $b$, note that we can find some positive remainder that results from the division. For example, when dividing $b=35$ by $a=8$, we see that 8 goes into 35 four times with a remainder of 3 (i.e., $35 = 4 \cdot 8 + 3$). To be explicit, note that we can find this remainder $r=3$ by subtracting as many 8's from 35 as we can without producing a negative. This, of course, necessarily results in the remainder being non-negative and less than 8 (i.e., $0 \le r \lt a$).
Suppose $q$ is the number of positive $a$'s that we can subtract from some positive $b$ without going negative. It shouldn't be too surprising that $b$ can then be uniquely written in the following form: $$b = qa + r \quad \quad 0 \le r \lt a$$
with $a \mid b$ when $r=0$, and $a \nmid b$ when $r \neq 0$.
Interestingly, by restricting $r$ to be non-negative and less than $a$ (i.e., $0 \le r \lt a$), we can uniquely write $b$ in this form even if $b$ is negative. For example, suppose $b = -31$ and $a = 4$. Note, if we subtract the desired non-negative $r \lt 4$ from $b$ it should leave a multiple of $4$. Of the four possibilities for this $r$ ($0$, $1$, $2$, or $3$), only $r=1$ fits the bill. So we can write $-31 = -8 \cdot 4 + 1$. Thus, $-31$ divided by $4$ leaves a remainder of $1$.
This is established formally with the following result (which we will later prove):
The Division Algorithm| If $a$ and $b$ are integers, with $a \gt 0$, there exist unique integers $q$ and $r$ such that $$b = qa + r \quad \quad 0 \le r \lt a$$ The integers $q$ and $r$ are called the quotient and remainder, respectively, of the division of $b$ by $a$. |
We also note that $a \mid b$ (i.e., $a$ is a divisor of $b$) when the aforementioned $r = 0$, and $a \nmid b$ when $r \neq 0$.
The use of the word "algorithm" above is meant to connect this result to a method or process by which we might identify the unique values of $q$ and $r$. There are several such methods, with some vastly more efficient than others.
The simplest (and probably slowest) of these was suggested by the above discussion: If $b$ is positive, the remainder $r$ of the division of $b$ by $a$ is the result of subtracting as many a's as are possible while still keeping the result non-negative. If $b$ is negative, the remainder is found in a slightly different way -- by adding as many $a$'s as necessary until the result becomes non-negative. The quotient $q$ is simply the number of $a$'s added or subtracted, made $q$ negative in the first case and kept positive in the second.
Calculator Tip: To find the remainder of $b/a$ quickly with even a simple calculator, perform the division. If the result was an integer, the remainder is zero and you are done. Otherwise, if the result was positive, subtract off it's integer part, while if the result was negative, add one more than it's integer part. Then, multiply this last result by the value of $a$ to produce the remainder.
The number of positive divisors a number has proves to be a very important way to classify the natural numbers. Only one such number has a single positive divisor, $n=1$, and so this is a special number is in a class all by itself. If a number has exactly two distinct positive divisors, itself and 1, it is called prime. The prime numbers are essentially the "atoms" of the number theory universe, as you will soon undoubtedly discover. Every other positive integer is said to be composite.
Lastly, to introduce one more very important term -- we say that two numbers are relatively prime if they share no common positive divisors other than $1$. So for example, $3$ and $5$ are relatively prime to one another, as are $12$ and $49$. However, $12$ and $27$ are not relatively prime as $3$ divides them both.