Question

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.

Answer 1

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.