# Number theory help

1. Mar 13, 2014

### chimath35

Conjecture: suppose n is an integer larger than 1 and n is not prime. Then 2^n-1 is not prime.

Proof attached.

Could someone please explain to me how they got to xy= 2^(ab)-1. I see the -1 part. Also I think I

do not understand the concept of 2^((a-1)b) I mean is it some index or some way of showing it is

finite? I am confused.

#### Attached Files:

• ###### proof 1.PNG
File size:
10.4 KB
Views:
72
2. Mar 13, 2014

### chimath35

Okay the proof is attached, I am having a tough time understanding it.

3. Mar 13, 2014

### Dick

It's just a power of 2. Try multiplying the line in question out term by term. It's what they started doing for you on the next line.

Last edited: Mar 13, 2014
4. Mar 13, 2014

### chimath35

Ya, but I don't get why only the last term has an a in it in each set of numbers?

5. Mar 13, 2014

### chimath35

Also the last paragraph has me confused.

6. Mar 13, 2014

### chimath35

I mean of course b has to be at least two by def. of primes but it didn't take ab = n>a to conclude that but they say it does basically. Then I get lost all after therefore.

7. Mar 14, 2014

### jbunniii

The expression in the second set of parentheses on the first line is $1 + 2^b + 2^{2b} + \ldots + 2^{(a-1)b}$. This means that there are $a$ terms being added, and the exponent of the $k$th term is $(k-1)b$.

8. Mar 14, 2014

### Staff: Mentor

(a - 1)b is the exponent on 2. Like Dick said, it's just a power of 2. Do you not understand how exponents work?

You need to be more specific. Write down the term that is confusing you.

What specifically is confusing in the last paragraph?
No. What it says is that n is a nonprime, and a and b are both smaller than n.

9. Mar 14, 2014

### jbunniii

Well, $b$ is not necessarily prime. But you're right, they could have simply indicated in the first sentence that we can choose $1<a<n$ and $1<b<n$ since $n$ is composite.

Since $b > 1$, we have $x = 2^b - 1 > 1$.

Since $b < n$, we have $x = 2^b - 1 < 2^n - 1$.

Together, these two facts show that $x$ is a nontrivial factor of $2^n - 1$ (i.e. $x$ is neither $1$ nor $2^n-1$), and therefore $2^n - 1$ is not prime.

 fixed a couple of typos

Last edited: Mar 14, 2014
10. Mar 14, 2014

### chimath35

I don't get it.

11. Mar 14, 2014

### jbunniii

Maybe a numerical example would help. If $b = 3$ and $a = 5$ then the expression $1 + 2^b + 2^{2b} + \ldots + 2^{(a-1)b}$ means $1 + 2^3 + 2^6 + 2^9 + 2^{12}$. Without specific numerical choices for $a$ and $b$ we have to use the $\ldots$ notation because the number of terms is a variable. In this notation, typically we write the first few terms explicitly, followed by $\ldots$, followed by the last term or two. Another way to write the same thing is
$$\sum_{k=1}^{a} 2^{(k-1)b}$$

12. Mar 14, 2014

### chimath35

Well, if n is not prime and a and b positive integers then a and b must be great than 2 by def. of prime. Think about it if n is composite and a and b are positive they must be atleast 2 by def. of prime. Any prime is written as 1 times itself they are the only factors.

13. Mar 14, 2014

### chimath35

Uhh thanks, I still just don't see the a-1 clearly that numerical version is simple 2^2b I don't see how or why an a is in there.

14. Mar 14, 2014

### jbunniii

The last term, $2^{12}$, is $2^{3(5-1)} = 2^{b(a-1)}$.

15. Mar 14, 2014

### jbunniii

Maybe a simpler example of the notation would be helpful. What does the expression $1 + 2 + 3 + \ldots + n$ mean to you?

16. Mar 14, 2014

### chimath35

So your expression means the pattern continues for n amount of numbers; also I see that x is neither 1 nor itself.

17. Mar 14, 2014

### chimath35

I get it, when ever I see that expression it just means the power is going up by a certain number each time.

18. Mar 14, 2014

### jbunniii

Right, and similarly for $1 + 2^b + 2^{2b} + \ldots + 2^{(a-1)b}$. The $a-1$ is telling us that the pattern continues for $a$ numbers (since the first exponent is zero).

19. Mar 14, 2014

### jbunniii

Right, the exponent increases by $b$ each time, starting at $0$ and ending at $(a-1)b$.

20. Mar 14, 2014

### chimath35

Also why even write y<xy that has no meaning that I see.