Question

Suppose that ${\mathbf{2}}^{\mathbf{N}\mathbf{-}\mathbf{1}}\mathbf{\equiv }\mathbf{1}\mathbf{(}\mathbf{}\mathbf{mod}\mathbf{}\mathbf{n}\mathbf{)}$. Is necessarily prime?

Short answer

No, n is not necessarily prime.

Step-by-step solution

Fermat’s little Theorem

Which says that, Ifnis a prime,a is any integer and$\mathit{n}\boxed{\mathbf{/}}\mathit{a}$ then${\mathbf{a}}^{\mathbf{n}\mathbf{-}\mathbf{1}}\mathbf{\equiv }\mathbf{1}\mathbf{(}\mathbf{}\mathbf{mod}\mathbf{}\mathbf{n}\mathbf{)}$

Finding that Is n necessarily prime or not.

Here we have,$2^{n-1}\equiv 1(modn)$

Heren is not necessarily prime.

Because Fermat pseudo-primes are also satisfy$2^{n-1}\equiv 1(modn)$ while Fermat pseudo-primes are composite integers.

Also, if we take$n=341$ then,

$2^{340}\equiv 1(mod341)$.

Hence,n is not necessarily prime.