The most common way to test whether a large number is prime is the Miller-Rabin test. If the test says a number is composite, it's definitely composite. Otherwise, the number is very likely, but not certain, to be prime. A pseudoprime is a composite number that slips past the Miller-Rabin test. (Actually, a strong pseudoprime. More on that below.)
Miller-Rabin Test
The Miller-Rabin test is actually a sequence of tests, one for each prime number. First, you run the test associated with 2, then the test associated with 3, then the one associated with 5, etc. If we knew the smallest numbers for which these tests fail, then for smaller numbers, we know for certain that they're prime if they pass. In other words, we can turn the Miller-Rabin test for probable primes into a test for provable primes.