HMMT 2007 U34

The Game. Eric and Greg are watching their new favorite TV show, The Price is Right. Bob Barker recently raised the intellectual level of his program, and he begins the latest installment with bidding on following question: How many Carmichael numbers are there less than 100,000? Each team is to list one nonnegative integer not greater than 100,000. Let $X$ denote the answer to Bob's question. The teams listing $N$, a maximal bid (of those submitted) not greater than $X$, will receive $N$ points, and all other teams will neither receive nor lose points. (A Carmichael number is an odd composite integer $n$ such that $n$ divides $a^{n-1}-1$ for all integers $a$ relatively prime to $n$ with $1<a<n$.)