Question

Prove that for any integer$\mathit{p}\mathbf{>}\mathbf{1}$,ifrole="math" localid="1663222073626" $\mathit{p}$isn’tpseudoprime, then$\mathit{p}$fails the Fermat test for at least half of all numbers in${{\mathbf{{\rm Z}}}_p}^{+}$

Short answer

To solve the problem understanding the concepts of subgroup i.e., it is required to show that it is nonempty and closed under the inverses and multiplication.

Step-by-step solution

Understanding the given concept 

To show that the set is a subgroup, it is required to show that it is nonempty and closed under the inverses and multiplication.

To prove that elements set inΖp+ that pass the Fermat test forms multiplicative subgroup ofΖp+

Since the subgroup order divides the group order, if subgroup is a strict subgroup, it must contain at most half of elements of group.

First, the set is nonempty, since.$1^{p-1}\equiv 1\mathrm{mod}p$

To prove if p is not pseudoprime then p fails Fermat Test for at least half of number 

If$a^{p-1}\equiv 1\left(\mathrm{mod}p\right)$ and, then${\left(ab\right)}^{p-1}\equiv a^{p-1}{b}^{p-1}\equiv 1\mathrm{mod}p$ , which shows closure under multiplication.

If ,$a^{p-1}\equiv 1\left(\mathrm{mod}p\right)$ then multiplying both sides of the equation by ${\left(a^{-1}\right)}^{p-1}$the shows that. $1\equiv {\left(a^{-1}\right)}^{p-1}\mathrm{mod}p$Thus, the set is closed under inverses.

Hence, on the other side if is not pseudo prime then fails Fermat Test for at least half of number.