equation x*i1 +k = y*i2+m (Or x*i1 -y*i2 = m -k) Where 0<=i1, i2 <n and i1 != i2. If GCD(x,y) divides (m-k), then there may exist some dependency in the loop statement s1 and s2. If GCD(x,y) does not divide (m-k) then both statements are independent and can be executed at parallel. Similarly this test is conducted for all statements present in a given loop. A concrete example source code in C would appear as: for (int i=0; i<100; i++) { s1 a[2*i] = b[i]; s2 c[i] = a[4*i+1]; } The GCD of (2,4) is 2 and dividend is 1. As 2 can not divide 1 properly (leaving remainder zero), there is no dependency between s1 and s2 and various other loop transformation methods can be applied. See also Automatic parallelization Banerjee test Dependence analysis Loop dependence analysis References Advanced Compiler Design and Implementation by Steven S Muchnick Compilers