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

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.

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.

• Use the Chinese remainder theorem. You look at each prime factor separately (generally, the prime powers dividing $n$), and glue the things together with the CRT. – Daniel Fischer Jun 23 '14 at 20:11
• Let's do it with Fermat's theorem: $$a^{90}\equiv \left(a^6\right)^{15}\equiv 1\mod 7$$ and $$a^{90}=\left(a^{12}\right)^7a^6\equiv a^6\mod 13$$ But that's still not that easy to write down, which $1\le a\le 91$ fulfill this property. – 0xbadf00d Jun 23 '14 at 21:32
• You don't need to find which, only how many. How many residues modulo $13$ satisfy $a^6 \equiv 1 \pmod{13}$? – Daniel Fischer Jun 23 '14 at 21:33
• You have $k$ residues modulo $7$ that satisfy $a^{90}\equiv 1 \pmod{7}$. and $m$ residues modulo $13$ with $a^{90} \equiv 1 \pmod{13}$. Then you have $k\cdot m$ residues modulo $7\cdot 13$ with $a^{90} \equiv 1 \pmod{91}$. – Daniel Fischer Jun 23 '14 at 21:47
• You are only looking at the remainders modulo $7$ there. There are only $7$ such, one of them has $a^{90}\equiv 0 \pmod{7}$. – Daniel Fischer Jun 23 '14 at 22:25