<s>[INST] Problem of Number Theory Can you give a tip for this question?
For all $ n $ odd positive integer, let be
$ F(n) = \# \{ a($mod $ n): a^{n-1} \equiv 1($mod $n) \} $
that is the number of elements of the set.


*

*Show that
$$ F(n) = \prod_{p|n} gcd(p-1,n-1) $$

*Let be $ F_0(n) $ the numbers $ a($mod $n) $ such that $ a^n \equiv a($mod $n) $. Find a formula like the previous one,

*Show that if $ F_0(n) $ < n, then $ F_0(n) \leq \frac{2}{3} n $. Show that if $ n \neq 6 $ and $ F_0(n) < n $ then $ F_0(n) \leq \frac{3}{5} n $

 [/INST] I have skimmed over some steps; you can try filling in the details.
1) Write $n=\prod_{i=1}^{m}{p_i^{a_i}}$, where $p_i$ are odd primes.
2) There exists a primitive root $\pmod{p_i^{a_i}}$.
3) Using 2), conclude that the number of solutions $\pmod{p_i^{a_i}}$ of $a^k \equiv 1 \pmod{p_i^{a_i}}$ is $\gcd(\varphi(p_i^{a_i}), k)$.
4) Apply 4) for $k=n-1$ and Chinese Remainder Theorem to get $F(n)=\prod_{i=1}^{m}{\gcd(\varphi(p_i^{a_i}), n-1)}=\prod_{p\mid n}{\gcd(p-1, n-1)}$.
5) If we want to look at even $n$, then for $2^l \| n$, we get $F(n)=\alpha\prod_{p\mid n, 2 \nmid p}{\left(\gcd(p-1, n-1) \right)}$. where $\alpha$ is the number of solutions to $a^{n-1} \equiv 1\pmod {2^l}$. We get $a \equiv 1 \pmod{2^l}$. Thus $$F(n)=\prod_{p\mid n}{\left(\gcd(p-1, n-1) \right)}$$

For $F_0(n)$, a similar approach applies and we get $\gcd(\varphi(p_i^{a_i}), k)+1$ solutions in step $3$, so $$F_0(n)=\prod_{p\mid n}{\left(\gcd(p-1, n-1)+1 \right)}$$ The analysis of even $n$ is also similar, and we get the same formula.

Note $\gcd(p-1, n-1)+1 \leq p$ so $F_0(n) \leq \prod_{p \mid n}{p} \leq n$. If there is strict inequality, either $n$ is not squarefree or $\gcd(p-1, n-1)<p-1$ for some $p$. 
In the former, if $q^2 \mid n$, $F_0(n) \leq \prod_{p \mid n}{p} \leq \frac{n}{q} \leq \frac{n}{2}$. 
In the latter case clearly $p>2$, and we have $\gcd(p-1, n-1) \leq \frac{p-1}{2}$ so $\gcd(p-1, n-1) \leq \frac{p+1}{2} \leq \frac{2}{3}p$. Thus $F_0(n) \leq \frac{2n}{3}$.

Note that if $n$ not squarefree or $p \geq 5$ in case 2, we get $F_0(n) \leq \frac{3n}{5}$. Thus if $\frac{3n}{5}<F_0(n)<n$ then we must have $n$ squarefree and $p=3$ in case $2$, $\gcd(3-1, n-1)=1$, $\gcd(p-1, n-1)=p-1$ for $p \mid n, p \not =3$. 
We have $\gcd(2, n-1)=1$ so $2 \mid n$. Thus $6 \mid n$
If $p \mid n$ for some $p>3$ then $\gcd(p-1, n-1)=p-1$ implies $n$ odd, a contradiction.
Thus $n$ is squarefree and a multiple of $6$, i.e. $n=6$.
</s>