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.

Advertisements

Entry filed under: Uncategorized.

Jolk Etymology Google Public Data

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed


Human Souls

wordpress visitor counter souls and counting...

%d bloggers like this: