# Prime - composite numbers

Let $n>2$ a natural number. We define the following sets: $$S=\{1 \leq a \leq n : (a,n)=1, a^{n-1} \not\equiv 1\pmod n\} \\ T=\{1 \leq b \leq n : (b,n)=1, b^{n-1} \equiv 1 \pmod n\}$$

1. Are there prime numbers $n$ for which $S \neq \varnothing$ ? Are there composite numbers $n$ for which $S=\varnothing$ ? Explain.
2. If $S \neq \varnothing$, show that $|S| \geq \frac{\phi(n)}{2}$.

Hint: Show that $T$ is a subgrub of $(\mathbb{Z}/n\mathbb{Z})^{\star}$. Which is the order?



For the first one, for a prime $n$, according to Fermat's theorem we have that $a^{n-1} \equiv 1 \pmod n$, so for all primes it stands that $S=\varnothing$, or not??

Could you give me some hints for the other questions??

The hint says to prove that $T$ can be identified with a subgroup of $(\mathbb{Z}/n\mathbb{Z})^*$, by using the residue classes.

Then $T$ is a subgroup because, whenever you have a finite abelian group $G$, the set $\{x\in G: x^k=1\}$ is a subgroup for any integer $k$.

The group $G=(\mathbb{Z}/n\mathbb{Z})^*$ has order $\varphi(n)$, so $|T|$ is a divisor of $\varphi(n)$: $k|T|=\varphi(n)$. Since $S=G\setminus T$ is by assumption not empty, we can draw a conclusion about $k$ and so…

Regarding the search of $n$ such that $S\neq\emptyset$, try a small composite number.

• From $S=G \setminus T$ do we have that $|S|=|G|-|T|=\phi(n)-\frac{\phi(n)}{k}$ ?? How can we continue to show that $|S| \geq \frac{\phi(n)}{2}$ ?? – Mary Star Jun 11 '15 at 22:32
• @MaryStar $k$ is an integer and $k>1$. – egreg Jun 11 '15 at 22:33
• So, we have that $$k \geq 2 \Rightarrow \frac{1}{k} \leq \frac{1}{2} \Rightarrow -\frac{1}{k} \geq -\frac{1}{2}$$ $$|S|=\phi(n)-\frac{\phi(n)}{k} \geq \phi(n)-\frac{\phi(n)}{2}=\frac{\phi(n)}{2}$$ right?? – Mary Star Jun 11 '15 at 22:38
• @MaryStar Yes, right. And, for $n=4$, … – egreg Jun 11 '15 at 22:39
• For $n=4$ we have that $|S|=1$, right?? – Mary Star Jun 11 '15 at 22:43