Question

Show that n is prime if and only if$\mathit{\varphi }\left(n\right)\mathbf{=}\mathit{n}\mathbf{‐}\mathbf{1}$ .

Short answer

The number$n$ is prime if and only if$\varphi \left(n\right)=n‐1$

Step-by-step solution

Identification of the given data

The given data can be listed below as,

• The expression of the $\varphi$-function is,$\varphi \left(n\right)=n‐1$.

Significance of relatively prime

The two distinct positive integers are relatively prime or not can decide if there is no positive integer that is greater than one which divides both the integers, is relatively prime, and otherwise not relatively prime.

Proving the number n is prime if and only if ϕ(n)=n‐1

Let us consider that the$n$ is prime then it is required to show that$\varphi \left(n\right)=n‐1$.

If$n$is prime then, every positive integer less than is relatively prime to, therefore, $\varphi \left(n\right)=n-1$.

Now consider,$\varphi \left(n\right)=n-1$ the it is required to show that is prime. For this it may prove the contra-positive of this consideration. Let is consider is not prime then it is required to show that $\varphi \left(n\right)\ne n-1$.

Let us consider$n$ is composite number then there are positive integers$a$ and$b$ that are less than$n$ that divide$n$ means it can be represented as $n=ab$. Thus,

$$\begin{gathered} \varphi \left(n\right)\le \left(n-1-2\right) \\ \le \left(n-3\right) \end{gathered}$$

Now it can be represented as$\varphi \left(n\right)<\left(n-2\right)$ which is $\varphi \left(n\right)\ne \left(n-1\right)$.

Thus,$n$ is prime if and only if $\varphi \left(n\right)=n-1$.