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 \}$

| cite | improve this answer | |
  • $\begingroup$ these solutions of a, except that they are primes to n=35 , are they not witness Fermat of compositeness? $\endgroup$ – Paris Lamp Jul 8 '15 at 19:27
  • $\begingroup$ @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. $\endgroup$ – poncho Jul 8 '15 at 20:49

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.