wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Multiple with all odd digits
        
(Message started by: Aryabhatta on Mar 11^th, 2010, 6:18pm)

Title: Multiple with all odd digits
Post by Aryabhatta on Mar 11^th, 2010, 6:18pm

For any natural number n, there is an n digit multiple of 5ⁿ such that each of the n digits is odd (working in base-10, of course).

Prove.

E.g:
5⁴*15 = 9375, a 4-digit number with all odd digits.

Title: Re: Multiple with all odd digits
Post by towr on Mar 12^th, 2010, 2:18am

[hide]Suppose we have an n-1 all-odd-digit number 5^n-1*k, then we can try to put an odd digit in front of it, such that 5^n-1*k + 5^n-1*2^n-1*m = 5ⁿ*l (where m http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif {1,3,5,7,9} is the new front digit)
So given a k, we need to find an m that satisfies k + 2^n-1*m = 5*l. Because 5 and 2 are coprime, we can always find an m = -k/2^n-1 (mod 5) = -k*3^n-1 (mod 5). This gives us an 0 <= m < 5, but if m is even we can just add 5 to get an odd 0 < m < 10.[/hide]

Title: Re: Multiple with all odd digits
Post by Aryabhatta on Mar 12^th, 2010, 8:54am

Correct! Well done.