## Bizarre Fact About Factors

*March 6, 2010 at 2:50 pm* *
Leave a comment *

For *any* integers B and x greater than 1, where B is not a multiple of any factors of x: There exists a positive integer n such that (B^n)-1 is divisible by x.

In other words: 999….9999 is a multiple of any given number, except for evens and multiples of 5 (base 10). You just need the right number of nines.

In binary, 1111…111 has the same property.

I won’t write out a formal proof, but here’s a simple explanation:

The decimal expansion of 1/x is a repeating decimal.

Therefore, it’s a fraction over B^n-1.

Inverting both sides of the equation, B^n-1 is a multiple of x.

This doesn’t actually work if x is a multiple of 2 or 5 (in decimal), or in general any of the factors of the radix, because the repeating decimal will have a number of zeroes before it. But it works in all other cases.

Example:

99999999999999999999999999999999999999999999999999999999999999999

99999999999999999999999999999999999999999999999999999999999999999

99999999999999999999999999999999999999999999999999999999999999999

99999999999999999999999999999999999999999999999999999999999999999

99999999999999999999999999999999999999999999999999999999999999999

99999999999999999999999999999999999999999999999999999999999999999

99999999999999999999999999999999999999999999999999999999999999999

99999999999999999999999999999999999999999999999999999999999999999

99999999999999999999999999999999999999999999999999 is a multiple of 1,337. That’s 570 nines.

Hey, I never said n had to be small.

EDIT: After poking around Wikipedia and playing with Wolfram|Alpha a bit, it seems that an upper bound on N is x-1. A better upper bound, however, is LCM(a,b,c…) where a,b,c are the prime factors of x, minus one.

1337 = 7*191.

LCM(6,190) is — guess what? — 570.

Entry filed under: Uncategorized.

Trackback this post | Subscribe to the comments via RSS Feed