Logo

AskSia

Plus

You need to refer to the sections on Congruence and Arithmetic modulo n in Chapt...
May 23, 2024
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≡3110 \equiv_3 1 and 10k≡3110^k \equiv_3 1 for any positive integer kk, we start by noting that 10≡1(mod3)10 \equiv 1 \pmod{3}
step 2
Since 10≡1(mod3)10 \equiv 1 \pmod{3}, raising both sides to the power of kk gives 10k≡1k(mod3)10^k \equiv 1^k \pmod{3}
step 3
Simplifying, we get 10k≡1(mod3)10^k \equiv 1 \pmod{3} for any positive integer kk
step 4
To show that A×10k≡3AA \times 10^k \equiv_3 A for any positive integers kk and AA, we use the result from step 3
step 5
Since 10k≡1(mod3)10^k \equiv 1 \pmod{3}, multiplying both sides by AA gives A×10k≡A×1(mod3)A \times 10^k \equiv A \times 1 \pmod{3}
step 6
Simplifying, we get A×10k≡A(mod3)A \times 10^k \equiv A \pmod{3}
step 7
Consider a number NN where the digits are [ak,ak−1,⋯ ,a1,a0][a_k, a_{k-1}, \cdots, a_1, a_0]. This number NN is equivalent to N=ak×10k+ak−1×10k−1+⋯+a2×102+a1×10+a0N = 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 10i≡1(mod3)10^i \equiv 1 \pmod{3} for any ii
step 9
Therefore, N≡ak×1+ak−1×1+⋯+a2×1+a1×1+a0(mod3)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≡ak+ak−1+⋯+a2+a1+a0(mod3)N \equiv a_k + a_{k-1} + \cdots + a_2 + a_1 + a_0 \pmod{3}
step 11
Thus, NN is divisible by 33 if and only if ak+ak−1+⋯+a2+a1+a0a_k + a_{k-1} + \cdots + a_2 + a_1 + a_0 is divisible by 33
step 12
To suggest a test for divisibility by 66, note that a number is divisible by 66 if and only if it is divisible by both 22 and 33
step 13
Therefore, a number is divisible by 66 if it is even (last digit is 0,2,4,6,0, 2, 4, 6, or 88) and the sum of its digits is divisible by 33
Answer
A number is divisible by 33 if the sum of its digits is divisible by 33. A number is divisible by 66 if it is even and the sum of its digits is divisible by 33.
Key Concept
Divisibility rules for 33 and 66
Explanation
The sum of the digits of a number determines its divisibility by 33. For divisibility by 66, the number must be even and the sum of its digits must be divisible by 33.
How can we prove that a number is divisible by 3 using the sum of its digits?
Solution by Steps
step 1
To prove that a number is divisible by 3 using the sum of its digits, we start by expressing the number in its decimal form. Let the number be n n and its digits be ak,ak−1,…,a1,a0 a_k, a_{k-1}, \ldots, a_1, a_0 . Then, we can write n n as: n=ak⋅10k+ak−1⋅10k−1+⋯+a1⋅10+a0 n = a_k \cdot 10^k + a_{k-1} \cdot 10^{k-1} + \cdots + a_1 \cdot 10 + a_0
step 2
Notice that 10≡1(mod3) 10 \equiv 1 \pmod{3} . This means that any power of 10 is congruent to 1 modulo 3: 10k≡1k≡1(mod3) 10^k \equiv 1^k \equiv 1 \pmod{3}
step 3
Using this property, we can simplify the expression for n n modulo 3: n≡ak⋅1+ak−1⋅1+⋯+a1⋅1+a0⋅1(mod3) n \equiv a_k \cdot 1 + a_{k-1} \cdot 1 + \cdots + a_1 \cdot 1 + a_0 \cdot 1 \pmod{3} n≡ak+ak−1+⋯+a1+a0(mod3) n \equiv a_k + a_{k-1} + \cdots + a_1 + a_0 \pmod{3}
step 4
Therefore, n n is divisible by 3 if and only if the sum of its digits ak+ak−1+⋯+a1+a0 a_k + a_{k-1} + \cdots + a_1 + a_0 is divisible by 3
Answer
A number is divisible by 3 if the sum of its digits is divisible by 3.
Key Concept
Divisibility by 3 using the sum of digits
Explanation
A number is divisible by 3 if the sum of its digits is divisible by 3 because each power of 10 is congruent to 1 modulo 3.
© 2023 AskSia.AI all rights reserved