# How to show that n is a pseudoprime to the base $\hat{b}$, where $\hat{b}$ is the inverse of b modulo n?

Let $\gcd(b,n)=1$ and let $n$ be a pseudoprime to the base $b$. How to show that $n$ is a pseudoprime to the base $\hat{b}$, where $\hat{b}$ is the inverse of b modulo n?

$\hat{b}$ satisfies formula $b \hat{b} \equiv 1 \pmod n$

following pseudoprime: Let k>1. Integer n>1 is pseudoprime to the base b, if n is composite and $b^n≡b \pmod n$.

-
There are several kinds of "pseudoprimes": for example, $n$ is a Fermat pseudoprime to the base $b$ if $\gcd(b,n)=1$ and $b^{n-1}\equiv 1 \pmod{n}$; $n$ is an Euler pseudoprime to the base $b$ if $\gcd(b,n)=1$ and $b^{(n-1)/2}\equiv \pm 1\pmod{n}$ (implies Fermat pseudoprime, but is not equivalent); $n$ is a strong pseudoprime to the base $b$ if $n=d2^s+1$ with $d$ odd, $\gcd(b,n)=1$ and either $b^d\equiv 1\pmod{n}$ or $b^{d2^r}\equiv -1\pmod{n}$ for some $r$, $0\leq r\lt s$. Which kind of pseudoprime are you working with? Just add the definition you are using on top. – Arturo Magidin Sep 27 '11 at 16:37
@Arturo: I mean following pseudoprime: Let $k>1$. Integer $n>1$ is pseudoprime to the base b, if n is composite and $b^n \equiv b \pmod n$. – alvoutila Sep 30 '11 at 15:00
It would be best to add the definition to the body of the question (through an edit). That way, people reading the question don't have to read through the comments to find out which one you mean. (By the way: it's a "Fermat pseudoprime"). – Arturo Magidin Sep 30 '11 at 15:57

Just raise both sides to $n-1$: $1 = 1^{n-1} \equiv (b\hat b)^{n-1} \equiv b^{n-1} \hat b^{n-1} \equiv 1 \cdot\hat b^{n-1} \equiv \hat b^{n-1} \pmod n$.

-

$\hat{b}^{n-1}\equiv \frac{1}{b^{n-1}}\pmod{n}$

$b^{n-1}\equiv 1\pmod{n}$

$\frac{1}{b^{n-1}}\equiv 1/1\equiv1\pmod{n}$

-
You can use \pmod to get (mod n) formatted properly. – TMM Sep 27 '11 at 16:01
How did you get $b^{n-1} \equiv 1 \pmod n$ from $\hat{b} \equiv \frac{1}{b^{n-1}} \pmod n$? – alvoutila Sep 28 '11 at 13:43

HINT $\rm\quad b^k\ \equiv\ 1 \iff\ (b^{-1})^k\ \equiv\ 1\$ by taking inverses.

-