4by12

Prime Numbers

Here’s a nice one. Show that, for any prime number p other than 2 and 5, there is a multiple of p that is written as a series of 1’s in decimal representation. For example, 111 is a multiple of 3, and 11 is a multiple of itself. Hint: Use the pigeonhole principle.

The solution: First, let’s show that there’s a multiple of p that is written as a series of 1’s, followed by a series of 0’s (e.g. 1111000). Consider the set of numbers {1, 11, 111, 1111, …}. For each item, calculate its ‘modulu p’: {1 mod p, 11 mod p, …}. Each of these is an integer between 0 and p-1. Because the original set is infinite, it must therefore contain two different items that are the same mod p (pigeonhole principle). Let’s call them a and b and assume a>b. Then (a-b) is the desired number, because:
(a-b mod p) = (a mod p) - (b mod p) = 0.

Okay, so for the prime p we have a number x that’s divisable by p, and:

x = 111…10…0 = 111…1 * 10^n

We can divide x by 10^n to get rid of the zeros and get y = x / 10^n = 111…1. y is still divisable by p because p isn’t 2 or 5.