# A composite odd number, not being a power of $3$, is a fermat-pseudoprime to some base

I want to prove the following statement :

If $$n$$ is an odd composite number, not being a power of $$3$$ (or, equivalent, having a prime factor $$p>3$$), $$n$$ is a fermat-pseudoprime to same base $$a$$, in other words, there is a number $$a$$ with $$1 and $$a^{n-1}\equiv 1\ (\ mod\ n\ )$$

I was able to prove the converse:

If $$a^{n-1}\equiv 1\ (\ mod\ n\ )$$ for some number $$a$$ with $$1, then the number $$o\ :=\ ord_a(n)$$ divides both $$n-1$$ and $$\phi(n)$$. Since $$o=1$$ is impossible because $$a\equiv 1\ (\ mod\ n\ )$$ contradicts $$1 and $$\phi(3^k)=2\times 3^{k-1}$$ , it follows that $$o=2$$. But $$a^2\equiv 1\ (\ mod\ 3^k\ )$$ implies $$a\equiv \pm1\ (\ mod\ 3^k\ )$$ because of $$gcd(a-1,a+1)\le 2$$. But this contradicts $$1, so the number cannot be a power of $$3$$

Is my proof of the converse correct ?

How can I show the original statement ?

Yes, your proof of the converse is correct.

To prove the original statement:

If $n = p^k$ for a prime $p > 3$, then the group of units modulo $n$ is cyclic, and therefore contains an element $a$ of order $p-1 \geqslant 4$. This is a base for which $n$ is a Fermat pseudoprime, and $a \not\equiv \pm 1 \pmod{n}$.

If $n$ has at least two distinct prime factors $p,q$, say $n = p^kq^m\cdot r$ with $\gcd(r,pq) = 1$, then let

$$a \equiv 1 \pmod{p^kr},\quad a \equiv -1 \pmod{q^m}.$$

Then $a^2 \equiv 1 \pmod{n}$, and $n$ is a Fermat pseudoprime for the base $a$.

• First of all, thanks for checking my proof. Could you explain, why the group of units of $\mathbb Z_{p^k}$ is cyclic, if $p>3$ ? Sep 17 '15 at 18:39
• It's cyclic for all odd primes $p$, but for $p=3$, we have $p-1= 2$, and then the element of order $p-1$ is $\equiv -1\pmod{n}$, as you noted in the question. If you already know that the group of units of $\mathbb{Z}/(p)$ is cyclic - any finite subgroup of the group of units of a field is cyclic, and $\mathbb{Z}/(p)$ is a finite field - then you get it by lifting. Say $r_1$ is a primitive root modulo $p$. Then look at $r_1^{p-1} \equiv 1 + kp\pmod{p^2}$. If $k \neq 0$, then the order of $r_1$ modulo $p^2$ is $p(p-1)$, so $r_1$ is a primitive root modulo $p^2$. Sep 17 '15 at 18:54
• If $k = 0$, then $(r_1 + p)^{p-1} \equiv r_1^{p-1} + (p-1)r_1^{p-2}p \not\equiv 1 \pmod{p^2}$, and $r_2 = r_1 + p$ is a primitive root modulo $p^2$. Continue until you reach $p^k$. If you have $r_m$ such that the order of $r_m$ modulo $p^m$ is $(p-1)\cdot p^{m-1}$, then either $r_m$ has order $(p-1)\cdot p^m$ modulo $p^{m+1}$, or $r_m + p^m$ has order $(p-1)\cdot p^m$ modulo $p^{m+1}$. Sep 17 '15 at 18:54
• OK, I know that $\mathbb Z_p$ is cyclic, but I must think about the "lifting". Sep 17 '15 at 18:59
• Not really, since we need an order divisible by $p^{k-1}$. Cauchy's theorem would only give us an element whose order is the product of all distinct prime divisors of $(p-1)\cdot p$ (we get that since our group is abelian, so if the orders of $a$ and $b$ are coprime, we have $\operatorname{ord}(ab) = \operatorname{ord}(a)\cdot \operatorname{ord}(b)$). But here, once we have the element of order $p-1$ modulo $p$, all we need is a part of the binomial theorem to get from $p^m$ to $p^{m+1}$. Sep 17 '15 at 19:12