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.

  • $\begingroup$ 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}$ ?? $\endgroup$ – Mary Star Jun 11 '15 at 22:32
  • $\begingroup$ @MaryStar $k$ is an integer and $k>1$. $\endgroup$ – egreg Jun 11 '15 at 22:33
  • $\begingroup$ 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?? $\endgroup$ – Mary Star Jun 11 '15 at 22:38
  • $\begingroup$ @MaryStar Yes, right. And, for $n=4$, … $\endgroup$ – egreg Jun 11 '15 at 22:39
  • $\begingroup$ For $n=4$ we have that $|S|=1$, right?? $\endgroup$ – Mary Star Jun 11 '15 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.