You are here:

Advanced Math/Number Theory

Advertisement


Question
This problem involves Mersenne Numbers,
I understand the proposition that if n is composite then 2^n - 1 is also composite.

I'm having trouble with proving the opposite of this statement for a general term.

I'm trying to show that if n >1 and x is a positive integer with x^n -1 prime, then x = 2 and n is prime.

All I really know so far is that x^n - 1 can be written (x-1)(((x^n-1) -1)...(x+1)
But I have no idea how to actually go about making the connection in the proof.

Thank you,

Answer
You are basically already on track. I will try to give as much detail as I can, following what you have already noted:

Assume x^n - 1 is prime.

If x=2, then n must be prime. If n is composite, then 2^n-1 is also composite. You say you have already shown this, but this can be seen by:

x^n - 1 = 2^(ab) - 1 = (2^b)^a - 1 = (2^b - 1)( (2^b)^(a-1) + (2^b)^(a-2) + .... + 2^b + 1 )

which can be prime only when 2^b-1=1 (i.e. b=1) or a-1=0 (i.e. a=1). The a-1=0 condition is the way to say the entire big factor reduces to 1:

(2^b)^(a-1) + (2^b)^(a-2) + .... + 2^b + 1 = 1.

The sum with "dot dot dot" is the sum of (2^b)^i, where i goes from 0 to a-1. In order for that sum to have only the term 1, you need a-1=0.

In either case, b=1 or a=1, which isn't really fair play when we said n=ab. Assuming "n is composite" really means n=ab and neither a nor b can be 1.

Thus 2^n-1 is composite whenever n is composite, because we have demonstrated a nontrivial factorization. Or, the contrapositive states that if 2^n-1 is prime, then n is prime.

Even though you might know that fact, since you say you already know that part of the proof, I'm repeating it because the same argument works for any number besides 2:

x^(ab) - 1 = (x^b - 1)( (x^b)^(a-1) + (x^b)^(a-2) + .... + x^b + 1 )

So if x^n is prime, it must be true that x^b-1=1 or a-1=0.

But if n=ab is composite (a≠1, b≠1), then a-1=0 is impossible, and x^b-1=1 can only be true when x=2 and b=1 (also impossible since b≠1).

Thus if x^n-1 is prime, no matter what x or n might be, n must be prime.

Furthermore, based on the argument above, even if n is prime, you can factor this with b=1 and a=n to get:

x^(n) - 1 = (x - 1)( (x^b)^(n-1) + (x^b)^(n-2) + .... + x^b + 1 )

which, as mentioned above, requires x=2, otherwise x^n - 1 will be divisible by x-1.

Advanced Math

All Answers


Answers by Expert:


Ask Experts

Volunteer


Clyde Oliver

Expertise

I can answer all questions up to, and including, graduate level mathematics. I am more likely to prefer questions beyond the level of calculus. I can answer any questions, from basic elementary number theory like how to prove the first three digits of powers of 2 repeat (they do, with period 100, starting at 8), all the way to advanced mathematics like proving Egorov's theorem or finding phase transitions in random networks.

Experience

I am a PhD educated mathematician working in research at a major university.

Organizations
AMS

Publications
Various research journals of mathematics. Various talks & presentations (some short, some long), about either interesting classical material or about research work.

Education/Credentials
BA mathematics & physics, PhD mathematics from a top 20 US school.

Awards and Honors
Various honors related to grades, various fellowships & scholarships, awards for contributions to mathematics and education at my schools, etc.

Past/Present Clients
In the past, and as my career progresses, I have worked and continue to work as an educator and mentor to students of varying age levels, skill levels, and educational levels.

©2016 About.com. All rights reserved.