<s>[INST] Find all the natural numbers which are coprimes to $n$ and are not a fermat witness to compositeness of $n$. The number $n=35$ is given. Find all the natural numbers $1 \leq a \leq n-1$ which are coprimes to $n$ and are not a fermat witness to compositeness of $n$. 
Is it enough to say that we are looking for these numbers that satisfy the following conditions? 
$n=35=5 \cdot 7$ 
$(a,n)=1$ 
$$a^{5-1} \equiv 1 \pmod 5 , \forall a \in \{1, \dots , 4\} \\ a^{7-1} \equiv 1 \pmod 7, \forall a \in \{1, \dots , 6\}$$ 
Can we say also the following for the inverse of the wanted number? 
$(a,35)=1 \Leftrightarrow (a,5)=1 \text{ and } (a,7)=1$ 
$(a,5)=1 \Rightarrow \exists x_1, y_1 : ax_1+5y_1=1 \\ \Rightarrow ax_1 \equiv 1 \pmod 5 \Rightarrow a^4x_1^4 \equiv 1 \pmod 5 \\ \Rightarrow x_1^4 \equiv 1 \pmod 5 \Rightarrow 5 \mid x_1^4 -1=(x_1^2-1)(x_1^2+1)=(x_1-1)(x_1+1)(x_1^2+1) \\ \Rightarrow x_1\equiv 1 \pmod 5 \text{ or } x_1 \equiv -1\pmod 5 \text{ or } x_1^2 \equiv -1\pmod 5$ 
Similar for $7$. 
 [/INST] We want to find  the $a$ in the interval $1\le a\le 34$ such that $a^{34}\equiv 1\pmod{35}$.
Note that since $a$ is relatively prime to $5$ and $7$, we have $a^4\equiv 1\pmod{5}$ and $a^{6}\equiv 1\pmod{7}$. It follows that $a^{12}\equiv 1$ modulo each of $5$ and $7$, and hence modulo $35$.
We have  $a^{12}\equiv 1\pmod{35}$ and $a^{34}\equiv 1\pmod{35}$ if and only if $a^d\equiv 1\pmod{35}$, where $d=\gcd(12,34)=2$.
Thus the non-witnesses to primality are the solutions of $x^2\equiv 1\pmod{35}$. This congruence has $4$ solutions, obtained by splicing together the $2$ solutions of $x^2\equiv 1\pmod{5}$ with the $2$ solutions of $x^2\equiv 1\pmod{7}$ using the Chinese Remainder Theorem. 
There are the two obvious solutions $x\equiv \pm 1\pmod{35}$. This gives $a=1$ and $a=34$. Now solve the system $x\equiv 1\pmod{5}$, $x\equiv -1\pmod{7}$. That gives the solution $a=6$. The final solution is obtained by taking the negative of $6$ modulo $35$, which gives  $a=29$.
</s>