Number Theory
4.1 Divisibility
Divides Notation and Basic Language
Number theory is a branch of mathematics that focus on the properties and relationships of numbers, usually the positive integers, and how we might generalize these facts. Some common topics of the field include divisibility, remainders, prime numbers, and modular arithmetic. In the elementary classroom we teach children about divisibility, how to factor, and how to find greatest common divisors or least common multiples. We will begin this section by revisiting divisibility.
When we say that a number is divisible by another number, we mean that the division of the two will not leave a remainder. To begin, we need to learn to generalize statements. We must think in terms of variables instead of specific numbers. Because the exact number is not the focus of our study, but the behavior of numbers like it.
Definition: Divides
Let $a,b\in\mathbb{W}$ with $b\ne 0$. We say "$b$ divides $a$" if there exists a whole number $k$ such that
$$a=bk.$$
We write this as $b\mid a$.
Furthermore, if $b\mid a$, then:
- $b$ is a factor (or divisor) of $a$.
- $a$ is a multiple of $b$.
Example: Notation usage
First, a simple example to get comfortable with the notation. What is the relationship between $12$ and $3$ when using division?
Show Solution
$$12\div 3 = 4$$ means that $3$ divides $12$. We would say $$3|12$$ and our reasoning for it is because $$12=3(4)$$
Remember in general if $a$ is divisible by $b$, we say $b$ divides $a$, or $b|a$ which means, $a=b(k)$ for some whole number $k$
MyOpenMath: Divides notation
Warning: Notation Pitfalls
The statements $b\mid a$, $\dfrac{b}{a}$, and $a\mid b$ are all different.
- $b\mid a$ means a divisibility relationship.
- $\dfrac{b}{a}$ means division.
- $a\mid b$ swaps the direction and may change truth value.
The whole number properties even and odd come up frequently in the classroom. These are recongiziable traits that can be used for things like pattern recognition. Before, we would say a number is even if it is evely divisible by two. However, because when dividing by two, the remainder algorithm gives us two distinct classes for numbers. A number either falls into
$$n=2(k)$$ or $$n=2(k)+1$$
These are exactly the definitions of even and odd. If the division left no remainder, the number is even. If the there was a remainder (which can only be 1, why?) then the number must be odd.
Definition: Even and Odd
A whole number $n$ is:
- even if $2\mid n$, equivalently $n=2k$ for some $k\in\mathbb{W}$.
- odd if $2\nmid n$, equivalently $n=2k+1$ for some $k\in\mathbb{W}$.
Example: Reading and checking divisibility statements
Decide whether each statement is true or false and explain why.
- $3\mid 12$
- $8\mid 2$
- $1\mid a$ for every whole number $a$
- $0\mid 2$
- $a\mid 0$ for every nonzero whole number $a$
Show Solution
Let's go one by one and keep the definition in front of us: $b\mid a$ means $a=bk$ for some whole number $k$.
- True: $12=3\cdot 4$.
- False: there is no whole number $k$ with $2=8k$.
- True: $a=1\cdot a$ always works.
- False: $0\mid 2$ would require $2=0\cdot k$, impossible.
- True (for $a\ne 0$): $0=a\cdot 0$.
The key idea is that divisibility is an existence statement: "Can I write it as a clean multiple?"
MyOpenMath: Divides notation
Divisibility Over Sums and Differences
Once we know a number divides two separate numbers, we can sum those numbers and keep divisibility. This is may be a simple fact, but it enables some powerful ideas later on for us. Consider this simple example: $5$ divides $15$ and $5$ divides $20$.
$$5|15 \land 5|20$$
We can check them real quick, $15=5(3)$ and $20=5(4)$. Now, we know that
$$5|(15+20) \rightarrow 5|35$$
Checking by defintion, $35=5(7)$. In fact, when we added them together we could have thought about $15$ as $3$ groups of $5$ and $20$ as $4$ groups of $5$. The result would have been $3+4=7$ groups of $5$ and that is exactly what we see here.
$$35=5(3+4)$$
This is truely a remarkable result, even if it seems simple at first.
Theorem: Divisibility Over a Sum
If $d\mid a$ and $d\mid b$, then $d\mid (a+b)$.
Proof
Assume $d\mid a$ and $d\mid b$. Then there exist whole numbers $q_1,q_2$ such that
$$a=dq_1,\qquad b=dq_2.$$
Add the equations:
$$a+b=dq_1+dq_2=d(q_1+q_2).$$
Since $q_1+q_2\in\mathbb{W}$ (closure), this matches the definition of $d\mid (a+b)$.
Fact: Useful Consequences
For whole numbers $d,a,b$:
- If $d\mid a$ and $d\mid b$, then $d\mid(a-b)$ whenever $a\ge b$.
- If $d\mid a$, then $d\mid (na)$ for every $n\in\mathbb{W}$.
Example: Using sum and difference rules strategically
Show that $6\mid (84-30)$ and $6\mid (84+30)$ without direct long division.
Show Solution
Because $84=6\cdot 14$ and $30=6\cdot 5$, we already know $6\mid 84$ and $6\mid 30$.
Then divisibility over sums/differences gives:
$$6\mid(84-30)=54,\qquad 6\mid(84+30)=114.$$
This is a great habit: prove divisibility structurally first, then compute if you want the value. We can see here since we were working with $14$ groups of $6$ and $5$ groups of $6$, then the difference would be $14-5=9$ groups of $6$, or $54$, while the sum would is $14+5=19$ groups of $6$ or $114$.
MyOpenMath: Divisibility over sum/difference
Divisibility Rules for 2, 5, 10, 4, and 8
Now we can use our little theorem for divisibility over sums and differences to get some general rules for divisibility. Some of which you already know, and possibly some of which will be new to you. First, divisibility by two. I think most people know that a number is divisible by two, or even, if the last digit is divisible by two. Why?
Well, for any whole number in base 10, we can write it as an expanded sum of powers of 10. Lets take $4938$ as our starting example. It seems like a sufficiently random number.
$$4938=4(1000)+9(100)+3(10)+8$$
In our theorem above, we only showed that the sum worked for adding two numbers together, but any number of terms work. So as long as $2$ divides every part of the sum, it will divide the sum.
$$4938=4(2\cdot 500)+9(2\cdot 50)+3(2\cdot 5)+8$$ $$4938=2(4\cdot 500)+2(9\cdot 50)+2(3\cdot 5)+8$$
Well, now we've shown that $2$ divides every piece of that sum except for the ones place. All we have to do is check and see if $2|8$, and it does, $8=2(4)$. This is why when checking to see if a number is even, you only have to check the one's place. Because in base $10$, every other position can be written as $10^n=(2\cdot 5)^n=2(2^{n-1}\cdot 5^n)$, which means every position other than the ones is guarenteed to be divisible by two.
Similarly, we could have pulled the $5$ or $10$ out front in those parenthesis using our associative and commutative rules of multiplication.
$$4938=5(4\cdot 200)+5(9\cdot 20)+5(3\cdot 2)+8$$ or $$4938=10(400)+10(90)+10(3)+8$$
because for any power of 10 greater than 1, we have
$$10^n=(2\cdot 5)^n=5(2^{n}\cdot 5^{n-1})$$ or $$10^n=10(10^{n-1})$$
Thus, we have our first rules of divisibility.
Theorem: Divisibility by 2, 5, and 10
For a whole number $n$:
- $2\mid n$ iff the last digit is even ($0,2,4,6,8$).
- $5\mid n$ iff the last digit is $0$ or $5$.
- $10\mid n$ iff the last digit is $0$.
We can do something similar to get divisibility rules for $4$ and $8$, but we'll need more than the ones place. Because $4=2\cdot 2$ we'll have to go all the way to the $100$'s place to guarentee divisibility by $4$.
$$10^2=(2\cdot 5)^2 = 4(5^2).$$
This means that any place that is $100$ or greater, we can split it up into $4$'s. $100=4(25)$, $1000=4(250)$, and so on. So given some arbitary number, we only need to check if the last two places of the number are divisible by 4.
$$4938 = 4(4\cdot 250)+4(9\cdot 25)+38$$
$38$ is unforunately not divisible by $4$, so neither is $4938$.
To get divisibility by $8$, we're gonna need three $2$s. That means any position $(10)^3=8(5^3)$ or higher will be divisble by $8$. We've only gotta check the last $3$ digits. While it isn't as quick of a check as $2$ or $4$, it is still significantly easier than checking some much larger number for divisibility.
Theorem: Divisibility by 4 and 8
For a whole number $n$:
- $4\mid n$ iff the number formed by the last two digits is divisible by 4.
- $8\mid n$ iff the number formed by the last three digits is divisible by 8.
Example: Fast screening with end-digit rules
Determine which of $2,4,5,8,10$ divide each number.
- $97,128$
- $83,026$
- $1,458,333$
Show Solution
We'll be quick and systematic.
- $97,128$: last digit is 8, so divisible by 2. Last two digits are 28, so divisible by 4. Last three digits are 128, divisible by 8. Not divisible by 5 or 10.
- $83,026$: last digit is 6, so divisible by 2 only among these end-digit tests. Last two digits 26 is not divisible by 4. Last three digits 026 is 26, not divisible by 8. Not by 5 or 10.
- $1,458,333$: last digit 3, so not divisible by 2, 5, or 10. Last two digits 33 not divisible by 4. Last three digits 333 not divisible by 8.
The attentive student might notice that if divisiblity by $2$ fails, there is no reason to check for $4$ or $8$.
MyOpenMath: Last-digit divisibility tests
Divisiblity rule for 6
$6$ is nice in that it is $6=2\cdot 3$. We can use this to our advantage to create a divisibility rule for 6. In our previous result, we saw that if $a|c$ and if $b|c$ with $a$ and $b$ being distinct natural numbers, then $(ab)|c$.
To pick some specific numbers to go with that, if $2|c$ and $3|c$, then $(2\cdot 3)|c$, or more explicity, $6|c$. This means that if a number is divisible by both $2$ and $3$, then it will be divisible by $6$
Theorem: Divisibility by 6
A whole number is divisible by $6$ iff it is divisible by both $2$ and $3$.
Similarly we can find rules for other composite numbers. For example, a number will be divisible by $12$ if it is divisible by both $3$ and $4$.
Theorem: Divisibility by 12
A whole number is divisible by $12$ iff it is divisible by both $3$ and $4$.
Digit-Sum and Alternating-Sum Rules: 3, 9, and 11
The number $3$ is where things start to change up a bit, because $3$ isn't a factor of $10$, $100$, or any power of $10$ for that matter. Because again, powers of $10$ are made up of $2$'s and $5$'s. $(10)^n=(2\cdot 5)^n=2^n\cdot 5^n$. But exactly one less than a power of 10, numbers like 9, 99, 999, and so on, are all divisible by 3. This is because (3\cdot 3=9). Let's take another number, say $5721$ and observe:
If both of the terms in this sum are divisible by $3$, then the whole number is divisible by $3$. So we only need to check if $5+7+2+1$ is divisible by $3$. And it is, $5+7+2+1=15$. So $5721$ is divisible by $3$.
By the exact same reasoning, we could have factored out a 9 instead of a 3 in that last step.
$$5721=\underbrace{9\cdot (5\cdot 111+7\cdot 11+2\cdot 1)}_{\text{divisible by 9}}+(5+7+2+1)$$
Theorem: Divisibility by 3 and 9
A whole number is divisible by:
- $3$ iff the sum of its digits is divisible by $3$.
- $9$ iff the sum of its digits is divisible by $9$.
Example: Divisibility by 3 and 9
Check if they following are divisible by 3 or 9.
- $1234$
- $369369$
- $111111111$
Show Solution
A quick check
- $1+2+3+4=10$, which is divsible by neither $3$ nor $9$.
- We could add all of those digits up. But each individual digit is divisible by $3$, so will the sum be. A little meta divisiblity. Similarly, we can disreguard the 9's, and the two $3+6=9$. This number is also divisible by $9$.
- Counting them up, there are nine $1$'s. So the sum is $9$ making the number divisible by both $3$ and $9$.
$11$ is in a similar boat as $3$ and $9$ in that it shares no factors with $10$. It also has a pattern, which may seem strange at first, in that every power of 10 will have a number divisible by 11 either directly above it, or below it. For example
$$10+1=11$$ $$100-1=99=11(9)$$ $$1000+1=1001=11(91)$$
This may be a little tough to show in general for us at this point, so we'll take it for granted. But observe the following derivation: if $n$ is some number in base 10 with digits $abcd$ then,
Theorem: Divisibility by 11
A whole number is divisible by $11$ iff its alternating digit sum is divisible by $11$.
For $a_ka_{k-1}\cdots a_1a_0$, test
$$a_0-a_1+a_2-a_3\pm \cdots a_k$$
Example: Testing 3, 9, and 11 in one pass
Decide divisibility of $8{,}471{,}986$ by $3$, $9$, and $11$.
Show Solution
Digit sum first:
$$8+4+7+1+9+8+6=43.$$
Since $43$ is not divisible by 3 or 9, the number is divisible by neither 3 nor 9.
Now for 11, take an alternating sum from right to left:
$$6-8+9-1+7-4+8=17.$$
Since 17 is not divisible by 11, the original number is not divisible by 11 either.
So the final verdict is: not divisible by 3, not by 9, and not by 11.
MyOpenMath: Digit-sum and alternating-sum rules
Divisibility rule for 7
$7$ is another special case in that it shares no factors with $10$. We will have to do something clever to a number to break it apart into something that is cleanly divisble by $7$ and something that is easily computable to get a rule for divisibility by $7$. Lets take some number, say $9247$, and start with its expanded form.
$$9247=9(1000)+2(100)+4(10)+7$$
Now we'll multiply both sides of this number by $2$.
$$ 2(9247)=9(2000)+2(200)+4(20)+7(2)$$
This may seem pooly motivated, but know that $21$ is divisible by $7$. And adding any number of $0$'s to the end of it won't change that fact. So lets add a $10^{n-1}$ to each $10^n$ position, to turn things like $2000$ into a $2100$.
$$2(9247)=9(2000) + 9(100) - 9(100) + 2(200) + 2(10) - 2(10) + 4(20) + 4(1) - 4(1) +7(2)$$
Remember we can't just add numbers to an equation and it stay true, so we also have to subtract them so the value stays the same. Now we can regroup some of these terms so that they take advantage of the $21$'s we've built.
With some clever number theory we've taken the number $9247$ and created an expression that separated the last digit from the rest, and subtracted twice that digit from it.
$$9247$$ became $$924 - 2(7)$$
The utility in this is that if this number is divisible by $7$, so will be the original.
$$942 - 2(7) = 910$$
Its still kind of hard to see if this number is divisble by $7$. But the beautiful part of this process is that we don't make any assumption about the original number. As long as its in base 10, we can do it again!
$$910$$ $$91-2(0)$$ $$91$$
Still not sure, lets do it again.
$$91$$ $$9-2(1)$$ $$7$$
And it is clear that this number is divisible by 7. Fantastic! This is a good taste of what number theory can do.
Theorem: Divisibility by 7
A whole number is divisible by 7 iff the number formed by removing the last digit, then subtracting twice the last digit, is divisible by 7.
If $n=10a+b$, test $a-2b$.
Example: Applying the 7-rule repeatedly
Check whether $2541$ is divisible by 7.
Show Solution
Apply the rule recursively:
$$2541\mapsto 254-2(1)=252$$ $$252\mapsto 25-2(2)=21$$
Now 21 is clearly divisible by 7, so 252 is divisible by 7, and therefore 2541 is divisible by 7.
This is why the recursive test is powerful, it shrinks the number fast.
Example: Mixed divisibility check
Determine whether $471240$ is divisible by $2,3,5,6,7,8,9,10,11$.
Show Solution
Use quick tests:
- By 2: yes (last digit 0)
- By 3: yes (digit sum $4+7+1+2+4+0=18$)
- By 5: yes (last digit 0)
- By 6: yes (by 2 and 3)
- By 8: yes (last three digits 240, and $240\div 8=30$)
- By 9: yes (digit sum 18)
- By 10: yes (last digit 0)
- By 11: yes (alternating sum $0-4+2-1+7-4=0$, and 0 is divisible by 11)
- By 7: check quickly $47124\mapsto 4712-8=4704\mapsto 470-8=462\mapsto 46-4=42$, yes
So this number is divisible by all listed values.