3
$\begingroup$

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<a<n-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<a<n-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<a<n-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<a<n-1$, so the number cannot be a power of $3$

Is my proof of the converse correct ?

How can I show the original statement ?

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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$ ? $\endgroup$ – Peter Sep 17 '15 at 18:39
  • 1
    $\begingroup$ 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$. $\endgroup$ – Daniel Fischer Sep 17 '15 at 18:54
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Daniel Fischer Sep 17 '15 at 18:54
  • $\begingroup$ OK, I know that $\mathbb Z_p$ is cyclic, but I must think about the "lifting". $\endgroup$ – Peter Sep 17 '15 at 18:59
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Daniel Fischer Sep 17 '15 at 19:12

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.