4
$\begingroup$

This question already has an answer here:

Prove, when $n$ is a positive integer, if $2^n - 1$ is prime, then $n$ is prime.

I did read some sort of proving on the web, but I could not understand it...

Any help?

And if possible, could the explanations be very clear?

Thank you guys :)

So, I've found this from somewhere:

Theorem. If 2n−1 is prime then n is prime.

Proof. Suppose that 2n−1 is prime, and write n=st where s,t are positive integers. Since xs−1=(x−1)(xs−1+xs−2+⋯+1) , we can substitute x=2t to see that 2t−1 is a factor of 2n−1. Since 2n−1 is prime there are only two possibilities, 2t−1=1or2t−1=2n−1 . Therefore t=1 or t=n. We have shown that the only possible factorisations of n are n×1 and 1×n. Hence, n is prime.

However, I have a few questions: 1) how do you know xs−1=(x−1)(xs−1+xs−2+⋯+1) 2) why is '2t−1' a factor of '2n−1' 3) how do you determine '2t−1=1or2t−1=2n−1' from 'Since 2n−1 is prime' 4) 'the only possible factorisations of n are n×1 and 1×n. ' how? 5) how did 'Hence, n is prime' come out as result?

$\endgroup$

marked as duplicate by user26486, user147263, Daniel W. Farlow, Claude Leibovici, Krish Mar 31 '15 at 7:24

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    $\begingroup$ If $\exists p,q\in\mathbb N_{\neq 1} (n=pq)$, then $2^n-1=(2^p-1)(2^{n-p}+\cdots+1)$, contradiction. $\endgroup$ – user26486 Mar 31 '15 at 2:27
3
$\begingroup$

Hint: First, you'd need to know that $(a-b)\mid (a^n - b^n)$ for all $n\in\mathbb{N}$. Once you do that, consider the contrapositive (if $n$ is not prime, then $2^n - 1$ is not prime).

$\endgroup$
  • $\begingroup$ what doess the ' ∣ ' represent? $\endgroup$ – amin Mar 31 '15 at 3:12
  • $\begingroup$ Oh, my bad. $\mid$ represents "divides": $a\mid b$ means you can write $b = ak$, for some integer $k$. $\endgroup$ – Miguelgondu Mar 31 '15 at 3:13
  • $\begingroup$ No problem :) So, a ∣ b means b/a ? $\endgroup$ – amin Mar 31 '15 at 3:14
  • 1
    $\begingroup$ @amin It means $\frac{b}{a}$ is an integer, except for $0\mid 0$. $\endgroup$ – user26486 Mar 31 '15 at 3:16
  • $\begingroup$ Oh okay, thanks. And how do you write the indices... all my indices keep being corrected automatically to become as such: 2^b becomes 2b... $\endgroup$ – amin Mar 31 '15 at 3:27
0
$\begingroup$

If you know the formula for the sum of the terms of a geometric progression find the sum of first $q-1$ terms of a G.P. with first term $1$ and common ratio $2^p$, and remember that the sum is an integer.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.