8.2k views
2 votes
Prove that for all integers n ≥ 0, (10n) ≡ 1 (mod 9). b. Use

part (a) to prove that a positive integer is divisible by 9 if, and
only if, the sum of its digits is divisible by 9.

User Ritlew
by
7.4k points

1 Answer

5 votes

Final answer:

To prove that for all integers n ≥ 0, (10n) ≡ 1 (mod 9), we can use mathematical induction. We also use this result to prove that a positive integer is divisible by 9 if, and only if, the sum of its digits is divisible by 9.

Step-by-step explanation:

To prove that for all integers n ≥ 0, (10n) ≡ 1 (mod 9), we can use mathematical induction. First, we establish the base case n = 0. In this case, 10^0 = 1, and 1 ≡ 1 (mod 9), so the statement holds.

Next, we assume that for some k ≥ 0, (10^k) ≡ 1 (mod 9). We want to show that (10^(k+1)) ≡ 1 (mod 9) based on this assumption.

We can write (10^(k+1)) as (10^k) * 10. Since (10^k) ≡ 1 (mod 9), we can substitute this congruence into the expression and get (10^(k+1)) ≡ 1 * 10 ≡ 10 ≡ 1 (mod 9).

Therefore, by mathematical induction, we have proven that for all integers n ≥ 0, (10n) ≡ 1 (mod 9).

To prove that a positive integer is divisible by 9 if, and only if, the sum of its digits is divisible by 9, we can use the fact that any positive integer can be expressed as a sum of its digits multiplied by powers of 10.

Using the result from part (a), we know that (10n) ≡ 1 (mod 9). Consider a positive integer m and let d1, d2, ..., dn be its digits. We can write m as m = d1 * 10^k1 + d2 * 10^k2 + ... + dn * 10^kn.

Using the result from part (a) repeatedly, we have m ≡ d1 * 1 + d2 * 1 + ... + dn * 1 ≡ d1 + d2 + ... + dn (mod 9). Since m ≡ d1 + d2 + ... + dn (mod 9), m is divisible by 9 if and only if d1 + d2 + ... + dn is divisible by 9.

User Alan John
by
7.9k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories