[eximius]

http://en.m.wikipedia.org/wiki/Carmichael_number

[contravariant]

I suppose that would work, although with a factor of 3 more than 1/3 of all inputs are not relatively prime so in those cases it would fail anyway.