# Thread: Result of Euclidean division

1. Hello!!!

I have applied a lot of times the euclidean division of $x^6-1$ with $x^2- \alpha^{a+1} (\alpha+1)x+ \alpha^{2a+3}, a \geq 0$, $\alpha$ a primitive $6$-th root of unity. But I don't get the right result...

We are over $\mathbb{F}_7$.

I got that $x^6-1=(x^2- \alpha^{a+1}(\alpha+1) x+ \alpha^{2a+3}) (x^4+ \alpha^{a+1} (\alpha+1) x^3+ \alpha^{2a+2}[(\alpha+1)^2- \alpha] x^2+ \alpha^{3a+3}(\alpha+1)[\alpha^2+1]x+ \alpha^{4a}[\alpha^4(\alpha+1)^2(\alpha^2+1)-[(\alpha+1)^2- \alpha]])+ \alpha^{5a}(\alpha+1)[\alpha^2+ \alpha+1+\alpha^5]x-2 \alpha^4-2\alpha^3-2 \alpha^8-\alpha^7+\alpha^4+\alpha^3-1$.

But the rest should be $0$. Have I done something wrong?

2. Originally Posted by evinda
Hello!!!

I have applied a lot of times the euclidean division of $x^6-1$ with $x^2- \alpha^{a+1} (\alpha+1)x+ \alpha^{2a+3}, a \geq 0$, $\alpha$ a primitive $6$-th root of unity. But I don't get the right result...

We are over $\mathbb{F}_7$.

I got that $x^6-1=(x^2- \alpha^{a+1}(\alpha+1) x+ \alpha^{2a+3}) (x^4+ \alpha^{a+1} (\alpha+1) x^3+ \alpha^{2a+2}[(\alpha+1)^2- \alpha] x^2+ \alpha^{3a+3}(\alpha+1)[\alpha^2+1]x+ \alpha^{4a}[\alpha^4(\alpha+1)^2(\alpha^2+1)-[(\alpha+1)^2- \alpha]])+ \alpha^{5a}(\alpha+1)[\alpha^2+ \alpha+1+\alpha^5]x-2 \alpha^4-2\alpha^3-2 \alpha^8-\alpha^7+\alpha^4+\alpha^3-1$.

But the rest should be $0$. Have I done something wrong?
Hey evinda!!

Did you take into account that for instance $\alpha^3 = -1$?
And that $\alpha^5 = \overline \alpha$?
And that $\alpha + \overline \alpha = 1$?

Oh, and how about writing it as:
$$\frac{x^6-1}{x^2- \alpha^{a+1} (\alpha+1)x+ \alpha^{2a+3}} = \frac{(x-1)(x+1)(x^2-x+1)(x^2+x+1)}{(x-\alpha^{a+1})(x-\alpha^{a+2})} = \frac{(x-1)(x+1)(x-\alpha)(x-\overline\alpha)(x-\alpha^2)(x-\overline\alpha^2)}{(x-\alpha^{a+1})(x-\alpha^{a+2})}$$

Now we can see that for instance with $a=1$, it simplifies to:
$$(x-1)(x-\alpha)(x-\overline\alpha)(x-\overline\alpha^2) = (x-1)(x^2-x+1)(x-\overline\alpha^2)$$
Btw, that is not in $\mathbb F_7$ is it?

Originally Posted by I like Serena

Did you take into account that for instance $\alpha^3 = -1$?

And that $\alpha + \overline \alpha = 1$?
How do we get these relations?

Originally Posted by I like Serena
Oh, and how about writing it as:
$$\frac{x^6-1}{x^2- \alpha^{a+1} (\alpha+1)x+ \alpha^{2a+3}} = \frac{(x-1)(x+1)(x^2-x+1)(x^2+x+1)}{(x-\alpha^{a+1})(x-\alpha^{a+2})} = \frac{(x-1)(x+1)(x-\alpha)(x-\overline\alpha)(x-\alpha^2)(x-\overline\alpha^2)}{(x-\alpha^{a+1})(x-\alpha^{a+2})}$$
Why does it hold that $(x-1)(x+1)(x^2-x+1)(x^2+x+1)=(x-1)(x+1)(x-\alpha)(x-\overline\alpha)(x-\alpha^2)(x-\overline\alpha^2)$ ?

Originally Posted by I like Serena
Now we can see that for instance with $a=1$, it simplifies to:
$$(x-1)(x-\alpha)(x-\overline\alpha)(x-\overline\alpha^2) = (x-1)(x^2-x+1)(x-\overline\alpha^2)$$
Btw, that is not in $\mathbb F_7$ is it?
Why isn't this in $\mathbb{F}_7$ ?

