# Find all numbes $1\le a\le n-1$ which are prime to n and they are not witness Fermat of compositeness of n

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 \}$
• @paris: they all have $a^{34} = 1 \pmod{35}$, and hence they are not Fermat witnesses. Reminder: the Fermat test for compositeness is $a^{n-1} \ne 1 \pmod{n}$; if we find an $a \ne 0 \pmod{n}$ where this is true, then we've shown that $n$ is composite. An $a$ that doesn't show this is a Fermat nonwitness. – poncho Jul 8 '15 at 20:49