IP Myth 21. Determining if Ax=b has an integer solution is NP-complete for integral A, b.
My thanks to Heiko Vogel for pointing this out. The key to this myth is that there are no bounds on x. (If we restrict x to be nonnegative, we have the standard form of a linear integer program, which is NP-complete.) This is the problem of solving linear diophantine equations for which Brown provides simple, polynomial-time algorithms. Also, see Aardal, Hurkens, and Lenstra.
I’d like to add that this problem might be NP-complete. However, this would imply that P=NP, so it’s not very likely.