Interesting proof... - Tilted Forum Project Discussion Community

KnifeMissile · 01-30-2004, 04:57 PM

I was reading an old math book that had this interesting problem in it. It's not a text book, just a book on mathematical reasoning and problem solving, much like George Polya's classic, How to solve it!
My book is called Doing Mathematics: an Introduction to Proofs and Problem Solving, by Steven Galovich.

Prove that if a^n - 1 is prime, then a = 2.

Although the proof is far from difficult, I wouldn't be surprised if this thread ends up as popular as blizzak's thread, Very Difficult Proof...

blizzak · 01-31-2004, 12:18 AM

hmm looks like merseinne primes to me
heh i'll get back to you on this one in due time

edit: is there supposed to be a restriction or range for n? cause I could disprove this much too easily if not. I think n is supposed to be a prime as well

KnifeMissile · 01-31-2004, 12:59 AM

I think you're getting your logic mixed up.
The question is merely asserting that a^n - 1 is prime. Whether there need be any further restrictions on n to ensure the truth value of this statement is totally irrelevant. The truth value has been established as a given and the implication is what's in question.

Prove that if a^n - 1 is prime, then a = 2.

KnifeMissile · 01-31-2004, 03:08 AM

Okay, it is trivially true that if n = 1, then a can not just be 2 but, indeed, any prime number. After looking at the question, it turns out that I've overlooked a small detail to exclude what is called the trivial case.

By the way, these trivial cases are more common than one might think but they're generally discarded 'cause... well... they're trivial!

Anyway, here's the amendment. Enjoy!

Prove that for n > 1, if a^n - 1 is prime, then a = 2.

blizzak · 01-31-2004, 03:49 PM

ah yes, the trivial case, just as in solving systems of linear equations
makes sense...still working on this

KnifeMissile · 02-02-2004, 01:49 PM

Okay, I'll give you all a hint, since this thread is threatening to fall off the board.

You can decompose a^n - 1 into a composite number by adding 0...

KnifeMissile · 02-09-2004, 12:26 PM

Okay, fine. Since so many people were so interested in this problem, I'll just post the solution right here!

You want to add the identity, 0, but in a very convenient form.

Let S be the summation symbol, represented in this clumsy ASCII form like so:

S(i=0,k)(a^i) = a^0 + a^1 + ... + a^k

So, add the identity 0 = S(i=1,n-1)(a^i) - S(i=1,n-1)(a^i) and the formula will simplify right before your eyes!

Code:

a^n - 1 = a^n - 1 + 0
        = a^n - 1 + S(i=1,n-1)(a^i) - S(i=1,n-1)(a^i)
        = S(i=1,n-1)(a^i) + a^n - 1 - S(i=1,n-1)(a^i)
        = a( S(i=0,n-2)(a^i) + a^(n-1)) - S(i=0,n-1)(a^i)
        = a*S(i=0,n-1)(a^i) - S(i=0,n-1)(a^i)
        = ( S(i=0,n-1)(a^i) ) * (a - 1)

As you can see, a^n -1 can be decomposed into two factors, S(i=0,n-1)(a^i) and a - 1. But a - 1 is supposed to be prime, so the only way that these two terms can not be factors is if a - 1 = 1.

Therefore, a = 2.
QED.

Pretty cool, eh!

rsl12 · 02-21-2004, 11:07 AM

yup, that would have been my proof too knifemissile.

01-30-2004, 04:57 PM	#1 (permalink)
KnifeMissile Location: Waterloo, Ontario	Interesting proof... I was reading an old math book that had this interesting problem in it. It's not a text book, just a book on mathematical reasoning and problem solving, much like George Polya's classic, How to solve it! My book is called Doing Mathematics: an Introduction to Proofs and Problem Solving, by Steven Galovich. Prove that if a^n - 1 is prime, then a = 2. Although the proof is far from difficult, I wouldn't be surprised if this thread ends up as popular as blizzak's thread, Very Difficult Proof...

01-31-2004, 12:18 AM	#2 (permalink)
blizzak Crazy	hmm looks like merseinne primes to me heh i'll get back to you on this one in due time edit: is there supposed to be a restriction or range for n? cause I could disprove this much too easily if not. I think n is supposed to be a prime as well __________________ Fueled by oxytocin! Last edited by blizzak; 01-31-2004 at 12:38 AM..

01-31-2004, 03:49 PM	#5 (permalink)
blizzak Crazy	ah yes, the trivial case, just as in solving systems of linear equations makes sense...still working on this __________________ Fueled by oxytocin!

02-09-2004, 12:26 PM	#7 (permalink)
KnifeMissile Location: Waterloo, Ontario	Okay, fine. Since so many people were so interested in this problem, I'll just post the solution right here! You want to add the identity, 0, but in a very convenient form. Let S be the summation symbol, represented in this clumsy ASCII form like so: S(i=0,k)(a^i) = a^0 + a^1 + ... + a^k So, add the identity 0 = S(i=1,n-1)(a^i) - S(i=1,n-1)(a^i) and the formula will simplify right before your eyes! Code: a^n - 1 = a^n - 1 + 0 = a^n - 1 + S(i=1,n-1)(a^i) - S(i=1,n-1)(a^i) = S(i=1,n-1)(a^i) + a^n - 1 - S(i=1,n-1)(a^i) = a( S(i=0,n-2)(a^i) + a^(n-1)) - S(i=0,n-1)(a^i) = aS(i=0,n-1)(a^i) - S(i=0,n-1)(a^i) = ( S(i=0,n-1)(a^i) ) (a - 1) As you can see, a^n -1 can be decomposed into two factors, S(i=0,n-1)(a^i) and a - 1. But a - 1 is supposed to be prime, so the only way that these two terms can not be factors is if a - 1 = 1. Therefore, a = 2. QED. Pretty cool, eh!

02-21-2004, 11:07 AM	#8 (permalink)
rsl12 On the lam Location: northern va	yup, that would have been my proof too knifemissile. __________________ oh baby oh baby, i like gravy.

01-31-2004, 12:59 AM	#3 (permalink)
KnifeMissile Location: Waterloo, Ontario	I think you're getting your logic mixed up. The question is merely asserting that a^n - 1 is prime. Whether there need be any further restrictions on n to ensure the truth value of this statement is totally irrelevant. The truth value has been established as a given and the implication is what's in question. Prove that if a^n - 1 is prime, then a = 2.

01-31-2004, 03:08 AM	#4 (permalink)
KnifeMissile Location: Waterloo, Ontario	Okay, it is trivially true that if n = 1, then a can not just be 2 but, indeed, any prime number. After looking at the question, it turns out that I've overlooked a small detail to exclude what is called the trivial case. By the way, these trivial cases are more common than one might think but they're generally discarded 'cause... well... they're trivial! Anyway, here's the amendment. Enjoy! Prove that for n > 1, if a^n - 1 is prime, then a = 2.

02-02-2004, 01:49 PM	#6 (permalink)
KnifeMissile Location: Waterloo, Ontario	Okay, I'll give you all a hint, since this thread is threatening to fall off the board. You can decompose a^n - 1 into a composite number by adding 0...