lotus

previous page: 55 arithmetic/digits/6.and.7.p
  
page up: Puzzles FAQ
  
next page: 57 arithmetic/digits/arabian.p

56 arithmetic/digits/all.ones.p




Description

This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

56 arithmetic/digits/all.ones.p


Prove that some multiple of any integer ending in 3 contains all 1s.

arithmetic/digits/all.ones.s

Let n be our integer; one such desired multiple is then
(10^(phi(n))-1)/9. All we need is that (n,10) = 1, and if the last
digit is 3 this must be the case. A different proof using the
pigeonhole principle is to consider the sequence 1, 11, 111, ..., (10^n
- 1)/9. We must have at some point that either some member of our
sequence = 0 (mod n) or else some value (mod n) is duplicated. Assume
the latter, with x_a and x_b, x_b>x_a, possesing the duplicated
remainders. We then have that x_b - x-a = 0 (mod n). Let m be the
highest power of 10 dividing x_b - x_a. Now since (10,n) = 1, we can
divide by 10^m and get that (x_b - x_a)/10^m = 0 (n). But (x_b -
x_a)/10^m is a number containing only the digit 1.

Q.E.D.

 

Continue to:













TOP
previous page: 55 arithmetic/digits/6.and.7.p
  
page up: Puzzles FAQ
  
next page: 57 arithmetic/digits/arabian.p