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 + m⁄5N) ≡ 0 (mod 5N+1)
⇔ k2N + m⁄5N ≡ 0 (mod 5)
⇔ k6N + m⁄5N ⋅ 3N ≡ 0 (mod 5)
⇔ k ≡ -m⁄5N ⋅ 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 = -5⁄51 ⋅ 31 mod 5 = -3 mod 5 = 7.
3-digit number: 375 since k = -75⁄52 ⋅ 32 mod 5 = -2 mod 5 = 3.
4-digit number: 9375 since k = -375⁄53 ⋅ 33 mod 5 = -1 mod 5 = 9.
and so on …
OEIS entry for this sequence: A151752
Posts
