Given the number $n=35$.Find all numbes $1\le a\le n-1$ which are prime to n and they are not witness Fermat of compositeness of n
I found this problem on internet and i am trying to find a solution but i can't find anything.It would be very nice if we can get a proof.
One way of attacking this is to note that the requirements on $a$ is that, for all prime factors $p$ of $n$:
$$a^{n-1} \equiv 1 \pmod{p}$$
If we go through the prime factors of $n$ (5, 7), we find that the above is equivalent to:
$$a \equiv \{1, 4\} \pmod{5}$$ $$a \equiv \{1, 6\} \pmod{7}$$
By the Chinese remainder theorem, that implies that there are four such solutions for $a$, namely $\{ 1, 6, 29, 34 \}$