Counting Fermat witnesses and liars
I think it would be worth explaining the terms you are using : what is a liar ? what is a witness ?

Except for that, the code is well presented and well tested (so many thanks for that).

Making code more simple in fermat_witness

You could easily rewrite fermat_witness: return pow(test_num, possible_prime-1) % possible_prime != 1.

Making code more simple in fermat_witness_liar_count

You could also rewrite fermat_witness_liar_count with less variables because you can get rid of liar_count by writing :

if witness_count != 0:
    return witness_count, temp_liar_count
return 0, 0


You can also get rid of temp_liar_count by writing :

witness_count = 0
for test_num in range(1, possible_prime):
    if fermat_witness(test_num, possible_prime):
        witness_count += 1
if witness_count != 0:
    return witness_count, possible_prime - witness_count - 1
return 0, 0


Then, you can use the fact that non-zero integers are considered as true values and try to write a single return:

return witness_count, possible_prime - witness_count - 1 if witness_count else 0


Finally, if you want to count, you can use sum and simply write :

witness_count = sum(1 for test_num in range(1, possible_prime)
    if fermat_witness(test_num, possible_prime))


The whole function becomes :

witness_count = sum(1 for test_num in range(1, possible_prime)
    if fermat_witness(test_num, possible_prime))

# When there are Fermat witnesses, all test_nums that arent are Fermat liars
return witness_count, possible_prime - witness_count - 1 if witness_count else 0


pow is a pow-erful builtin

pow handles what you are trying to do in a more efficient way :


  if z is present, return x to the power y, modulo z (computed more
  efficiently than pow(x, y) % z)


fermat_witness becomes :

return pow(test_num, possible_prime-1, possible_prime) != 1


Then, I guess more mathematical optimisations could be performed but I haven't tried at all.