CALCU-You need to refer to the sections on Congrue

You need to refer to the sections on Congruence and Arithmetic modulo n in Chapter 3 for this question. Consider numbers such as 19326 or 96123. One way to check whether they are divisible by 3 is to simply try to divide them directly. However, there is a test for divisibility by 3. Add up the digits, e.g. 1 + 9 + 3 + 2 + 6 = 21. Since the sum of the digits 21 is divisibly by 3, then both numbers are divisible by 3, since the sums of their digits are divisible by 3. A number such as 112 is not divisible by 3 since 1 + 1 + 2 = 4 is not divisible by 3. The goal of this question is to prove formally that this test for divisibility by 3 works for the general case. (a) Show that 10 ≡3 1 and 10k ≡3 1 for any positive integer k. (b) Show that A × 10k ≡3 A for any positive integers k and A. (c) Now consider a number where the digits are [ak, ak−1, · · · , a1, a0]. This number N is equivalent to N = ak × 10k + ak−1 × 10k−1 + · · · + a2 × 102 + a1 × 10 + a0, where ak is an integer from 1 to 9, and the rest of the ai are integers from 0 to 9. Show that N ≡3 ak + ak−1 + · · · + a2 + a1 + a0, and then show that N is divisible by 3 if and only if ak + ak−1 + · · · + a2 + a1 + a0 is divisible by 3. (d) Suggest a test for divisibility by 6.

Solution by Steps

step 1

To show that

10 \equiv_3 1

and

10^k \equiv_3 1

for any positive integer

k

, we start by noting that

10 \equiv 1 \pmod{3}

step 2

Since

10 \equiv 1 \pmod{3}

, raising both sides to the power of

k

gives

10^k \equiv 1^k \pmod{3}

step 3

Simplifying, we get

10^k \equiv 1 \pmod{3}

for any positive integer

k

step 4

To show that

A \times 10^k \equiv_3 A

for any positive integers

k

and

A

, we use the result from step 3

step 5

Since

10^k \equiv 1 \pmod{3}

, multiplying both sides by

A

gives

A \times 10^k \equiv A \times 1 \pmod{3}

step 6

Simplifying, we get

A \times 10^k \equiv A \pmod{3}

step 7

Consider a number

N

where the digits are

[a_k, a_{k-1}, \cdots, a_1, a_0]

. This number

N

is equivalent to

N = a_k \times 10^k + a_{k-1} \times 10^{k-1} + \cdots + a_2 \times 10^2 + a_1 \times 10 + a_0

step 8

Using the result from step 3, we know that

10^i \equiv 1 \pmod{3}

for any

i

step 9

Therefore,

N \equiv a_k \times 1 + a_{k-1} \times 1 + \cdots + a_2 \times 1 + a_1 \times 1 + a_0 \pmod{3}

step 10

Simplifying, we get

N \equiv a_k + a_{k-1} + \cdots + a_2 + a_1 + a_0 \pmod{3}

step 11

Thus,

N

is divisible by

3

if and only if

a_k + a_{k-1} + \cdots + a_2 + a_1 + a_0

is divisible by

3

step 12

To suggest a test for divisibility by

6

, note that a number is divisible by

6

if and only if it is divisible by both

2

and

3

step 13

Therefore, a number is divisible by

6

if it is even (last digit is

0, 2, 4, 6,

or

8

) and the sum of its digits is divisible by

3

Answer

A number is divisible by

3

if the sum of its digits is divisible by

3

. A number is divisible by

6

if it is even and the sum of its digits is divisible by

3

.

Key Concept

Divisibility rules for

3

and

6

Explanation

The sum of the digits of a number determines its divisibility by

3

. For divisibility by

6

, the number must be even and the sum of its digits must be divisible by

3

.

How can we prove that a number is divisible by 3 using the sum of its digits?

AskSia

Plus