There are more misleading issues :
FindInstance[EvenQ[n] && PrimeQ[n], n, Integers]
(*
==> {}
*)
These both results are in v. 7.0.1 as well as in v. 8.0.4
Edit
Even much worse :
FindInstance[OddQ[n] && PrimeQ[n], n, Integers]
(*
==> {}
*)
In general, Exists
and FindInstance
work unexpectedly with OddQ
, EvenQ
, PrimeQ
, e.g. :
Exists[n, n^2 == 9 && PrimeQ[n]] // Resolve
(*
==> False
*)
Exists[n, n^2 == 9 && OddQ[n]] // Resolve
(*
==> False
*)
Exists[n, PrimeQ[n] && n < 20] // Resolve
(*
==> False
*)
FindInstance[EvenQ[n] && n > 10, n, Integers]
(*
==>{}
*)
However
FindInstance[n > 10 && n < 20, n, Integers]
(*
==> {{n -> 11}}
*)
Exists[n, n^2 == 9 && n < 0] // Resolve
(*
==> True
*)
Exists[n, 10 < n && n < 20] // Resolve
(*
==> True
*)
Edit 2
Since those issues rather souldn't be called bugs while they still can be misleading, one may blame them on misusing of predicates inside FindInstance
and Exists
and we could expect more detailed documentation.