I am reading "The Design and Analysis of Computer Algorithms" by Aho, Hopcroft, Ullman.
Without a proof, the authors wrote the following proposition held.
Let $R$ be any commutative ring with $1$.
Let $\omega$ be an element of $R$ which satisfies the following three conditions:
- $\omega\ne 1.$
- $\omega^n=1.$
- $1+\omega^p+(\omega^p)^2+\dots+(\omega^p)^{n-1}=0$ for all $p\in\{1,\dots,n-1\}.$
Assume that $n\cdot 1$ has a multiplicative inverse.
Assume that there exists $\psi\in R$ such that $\psi^2 = \omega$.Then, $\psi^n=-1$.
My first question is the following:
Let $R$ be any commutative ring with $1$ which is not an integral domain.
Then, does the above proposition really hold?
My second qutstion is the following:
Let $R$ be any commutative ring with $1$ which is an integral domain.
Then, does the above proposition hold?
My attempt is here when $R$ is an integral domain:
When $n$ is even, $0=\omega^n-1=(\omega^{\frac{n}{2}}-1)(\omega^{\frac{n}{2}}+1).$
So, $\omega^{\frac{n}{2}}=1$ or $\omega^{\frac{n}{2}}=-1$.
If $\omega^{\frac{n}{2}}=1$, then $n = 1+\omega^{\frac{n}{2}}+(\omega^{\frac{n}{2}})^2+\dots+(\omega^{\frac{n}{2}})^{n-1}=0$.
By assumption, $n\cdot 1$ has a multiplicative inverse. So $n\cdot 1\ne 0$.
This is a contradiction.
So, $\omega^{\frac{n}{2}}=-1$.
So, $\psi^n=(\psi^2)^{\frac{n}{2}}=\omega^{\frac{n}{2}}=-1.$
When $n$ is odd, $\cdots$
- My observations when $R$ is an integral domain:
Assume that $n\cdot 1 \ne 0.$
Let $\omega$ be an element of $R$ which satisfies the following three conditions:
- $\omega\ne 1.$
- $\omega^n=1.$
- $1+\omega^p+(\omega^p)^2+\dots+(\omega^p)^{n-1}=0$ for all $p\in\{1,\dots,n-1\}.$
Then $\omega$ satisfies $\omega^p\ne 1$ for all $p\in\{1,\dots,n-1\}$ and $\omega^n=1.$
Proof:
If $\omega^p=1$ for some $p\in\{1,\dots,n-1\}$, then $n\cdot 1=1+\omega^p+(\omega^p)^2+\dots+(\omega^p)^{n-1}=0$ by 3.
This contradicts the assumption $n\cdot 1\ne 0$.
So, $\omega^p\ne 1$ for all $p\in\{1,\dots,n-1\}$ and $\omega^n=1$.
Assume that $\omega^p\ne 1$ for all $p\in\{1,\dots,n-1\}$ and $\omega^n=1$.
Then the followings hold:
- $\omega\ne 1.$
- $\omega^n=1.$
- $1+\omega^p+(\omega^p)^2+\dots+(\omega^p)^{n-1}=0$ for all $p\in\{1,\dots,n-1\}.$
Proof:
Let $p\in\{1,\dots,n-1\}$.
$0 = 1^p - 1 = (\omega^n)^p -1= (\omega^p)^n -1= (\omega^p-1)(1+\omega^p+(\omega^p)^2+\dots+(\omega^p)^{n-1})$.
Since $\omega^p\ne 1$ and $R$ is an integral domain, $1+\omega^p+(\omega^p)^2+\dots+(\omega^p)^{n-1}=0.$
Assume that $\omega^p\ne 1$ for all $p\in\{1,\dots,n-1\}$ and $\omega^n=1$.
Let $\psi$ be an element of $R$ such that $\psi^2=\omega$.
Then, $\psi^n = 1$ or $\psi^n = -1$.
If $\psi^n = 1$, then $\psi^p\ne 1$ for all $p\in\{1,\dots,n-1\}$.
Proof:
$0=\omega^n-1=\psi^{2n}-1=(\psi^n-1)(\psi^n+1)$.
Since $R$ is an integral domain, $\psi^n = 1$ or $\psi^n = -1$.
If $\psi^n=1$ and $\psi^p=1$ for some $p\in\{1,\dots,n-1\}$, then $1=\psi^{2p}=\omega^p$.
This is a contradiction.