How many $\overline{a}\in\left(\mathbb{Z}/91\mathbb{Z}\right)^\times$ pass the Fermat and Miller-Rabin primability tests?

Question

Let $$\text{F}_{91}:=\left\{\overline{a}\in\left(\mathbb{Z}/n\mathbb{Z}\right)^\times:91\text { passes the Fermat primality test to base }a\right\}$$ and $$\text{MF}_{91}:=\left\{\overline{a}\in\left(\mathbb{Z}/n\mathbb{Z}\right)^\times:91\text { passes the Miller-Rabin primality test to base }a\right\}$$ How do we calculate $|\text{F}_{91}|$ and $|\text{MF}_{91}|$? Starting with the Fermat primality test: As described in the Wikipedia article, the algorithm depends on a parameter $k$. In each iteration (there are at most $k$ iterations), a random variable $a\in\left(\mathbb{Z}/n\mathbb{Z}\right)^\times$ is chosen and testet for $$a^{91-1}\equiv1\text{ mod }91$$ If this test fails, the algorithm stops and yields that $91=7\cdot 13$ is not prime. However, I'm not sure how to calculate $|\text{F}_{91}|$ since the test depends on some randomness.

Answer 1

The randomness (or more likely pseudo-randomness) that one uses in the application of the tests shall be ignored here.

"The Fermat test to base $a$" is specifically whether $a^{n-1} \equiv 1 \pmod{n}$, like the "Miller-Rabin test to base $a$" (also called strong Fermat test) is whether $a^m\equiv 1 \pmod{n}$ or $a^{2^j\cdot m} \equiv -1 \pmod{n}$ for one $j \in \{0,\dotsc,k-1\}$, where $n-1 = 2^k\cdot m$ with $m\equiv 1 \pmod{2}$.

So the question is, for how many $\overline{a} \in (\mathbb{Z}/91\mathbb{Z})^\times$ do we have

• $a^{90} \equiv 1 \pmod{91}$, resp.
• $a^{45} \equiv \pm 1 \pmod{91}$.

Since $91 = 7\cdot 13$, the numbers are not hard to find.