Lets take Beal's $1,000,000
I'm being pathetically lazy (pun intended), but why not... seems to fulfill the rules.

Haskell, 204

import Control.Monad
import Control.Monad.Omega
main=print.filter(\[(a,x),(b,y),(c,z)] 
 -&gt;and$(a^x+b^y==c^z):zipWith(((&gt;1).).gcd)[a,b,c][b,c,a])
 .runOmega$mapM(\_-&gt;liftM2(,)(each[1..])$each[3..])"123"


This prints1 all combinations which fulfill the counterexample property. I used the control-monad-omega package for diagonalising ℕ6... might be considered library-cheating. But seeing as someone will later post an APL answer where all this stuff is built into the language (or isn't it?), I don't give too much about it...

Of course, the program is way too slow (naïve exhaustion, and linked-lists as data structure) to be expectable of actually yielding a counterexample, but Haskell itself can actually achieve decent performance.



1Since it prints the tuples in list format, i.e. in one line, you need to switch your terminal's buffering off or you won't see when a result comes in. Alternatively, you can replace print with mapM_ print so you get a newline after each result, flushing a line-buffered terminal.

To test the program, change each[3..] to each[2..], then you'll simply get all non-coprime pythagorean tuples as result.