Prerequisite: Number systems
A divisibility criterion is a rule that allows us to determine (quickly!) if a number is divisible by another number. The most common ones usually involve some sort of manipulation of the digits of the number in decimal notation.
Powers of
Leading question
How would you extract the last digit of a number using division with remainder?
Divisibility criterion for 2
A number is divisible by 2 iff its last digit is even.
Problem 1
Prove the divisibility criterion for 2.
Divisibility criterion for 4
A number is divisible by 4 iff the number formed by its last two digits is divisible by 4.
Problem 2
Prove the divisibility criterion for 4.
Divisibility criterion for 8
A number is divisible by 8 iff the number formed by its last three digits is divisible by 8.
Problem 3
Prove the divisibility criterion for 8.
Powers of
Leading question
Can you show that the number consisting of
copies of the digit is divisible by and ? What is ?
Divisibility criterion for 3
A number is divisible by 3 iff the sum of its digits is divisible by 3.
Problem 4
Prove the divisibility criterion for 3.
Divisibility criterion for 9
A number is divisible by 9 iff the sum of its digits is divisible by 9.
Problem 5
Prove the divisibility criterion for 9.
Other numbers
Divisibility criterion for 5
A number is divisible by 5 iff its last digit is 0 or 5.
Problem 6
Prove the divisibility criterion for 5.
Divisibility criterion for 11
A number is divisible by 11 iff the alternating sum of its digits is divisible by 11.
Problem 7
Prove the divisibility criterion for 11.
Even more numbers
As we will see this week, divisibility by, say,
Lemma
Suppose
where . Then and .
In particular, we can use this lemma to establish divisibility criteria for numbers like
Problems
Problem 8
For numbers
and find the closest numbers divisible by ; ; ; ; ; ; ; . Hint: no guessing or significant calculations are required.
Problem 9
Show that the following numbers are not squares of natural numbers: а) 12345678; b) 987654; c) 1234560; d) 98765445. Hint: if a square is divisible by, say,
, then it is divisible by . Does this work for every number instead of ?
Comment
We will actually see the condition “have the same remainder” a lot later: such numbers will be called congruent.
Problem 10 (!)
All the mentioned divisibility criteria reduce divibility by a number to checking a smaller number. In particular, the divisibility criterion for
reduces divisibility by to divisibility of the sum of the digits. Actually, a stronger statement is true: the remainder of a number when divided by is the same as the remainder of the sum of the number’s digits when divided by . Prove this statement. Reformulate it for other divisibility criteria.
Prerequisite: Number systems
Problem 11
Consider a number
written base . Can you establish a divisibility criterion for divisibility by ? Hint: compare with dividing by in decimal notation.
Problem 12
Consider a number
written base . Can you establish a divisibility criterion for divisibility by ? Hint: compare with dividing by in decimal notation.
Problem 13 (hard)
Can you establish a divisibility criterion for divisibility by
?
Problem 14 (hard) (open-ended)
Devise divisibility criteria assuming you are given the number in base
.
- What are the criteria of divisibility by
, , , ? - Can you establish a criterion for divisibility by
? by ?