Solution to a problem asked by Rohan at RSA.

Prove that for every positive integer n there exists an n-digit number divisible by 5n all of whose digits are odd.
Before we proceed let us keep a note of a little thing we'll need.

1 ≡ -4 (mod 5) 3 ≡ -2 (mod 5) 5 ≡ 0 (mod 5) 7 ≡ -3 (mod 5) 9 ≡ -1 (mod 5)

So, the set {1, 3, 5, 7, 9} covers all possible values in mod 5 arithmetic. Now, let us begin the proof.

The statement is clearly true for n = 1 as there exists 5 which is a 1-digit number divisibile by 51 and all its digits are odd.

Let us assume that the statement is true for n = N where N is a positive integer. So, there exists an integer m which is N-digit, divisible by 5N and all its digits are odd.

Now, we will show that for n = N + 1, there exists an integer k10N + m divisible by 5N+1 where k ∈ {1, 3, 5, 7, 9};

k10N + m ≡ 0 (mod 5N+1)

⇔ 5N(k2N + m5N) ≡ 0 (mod 5N+1)

⇔ k2N + m5N ≡ 0 (mod 5)

⇔ k6N + m5N ⋅ 3N ≡ 0 (mod 5)

⇔ k ≡ -m5N ⋅ 3N (mod 5)

⇔ k ∈ {1, 3, 5, 7, 9} … (from the note in the beginning)

So, we have shown that for some odd digit k, we have a number k10N + m divisible by 5N+1. Also, note that this number is an N+1 digit number because m was an N digit number.

Hence, from the principle of mathematical induction, the proof is complete for all positive integers n.

We can use this proof to generate the n-digit numbers for all values of n.

1-digit number: 5 2-digit number: 75 since k = -551 ⋅ 31 mod 5 = -3 mod 5 = 7. 3-digit number: 375 since k = -7552 ⋅ 32 mod 5 = -2 mod 5 = 3. 4-digit number: 9375 since k = -37553 ⋅ 33 mod 5 = -1 mod 5 = 9. and so on …

OEIS entry for this sequence: A151752

No comments

Post a comment

RSS