Solution to a problem asked by Rohan at RSA.

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

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 5^{1} 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
5^{N} and all its digits are odd.

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

k10^{N} + m ≡ 0 (mod 5^{N+1})

⇔ 5^{N}(k2^{N} +
^{m}⁄_{5N}) ≡ 0 (mod
5^{N+1})

⇔ k2^{N} + ^{m}⁄_{5N}
≡ 0 (mod 5)

⇔ k6^{N} + ^{m}⁄_{5N}
⋅ 3^{N} ≡ 0 (mod 5)

⇔ k ≡ -^{m}⁄_{5N} ⋅
3^{N} (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
k10^{N} + m divisible by 5^{N+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 =
-^{5}⁄_{51} ⋅ 3^{1} mod 5
= -3 mod 5 = 7.
3-digit number: 375 since k =
-^{75}⁄_{52} ⋅ 3^{2} mod 5
= -2 mod 5 = 3.
4-digit number: 9375 since k =
-^{375}⁄_{53} ⋅ 3^{3} mod
5 = -1 mod 5 = 9.
and so on …

## No comments