pseudo-primality and test of Solovay-Strassen

If you know the prime factorization of $n=p_1 ^{d_1} \dots p_N ^{d_N}$, then the question has already been asked and answered: the number you are looking for is $\prod \limits _{k=1} ^N \gcd (n-1, p_k -1)$.

If you do not know the factorization of $n$, then Pomerance has obtained a lower bound given by $\exp (\log x) ^{\frac E {E+1} - \varepsilon}$ (see section 4) and an upper bound given by $\frac x {\sqrt {\exp \frac {\log x \log \log \log x} {\log \log x}}}$. These results are also cited by Erdős in an article from 1988. (While consulting them, keep in mind that $\log = \log _2$ and that in Pomerance's second article $\log_2 = \log \log$ and $\log_3 = \log \log \log$, a very uninspired notation. These estimates, though, are probably not what you have in mind for your students.)