Prove that 91 is pseudoprime to base b.

Question

I'm quite stuck on this question and would really appreciate anyone who's able to explain the way it's worked out to me!

The full question is 'Let b be an integer coprime to 91. Assume that b is a quadratic residue modulo 91. Prove that 91 is pseudoprime to base b'.

Any help would be much appreciated! I've been staring at this question for a while now.

Do you need a value for p? It doesn't state one.... – Jun 01 '20 at 13:33 — , Jun 01 '20 at 13:33
Well, what's it doing there then? – TonyK Jun 01 '20 at 13:35 — TonyK, Jun 01 '20 at 13:35

score 1 · Answer 1 · answered Jun 01 '20 at 13:34

1

If $b\equiv x^2\bmod91$, then $b\equiv x^2\bmod 13$ and $7$.

Therefore, $b^6\equiv x^{12}\equiv1\bmod13$ and $7$, assuming $b$ is coprime to $13$ and $7$.

Therefore, $b^6\equiv1\bmod 91$.

Therefore $b^{90}\equiv 1\bmod 91$; i.e., $91$ is a pseudoprime to base $b$.

answered Jun 01 '20 at 13:34

J. W. Tanner

Well, if $91|b-x^2$, then $13|b-x^2$ and $7|b-x^2$, because $13|91$ and $7|91$ (divisibility is a transitive relation); $x^{12}\equiv1 \bmod 13$ and $7$ assuming $x$ is coprime to $13$ and $7$ is due to Fermat's little theorem – J. W. Tanner Jun 01 '20 at 13:38

1 Answers1