# Basic number theory proofs

1. Deduce that there is a prime gap of length $\geq n$ for all $n \in \mathbb{N}$
2. Show that if $2^n - 1$ is prime, then $n$ is prime.
3. Show that if $n$ is prime, then $2^n - 1$ is not divisible by $7$ for any $n > 3$.
1. I'm not really sure how to do the first bit.

2. For the second one, I'm not sure if this is correct but I have this: If $n$ is not prime, then $n = a b, a, b > 1$. Also $2^n - 1 = (2 - 1)(1 + 2 + 2^2 + .... + 2^{n-1})$. So if we substitute for $n = ab$, we get $(2^a)^b - 1 = (2^a - 1)(1 + 2^a + (2^a)^2 + .... + (2^a)^{b - 1})$ which is now composite and so if $n = ab$, then $2^n - 1$. This means that $2^n - 1$ is prime if $n$ is prime.

3. For the last one, we have a hint "Follow the example in lectures to show that $2^n - 1$ is not divisible by $3$", but I missed this lecture and haven't had a chance to get the note, so can someone help me with the divisible by $3$ bit and then I can try the divisible by $7$ bit myself.

Thank you

EDIT: I found a simpler proof for the second bit online:

Supposed $n$ is composite, it can be then written in the form $n = ab, a, b > 1 \implies (2^a)^b - 1$ is prime with $b>1$ and $2^a>2$, contradicting statement $1$.

What is statement $1$? Maybe then I can understand why it contradicts it.

-
For the edit, it will be on the page you found. –  anon271828 Feb 1 '13 at 20:10
Please show a bit more effort on your side to solve the homework problems. –  vonbrand Feb 1 '13 at 22:43
Deduce from what? Previous exercises? Theorems given in class? From the statement "For every $k$ there is a prime gap of at least $2^k$"? The last one seems unlikely, though. Context and details are always good! –  Asaf Karagila Feb 2 '13 at 2:55
@AsafKaragila Ohh, I didn't think about it like that! In the first two parts of that question, I already showed that every prime gap is even and that $n! + i$ for $1 < i < n$ is not a prime number. –  Kaish Feb 2 '13 at 13:42
Kaish, that's important and very useful information to the question which makes the first question much easier to answer -- even without having extensive knowledge in number theory. –  Asaf Karagila Feb 2 '13 at 13:44

Since you have shown that there are no primes between $n!$ and $n!+n$, now it's time to combine this with the infinitude of prime numbers and we have the following:

Claim: Let $n>2$ be a natural number, let $p$ be the maximal prime number such that $p<n!$ and let $q$ be the least prime number such that $n!<q$, then there is no prime number between $p$ and $q$ and $q-p\geq n$.

Proof. The first part of the claim is true because any number between $p$ and $q$ would either be between $p$ and $n!$ in contradiction to how we chose $p$, or between $n!$ and $q$ which is a contradiction to how we chose $q$. The second part follows from the fact that $n!+i$ is not a prime number for any $i<n$ and therefore $p<n!+i<q$ and so $q-p\geq n$.

-

For the second, you start with "Assume $n$ is not prime, (in which case you want to consider separately the case $n = 1$ which is not prime, and the case $n$ is composite"), so...(there exist $a>1$, $b>1$ such that $n = ab$).

Then you want to end with "hence, if $n = ab$, then $2^n - 1$ cannot be prime. So you've proven the contrapositive of the proposition, and should end with confirming the proposition: "if $2^n - 1$ is prime, then $n$ must be prime."

Regarding your edit, I am assuming the statement 1 was an assumption, for the sake of contradiction, $n$ is not prime. So $n = 1$ or $n = ab, a, b>1$, and showing case 1: if $n = 1$, then $2^n - 1 = 2 - 1 = 1$, which is not prime. Then what you see is "case 2"... and conclusion.

-

For the first part, you can use the idea of a factorial. Since you are looking for, say $n$ gap, start with $n!+2$. Then $n!+2$ can be divided by 2, since $n!=n(n-1)...2.1$ . Also $n!+k$ if $k$ is less than $n$ divides by $k$, and obviously $n!+n$ divides by $n$. That's a gap of $(n-1)$. If you want $n$ gap, start with (n+1)!.

-
So how does that being able to divide by $k$ show that there is a prime gap of length $n$? –  Kaish Feb 1 '13 at 20:19
@Kaish Have you given any thought to any strategies for showing that a number is not prime? –  Erick Wong Feb 1 '13 at 20:24
@ErickWong Yeah. Square root it and then see if you can divide by any of the prime numbers less that the square root. If you can't, then that number is prime. –  Kaish Feb 1 '13 at 20:26
@Kaish Note that I asked how to show a number is not prime. What is the minimum evidence needed to show that $n!+k$ is not prime? –  Erick Wong Feb 1 '13 at 20:31
all n numbers in the sequence (n+1)!+2,(n+1)!+3,...,(n+1)!+(n+1) divide by the numbers 2,3,4,...,k,...,n, n+1 which means they are not primes. –  ciceksiz kakarot Feb 1 '13 at 20:32

Hint: For the second part, argue by contrapositive as amWhy suggested. Suppose that $n = ab$. Show that $2^n - 1 = 2^{ab} - 1$ is composite by considering the difference of powers factorization $$x^k - y^k = (x-y)(x^{k-1} + x^{k-2}y + \cdots + xy^{k-2} + y^{k-1})$$ It'll also be instructive to reason out why the method fails for prime exponent.

For the third part, consider $$2^n - 1 \pmod 7$$ As $n$ ranges through the natural numbers, the congruence repeats in a very obvious pattern. Try to reason out exactly when $2^n \equiv 1 \pmod 7$.

-

For the 3rd part, if $7\mid(2^n-1)$ where $n$ is any natural number,

We get $2^n\equiv1\pmod 7$

Now, $2\equiv2\pmod 7,2^2\equiv4,2^3=8\equiv1\pmod 7\implies ord_72=3$

Form here, $ord_72\mid n\implies 3\mid n$

Now if $n$ is prime, $n$ must be $3$ else $n$ will be composite.

-