What does it mean when a number 'y' is pseudoprime to base 'x'

Question

I am self learner so I don't really understand about pseudoprime to base $x$

For example, $91$ is a pseudoprime to base $3$ then is $91$ also a pseudoprime to base $2$?

thank you please explain.

edit** I did a bit research

For example, an odd composite integer $N$ will be called a Fermat pseudoprime to base $a$, if $\gcd(a, N) = 1$ and $a^{N−1} \equiv 1 \pmod{N}$.

My question is what about base $2$? Do we use the same formula like $2^{90}$ and divide by $91$? If I don't get a remainder as $1$, it is not a pseudoprime, right? But when I plugged in on the calculator, the number is too big so how can I find a remainder on calculator?

Answer 1

Yes. If nothing else is said, it is assumed that pseudoprime means Fermat's pseudoprime, i.e., a number $n$ such that $a^{n-1}\equiv1\bmod{a}$. The number $a$ is the base here, so pseudoprime w.r.t. base $3$ is a number such that $3^{n-1}\equiv1\bmod 3$.

We call it a pseudoprime, because all primes are pseudoprimes w.r.t. all bases (but not vice versa, as you realized).