AMC 12 Mock Exam 1 Problem 11

Since $40=8\cdot5$ with $\gcd(8,5)=1$, we need $8\mid n^2-1$ and $5\mid n^2-1$.

Mod $8$: an odd number has $n^2\equiv1\pmod 8$, while an even number has $n^2\equiv0$ or $4\pmod 8$. So $n$ must be odd.

Mod $5$: $5\mid(n-1)(n+1)$ iff $n\equiv\pm1\pmod5$.

By the Chinese Remainder Theorem the valid $n$ form $4\cdot2=8$ residue classes modulo $40$, namely $1,9,11,19,21,29,31,39$. The numbers $1$ through $80$ contain $2\cdot8=16$ valid values, and among $81,\dots,100$ (which are $\equiv1,\dots,20$) the valid ones are $81,89,91,99$. Total: $16+4=\boxed{20}$.