A graph is -decomposable if can be decomposed into subgraphs, each of which is isomorphic to . A graph is a greatest common divisor of two graphs and if is a graph of maximum size such that both and are -decomposable. The greatest common divisor index of a graph of size is the greatest positive integer for which there exist graphs and , both of size at least , such that is the unique greatest common divisor of and . If no such integer exists, the greatest common divisor index of is infinite. Several graphs are shown to have infinite greatest common divisor index, including matchings, stars, small paths, and the cycle . It is shown for an edge-transitive graph of order with vertex independence number less than that if is an -decomposable graph of sufficiently large size, then is also decomposable. From this it follows that each such edge-transitive graph has finite index. In particular, all complete graphs of order at least are shown to have greatest common divisor index and the greatest common divisor index of the odd cycle lies between and . The graphs , , have infinite or finite index depending on the value of ; in particular, has infinite index if and index if .