Easiest way to check whether the number is prime or not

Question

Recently I came across a YouTube video which explains the easiest way to check whether the given number is prime or not the equation was:

$$\frac{2^x - 2}{x}$$

According to that video if $x$ is a prime number, it will give a whole number as a result. If $x$ is not a prime number, it will give a number with decimal place as result.

For example for 6, the result is 10.333... so it is not a prime. for 7, the result is 18 so it is a prime number.

I tried out some number and found out that this is true for most of the number, How's this possible? is this a correct equation.

See the full video here: https://youtu.be/AUn7h05A8WM

Answer 1

The correct statement is: for all positive odd integers $n$, if $n$ is prime, then $n$ divides $2^n-1$.

---

Here is a quick proof: For any prime $p$ and $k< p$, we know that $p$ can't divide $k!$, but $p$ does divide $p!$. Therefore $$p\mid{p\choose k}$$ for all $p>k>0$. For all positive integers $a$, we have by the binomial formula: $$2^p=(1+1)^p=\sum_{k=0}^{p}{p\choose k}$$ $p$ divides all terms of this sum, except where $k=0$ and $k=p$, so there is some integer $n$ such that:

$$2^p=pn+{p\choose 0}1^0+{p\choose p}1^p=pn+2$$ so $2^p-2=pn$, so $2^p-2$ is divisible by $p$.

Answer 2

Mwahahahaha! I love how often humans are ensnared by the trap of small numbers. Show something is true for a few small numbers and then they think it's true for all numbers.

They see that for $n = 2$, the only even prime, we get $$\frac{2^n - 2}{n} = \frac{4 - 2}{2} = 1,$$ but for all higher even $n$, it is easy to see that $$\frac{2^n - 2}{n}$$ will be a rational number but not an integer.

Then for the odd $n$, they invoke Fermat's little theorem. So many misconceptions with that one: it should be called Fermat's big theorem if he had actually come up with it. The Tooth Fairy, Santa Claus and the ancient Chinese knew about it long before Fermat.

Anyway, the big theorem tells us that $a^p \equiv a \pmod p$ if $p$ is prime and $\gcd(a, p) = 1$. So if $p$'s an odd prime, it's coprime to $2$ and therefore $2^p - 2$ is a multiple of $p$.

However, this provides no guarantee for odd composite numbers. Hint: use modular arithmetic if the numbers get too big for your calculator.