Prove that for each positive integer n, there exists an n-digit number having only odd digits and divisible by 5^n

As we are just looking for the piece of cheese here rather than a deep explanation, we can do this:

There are answers for 5,25,125, obviously. And we can add any odd number we like in front of the last number we found and still ensure divisibility by the last power of 5 we used since if 5^x divides y, it also divides 10y.

Now for 625 we have:

625              
1375 mod 625=125
3375 mod 625=250
5375 mod 625=375
7375 mod 625=500
9375 mod 625= 0

and then:

3125              
19375 mod 3125 =  625
39375 mod 3125 = 1875
59375 mod 3125 = 0
79375 mod 3125 = 1250
99375 mod 3125 =2500

and then:

15625             
 
159375 mod 15625 = 3125 
359375 mod 15625 = 0 
559375 mod 15625 =12500 
759375 mod 15625 =9375 
959375 mod 15625 = 6250 

We observe that each odd number chosen generates a different multiple (0 to 4) mod 5^n of 5^(n-1). One and exactly one of these must also be divisible by 5*5^(n-1), or 5^n. So by induction we are guaranteed a solution for any length n; and that solution is unique for that value of n.

Neat problem.

Edited on May 13, 2013, 11:13 am

Posted by broll on 2013-05-13 10:34:32