Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Seeking formal proof: primes, powers, factors
Replies: 11   Last Post: Jul 5, 2014 5:49 AM

 Messages: [ Previous | Next ]
 Chris Angelico Posts: 4 Registered: 7/3/14
Seeking formal proof: primes, powers, factors
Posted: Jul 3, 2014 8:51 AM

Greetings, experts!

I hope this is an appropriate place to ask this question; if not, please
point me to some place where it's more appropriate.

(Caveat: I'm not a tertiary-trained mathematician in any sense; my
skills and terminology are basically high school algebra level.)

Given any prime number P and whole number B, either P is a factor
of B, or P is a factor of B^(P-1)-1.

I can state with confidence that this is true, by looking to long
division. With a base of 10, this is the standard conversion of vulgar
fraction to repeating decimal fraction - for example, the expansion of
1/7 is calculated thus:

10/7 = 1, remainder 3
30/7 = 4, remainder 2
20/7 = 2, remainder 6
60/7 = 8, remainder 4
40/7 = 5, remainder 5
50/7 = 7, remainder 1
10/7 = ... and we're back to the top.

It repeats on period 6, which means that 7 * 142857 = 999999, which is
10^6-1.

The remainder must be a whole number smaller than the original prime,
and it can be 0 only if the prime is a factor of the base, which means
that there are only six possible remainders for the division. Since
the "state" of the division is simply the previous remainder, there
are only six possible states, which means the cycle MUST repeat after
six digits. (Some expansions repeat sooner than that, eg 1/3 repeats
on period 1. It's always a factor of the maximum - in this case, 2 -
so it's still true that it repeats on period 2.)

None of this depends on the division being done in base 10. It works
in any other base, just as well. (With a base of 2, we're looking at
Mersenne numbers; ergo for any prime number P, the P-1th Mersenne
number is a multiple of P.) And it works for any prime number. Hence
the original postulation.

So, since it's provably unfalsifiable, it ought to be possible to
prove mathematically. But how? What aspect of mathematics makes this
true? Surely there must be something.

Hope you find this sort of thing as fascinating as I do!

Chris Angelico

Date Subject Author
7/3/14 Chris Angelico
7/3/14 bert
7/3/14 Chris Angelico
7/3/14 Peter Percival
7/3/14 scattered
7/3/14 Chris Angelico
7/3/14 bert
7/3/14 Chris Angelico
7/4/14 Brian Q. Hutchings
7/4/14 bert
7/4/14 quasi
7/5/14 Phil Carmody