4. Originally Posted by evinda
How do we get these relations?
Since $\alpha$ is a roots of unity.
The solutions are $1, \alpha, \alpha^2, ..., \alpha^5$.
It means that we can write:
$$x^6 - 1 = (x-1)(x-\alpha)(x-\alpha^2)...(x-\alpha^5)$$
We can verify that the stated equality holds.

Quote:
Why isn't this in $\mathbb{F}_7$ ?
Isn't $\mathbb F_7 = \{0,1,2,3,4,5,6\}$?
The primitive root of unity $\alpha$ is not in there...

Originally Posted by I like Serena
Since $\alpha$ is a roots of unity.
I thought that we get from the fact that $\alpha$ is a $6$-th root of unity that $\alpha^6=1$ and $\alpha^i \neq \alpha^j, i \neq j, 1 \leq i, j \leq 6$.

Originally Posted by I like Serena

Isn't $\mathbb F_7 = \{0,1,2,3,4,5,6\}$?
The primitive root of unity $\alpha$ is not in there...
If we take a field of the form $\mathbb{F}_{7^m}$ for some $m \in \mathbb{N}$ ?

6. Originally Posted by evinda
I thought that we get from the fact that $\alpha$ is a $6$-th root of unity that $\alpha^6=1$ and $\alpha^i \neq \alpha^j, i \neq j, 1 \leq i, j \leq 6$.

If we take a field of the form $\mathbb{F}_{7^m}$ for some $m \in \mathbb{N}$ ?
Hold on!

Actually, $\mathbb{F}_{7}$ does have a primitive 6-th root of unity.
We have either $\alpha=3$ or $\alpha=4$.
Note that the numbers $3^k$ are all distinct for $1 \le k \le 6$, and $3^6=1$.

Btw, we still get $\alpha^3 = -1$, since it's a primitive 2-nd root of unity.

Originally Posted by I like Serena

Actually, $\mathbb{F}_{7}$ does have a primitive 6-th root of unity.
We have either $\alpha=3$ or $\alpha=4$.
How did you deduce this?

Originally Posted by I like Serena

Note that the numbers $3^k$ are all distinct for $1 \le k \le 6$, and $3^6=1$.
I see...

Originally Posted by I like Serena

Btw, we still get $\alpha^3 = -1$, since it's a primitive 2-nd root of unity.
Why is it a 2-nd root of unity?

8. Originally Posted by evinda
How did you deduce this?

I see...
By checking all numbers in $\mathbb F_7$, to see if they satisfied the criterion for a primitive root of unity.

Quote:
Why is it a 2-nd root of unity?
Because $(\alpha^3)^2 = 1$, so $x=\alpha^3$ satisfies $x^2=1$.
We also know that $\alpha^3 \ne 1$, which follows from the fact that $\alpha$ is a primitive 6-th root of unity.
And finally, because the only numbers that satisfy $x^2=1$ are $x=\pm 1$.

Originally Posted by I like Serena
By checking all numbers in $\mathbb F_7$, to see if they satisfied the criterion for a primitive root of unity.

Because $(\alpha^3)^2 = 1$, so $x=\alpha^3$ satisfies $x^2=1$.
We also know that $\alpha^3 \ne 1$, which follows from the fact that $\alpha$ is a primitive 6-th root of unity.
And finally, because the only numbers that satisfy $x^2=1$ are $x=\pm 1$.
Ah I see... Do we use this at my initial calculations or at the calulations that you did?

10. Originally Posted by evinda
Ah I see... Do we use this at my initial calculations or at the calculations that you did?
Well... if we divide $x^6-1$ by $x-\alpha^{a+1}$ first, we get:
$$\frac{x^6-1}{x-\alpha^{a+1}} = x^5 + \alpha^{a+1}x^4 + \alpha^{2(a+1)}x^3 + \alpha^{3(a+1)}x^2 + \alpha^{4(a+1)}x + \alpha^{5(a+1)} +\frac{\alpha^{6(a+1)} - 1}{x-\alpha^{a+1}}$$
Note that the remainder term $\alpha^{6(a+1)} - 1=0$, because $\alpha$ is a 6-th root of unity.

That leaves dividing what we found by $x-\alpha^{a+2}$...

Alternatively, if I redo your calculation, I get the same terms for $x^4$, $x^3$, and $x^2$, but a different term for $x$.
Mine is $\alpha^{a+1}(\alpha^{2a+2} - 2\alpha^{a+2}) x = \alpha^{2a+3}(\alpha^a - 2)x$.
Oh, and my final remainder term has a constant of $1+\alpha+\alpha^2+\alpha^3+\alpha^4+\alpha^5$, which is indeed $0$. It suggests that my calculation is correct.

Perhaps there is a mistake in your calculation.