prueba a buscar los divisores de ambos y almacena los de cada uno en un vector; despues compara ambos vectores en busca de coincidencias: siempre coincidiran en el 1...pero no se sabe si coincidiran en mas. Por tanto si haces esta busqueda controlandola con un contador inicializado en 0, tendras luego la posibilidad de poner esta condicion:
if(cont==1)
printf("\n\t%d y %d son primos relativos\n", a, b);
else
printf("\n\t%d y %d no son primos relativos\n", a, b);
espero que te sirva de algo!! ;)