A theory of equivalent integer programs is developed that shows that every all-integer integer programming problem is equivalent to infinitely many other integer programming problems. The equivalence is such that the solution to any one problem in the equivalence class determines the solution to every other problem in the class. Procedures to construct certain canonical problems in each equivalence class are described. The relationship of this theory to computational algorithms is discussed.