Question

Let n be the positive integer such that ${{2}^{n}}-1$ is a prime number. Prove that n is a prime number.

Answer 1

Hint: Use the contradiction method to solve this question. Suppose n is not a prime and can be expressed as multiplication of two numbers i.e. ‘a’ and ‘b’. So, put
$n=ab$
$N={{2}^{ab}}-1$
Now, divide and multiply the expression N by ${{2}^{a}}-1$ .

Complete step-by-step answer:

As, we need to prove that n will be a prime number if $\left( {{2}^{n}}-1 \right)$ is a prime number. So, let us use the contradiction method and suppose that n is not a prime.
As we know, a prime number is a number which has only two factors, i.e. 1 and the number itself.
So, n is not a prime, hence, we can split ‘n’ in two or more factors. So, let n
$n=ab$ ……………………………………(i)
Where $a>1$ , $b>1$ and $\left( a,b \right)$ are integers.
As it is a problem that ${{2}^{n}}-1$ is a prime number. Hence, we can put the value of n from equation (i) and get that ${{2}^{ab}}-1$ is a prime. Let value of ${{2}^{ab}}-1$ is N. So, we get
$N={{2}^{ab}}-1$ ……………………..(ii)
Now let us observe the expression ${{2}^{ab}}-1$ by putting some values of a and b to it.
On putting $a=2,b=2$ , we get
${{2}^{ab}}-1={{2}^{4}}-1=15$
Now, let us find the values of ${{2}^{a}}-1$ and ${{2}^{b}}-1$ , we get
${{2}^{a}}-1={{2}^{2}}-1=3$ and ${{2}^{b}}-1={{2}^{2}}-1=3$
As 15 is divisible by 3 i.e. ${{2}^{ab}}-1$ is divisible by ${{2}^{a}}-1$ and ${{2}^{b}}-1$ .
Substituting another values of ‘a’ and ‘b’ as $a=5,b=2$ , we get
${{2}^{ab}}-1={{2}^{10}}-1=1024-1=1023$
So, we get values of ${{2}^{a}}-1$ and ${{2}^{b}}-1$ as
${{2}^{a}}-1={{2}^{5}}-1=31$ and ${{2}^{b}}-1={{2}^{2}}-1=3$
Now, 1023 is divisible by 31 and 3 both i.e. ${{2}^{ab}}-1$ is divisible by ${{2}^{a}}-1$ and ${{2}^{b}}-1$ .
Now, let us observe the general expression ${{2}^{ab}}-1$ by dividing it with ${{2}^{a}}-1$ as follows.
Multiply and divide the equation (ii) by $\left( {{2}^{a}}-1 \right)$ . We get,
$N=\left( \dfrac{{{2}^{ab}}-1}{{{2}^{a}}-1} \right)\left( {{2}^{a}}-1 \right)$ ………………………………….(iii)
Now, let us divide ${{2}^{ab}}-1$ by ${{2}^{a}}-1$ as follows: -
\[\begin{align}
  & {{2}^{a}}-1\overset{{{2}^{ab-a}}+{{2}^{ab-2a}}+{{2}^{ab-3a}}+.....1}{\overline{\left){{{2}^{ab}}-1}\right.}} \\
 & \text{ }\underline{-{{2}^{ab}}-{{2}^{ab-a}}} \\
 & \text{ }{{2}^{ab-a}}-1 \\
 & \text{ }\underline{-{{2}^{ab-a}}-{{2}^{ab-2a}}} \\
 & \text{ }{{2}^{ab-2a}}-1 \\
 & \text{ }\underline{-{{2}^{ab-2a}}-{{2}^{ab-3a}}} \\
 & \text{ }{{2}^{ab-3a}}-1 \\
 & \text{ }\text{. }\text{. }\text{. }\text{.} \\
 & \text{ }\text{. }\text{. }\text{. }\text{. } \\
 & \text{ }\text{. }\text{. }\text{. }\text{. } \\
 & \text{ }\text{. }\text{. }\text{. }\text{. } \\
 & \text{ }{{\text{2}}^{a}}-1 \\
 & \text{ }\underline{{{\text{2}}^{a}}-1} \\
 & \text{ }\underline{\text{ }0\text{ }} \\
\end{align}\]
Hence, we get value of $\dfrac{{{2}^{ab}}-1}{{{2}^{a}}-1}$ as
$\dfrac{{{2}^{ab}}-1}{{{2}^{a}}-1}=\left( {{2}^{ab-a}}+{{2}^{ab-2a}}+{{2}^{ab-3a}}+.....+{{2}^{a}}+1 \right)$
Hence, we can write equation (iii) as
$N=\left( {{2}^{a}}-1 \right)\left( {{2}^{ab-a}}+{{2}^{ab-2a}}+{{2}^{ab-3a}}+.....+{{2}^{a}}+1 \right)$ ……………………..(iv)
Now, as we know that $a>1$ and $b>1$ , the value of both brackets of above expression can not be 1. So, we observe the number N can be resolved into two factors, which are given in the equation (iv). So, it is contradicting our assumption that ‘n’ is a prime number. So, it is not possible that the number N will not be a prime because it is given in the problem. So, only one thing is wrong that is our assumption i.e. n is not a prime number.
Hence, ${{2}^{n}}-1$ will be a prime if n is a prime. So, it is proved that n is a prime number.

Note: Another approach to prove the statement that ${{2}^{ab}}-1$ is a multiple ${{2}^{a}}-1$ or ${{2}^{b}}-1$ would be principle of mathematical induction as ${{2}^{ab}}-1$ is factor of ${{2}^{a}}-1$ for $a=2$ So, $p\left( 2 \right)$ is true.
Let ${{2}^{ab}}-1$ is factor of ${{2}^{a}}-1$ , so, we get ${{2}^{ab}}-1=m\left( {{2}^{a}}-1 \right)$.
So, $p\left( a \right)$ is true.
Now, statement $p\left( a+1 \right)$ with the help of above statement i.e. ${{2}^{\left( a+1 \right)b}}-1$ is a factor of ${{2}^{\left( a+1 \right)}}-1$ .
So, it can be another approach.
Therefore, one can prove the question by taking examples of it as well.
Put $n=2$ , we get
${{2}^{2}}-1=3$ (Prime)
$n=3$ , we get
${{2}^{3}}-1=7$ (prime)
$n=5$ , we get
${{2}^{5}}-1=31$ (prime)
Hence, ${{2}^{n}}-1$ will always give a prime, if n is prime. But, we can not generalize this question with this approach.