Ya he corregido las erratas. Gracias una vez más por avisar. En cuanto a la posibilidad de encontrar un algoritmo de división euclídea en enteros ciclotómicos basado en la división euclídea de polinomios, que es en esencia lo que planteas, es poco probable que sea posible, precisamente por lo que tú mismo apuntas: el grado y la norma no tienen nada que ver. La división euclídea se complica cuando aumenta el primo, y a partir de cierto primo deja de existir. No parece que haya algoritmos sencillos para dividir enteros ciclotómicos de orden 5 y mucho menos para orden 7 o superiores.
La buena noticia es que en realidad nunca vamos a tener que dividir enteros ciclotómicos en la práctica. Sólo vamos a usar la existencia de división euclídea para justificar que los enteros ciclotómicos tienen factorización única, que es un resultado teórico. Para el UTF necesitamos poco más, porque la demostración es una reducción al absurdo, por lo que en ella intervienen pocos cálculos con números concretos, pero puestos a manejarse con enteros ciclotómicos, el problema práctico es encontrar primos, no encontrar cocientes y restos euclídeos.