3
$\begingroup$

For which values of $n$, does the finite field $\mathbb{F}_{5^{n}}$ with $5^{n}$ elements contain a non-trivial $93$rd root of unity?

I don't know how to find the value of $n$.

2 Answers 2

11

In this answer, I assume that the adjective non-trivial in the OP's question modifies the entire noun phrase 93rd root of unity and not just root of unity and thus "nontrivial 93rd root of unity" means an element of multiplicative order $93$ and excludes the elements of multiplicative orders $3$ and $31$ which also happen to be included in the $93$rd roots of unity.

$\mathbb F_{5^n}$ contains an element of multiplicative order $93$ if and only if $93$ is a divisor of $5^n-1$, that is, $5^n \equiv 1\bmod 93$. The brute force way of finding the smallest value of $n$ is to just calculate the values of $5^1$, $5^2$, $5^3$, $\ldots$ modulo $93$ until you find the answer. So we proceed as follows: $$\begin{align*} 5^0 & \equiv 1 \bmod 93\\ 5^1 &\equiv 5 \bmod 93\\ 5^2 &\equiv 25 \bmod 93\\ 5^3 = 125 &\equiv 32 \bmod 93\\ 5^4 \equiv 5\times 32 =160 &\equiv 67 \bmod 93\\ 5^5 \equiv 5\times 67 = 335 &\equiv 56 \bmod 93\\ 5^6 \equiv 5\times 56 = 280 &\equiv 1 \bmod 93\\ \end{align*}$$ Thus, $\mathbb F_{5^6}$ is the smallest field of characteristic $5$ that contains an element of multiplicative order $93$. For the benefit of @suchandaadhikari, we continue the above calculation $$\begin{align*} 5^7 \equiv 5\times 1 &\equiv 5 \bmod 93\\ 5^8 \equiv 5\times 5 &\equiv 25 \bmod 93\\ 5^9 \equiv 5\times 25 &\equiv 32 \bmod 93\\ 5^{10} \equiv 5\times 32 =160 &\equiv 67 \bmod 93\\ 5^{11} \equiv 5\times 67 = 335 &\equiv 56 \bmod 93\\ 5^{12} \equiv 5\times 56 = 280 &\equiv 1 \bmod 93\\ \end{align*}$$ and then unforgivably (that is, without ever mentioning the principle of mathematical induction) jump to the conclusion that $5^n-1$ is divisible by $93$ if and only if $n$ is a multiple of $6$.

Those wishing to include $3$rd and $31$st roots of unity among the nontrivial $93$rd roots of unity can carry out similar calculations of discover that $n$ must be a multiple of $2$ for $\mathbb F_{5^n}$ to include a cube root of unity while $n$ must be a multiple of $3$ to include a $31$st root of unity. So, the conclusion would be that $n$ must be a multiple of $2$ or $3$ for $\mathbb F_{5^n}$ to include a non-trivial $93$rd root of unity. Note that or is used here in its mathematical meaning which allows for both conditions to hold simultaneously (which makes $n$ a multiple of $6$) instead of its meaning in ordinary English where "$A$ or $B$" means that either $A$ holds or $B$ holds, but not both unless "or both" is appended to the phrase "$A$ or $B$" to explicitly allow the possibility that both $A$ and $B$ might hold.

  • 0
    Thanks! Now i can understand this properly.2012-05-24
  • 1
    It might also be worth mentioning that nobody knows how to do this in a way that is significantly better than brute-force enumeration.2012-05-24
  • 0
    thanks for the help on the question. but it is also true that 'n' could also be any other multiple of 6, like 12, 18 and so on... all of these have the similar property, right?2012-10-29
  • 1
    @Ram Yes, as I said at the very end of my answer "... $\mathbb F_{5^n}$ contains an element of multiplicative order $93$ if and only of $n$ is an integer multiple of $6$." This means that $12, 18 ,24, \ldots$, all multiples of $6$, also have the same property exactly as you say.2012-10-30
  • 0
    Why is "a non-trivial 93rd root of unity" an element of order 93? I'd say that any root of unity that is not 1 is non-trivial, in particular, elements of order 3 and 31 should also work.2012-12-05
  • 1
    @Phira I agree, but many non-mathematicians who use finite fields in their work (e.g. engineers studying coding theory) tend to use _non-trivial_ to mean _primitive_ and that is the way I interpreted the question. My answer very carefully avoided both words entirely and answered what I believe was intended: "For which values of $n$ does $\mathbb F_{5^n}$ contain an element of multiplicative order $93$?"2012-12-05
8

I'll give you one direction - see if you can do the other on your own.

Suppose we have a non-trivial $93$rd root of unity $\zeta\in\mathbb{F}_{5^n}$. Then $\zeta$ would, of course, have to be non-zero. So $\zeta\in\mathbb{F}_{5^n}^\times$, and by definition we have that the order of $\zeta$ as an element of the multiplicative group $\mathbb{F}_{5^n}^\times$ is $93$. By Lagrange's theorem, this is only possible if $93\mid 5^n-1$. Note that $93\mid 5^n-1$ if and only if $3\mid 5^n-1$ and $31\mid 5^n-1$, because $93=3\cdot 31$ is the prime factorization of $93$.

When does that happen? Look at the following table: $$\begin{array}{c|c|c|c|c|c|c} n & 0 & 1 & 2 & 3 & 4 & 5 & 6\\ \hline 5^n & 1 & 5 & 25 & 125 & 625 & 3125 & 15625\\ \hline \text{mod }3 & 1 & 2 & 1 & 2 & 1 & 2 & 1 \\ \hline \text{mod }31 & 1 & 5 & 25 & 1 & 5 & 25 & 1 \end{array}$$ The period of $5^n$ modulo $3$ is $2$, and the period of $5^n$ modulo $31$ is $3$ (the proof that this period holds for all $n$ is straightforward). Thus, the $n$ for which $5^n\equiv 1\bmod 3$ and $5^n\equiv 1\bmod 31$ (i.e. the $n$ for which $3\mid 5^n-1$ and $31\mid 5^n-1$) are those $n$ such that $2\mid n$ and $3\mid n$, i.e. the $n$ which are multiples of $6$.

Ok, so we've established that, if there is a primitive $93$rd root of unity in $\mathbb{F}_{5^n}$, then it must be the case that $6\mid n$.

Is the converse true? Try to work it out yourself.

  • 1
    Zev - this is serious. We both need to go to sleep.2012-05-23
  • 2
    Haha ***neverrrrr***2012-05-23
  • 2
    +1 Do observe that the third cyclotomic polynomial $$\phi_3(x)=x^2+x+1$$ is quadratic, so even in characteristic zero you never need higher than a quadratic extension to include primitive cubic roots of unity!2012-05-23