Mixing
Condition for roots of $x^2+xy+y^2inmathbb{F}_{q^n}[x,y]$
$begingroup$
Let $q$ be a prime number and $n$ an integer.
Is there some number theoretic condition involving the numbers $q,n$ that can tell me when is the polynomial
$$x^2+xy+y^2inmathbb{F}_{q^n}[x,y]$$
doesn't have roots other than ones with $x=y$.
abstract-algebra polynomials finite-fields
edited Jan 23 at 10:46
Adam Higgins
613113
asked Jan 23 at 9:19
user621824user621824
304
$endgroup$
add a comment |
$begingroup$
Let $q$ be a prime number and $n$ an integer.
Is there some number theoretic condition involving the numbers $q,n$ that can tell me when is the polynomial
$$x^2+xy+y^2inmathbb{F}_{q^n}[x,y]$$
doesn't have roots other than ones with $x=y$.
abstract-algebra polynomials finite-fields
edited Jan 23 at 10:46
Adam Higgins
613113
asked Jan 23 at 9:19
user621824user621824
304
$endgroup$
$begingroup$
Unless $q = 3$, I can't see how $x=y$ would produce roots, other than $x=y=0$...
$endgroup$
– Dirk Liebhold
Jan 23 at 9:32
$begingroup$
Ignoring the solution $x=y=0$. By the quadratic formula $x^{2} + xy + y^{2} = 0$ only when $x = left( frac{-1 pm sqrt{-3}}{2} right)y$. Thus $x^{2} + xy + y^{2} = 0$ as a polynomial in $mathbb{F}_{q^{n}}left[x,yright]$ has no roots if and only if $q neq 2$ and $mathbb{F}_{q^{n}}$ has no square roots of $-3$.
$endgroup$
– Adam Higgins
Jan 23 at 9:33
add a comment |
$begingroup$
Let $q$ be a prime number and $n$ an integer.
Is there some number theoretic condition involving the numbers $q,n$ that can tell me when is the polynomial
$$x^2+xy+y^2inmathbb{F}_{q^n}[x,y]$$
doesn't have roots other than ones with $x=y$.
abstract-algebra polynomials finite-fields
edited Jan 23 at 10:46
Adam Higgins
613113
asked Jan 23 at 9:19
user621824user621824
304
$endgroup$
Let $q$ be a prime number and $n$ an integer.
Is there some number theoretic condition involving the numbers $q,n$ that can tell me when is the polynomial
$$x^2+xy+y^2inmathbb{F}_{q^n}[x,y]$$
doesn't have roots other than ones with $x=y$.
abstract-algebra polynomials finite-fields
abstract-algebra polynomials finite-fields
edited Jan 23 at 10:46
Adam Higgins
613113
asked Jan 23 at 9:19
user621824user621824
304
edited Jan 23 at 10:46
Adam Higgins
613113
asked Jan 23 at 9:19
user621824user621824
304
edited Jan 23 at 10:46
Adam Higgins
613113
edited Jan 23 at 10:46
Adam Higgins
613113
edited Jan 23 at 10:46
Adam Higgins
613113
613113
asked Jan 23 at 9:19
user621824user621824
304
asked Jan 23 at 9:19
user621824user621824
304
asked Jan 23 at 9:19
user621824user621824
304
304
$begingroup$
Unless $q = 3$, I can't see how $x=y$ would produce roots, other than $x=y=0$...
$endgroup$
– Dirk Liebhold
Jan 23 at 9:32
$begingroup$
Ignoring the solution $x=y=0$. By the quadratic formula $x^{2} + xy + y^{2} = 0$ only when $x = left( frac{-1 pm sqrt{-3}}{2} right)y$. Thus $x^{2} + xy + y^{2} = 0$ as a polynomial in $mathbb{F}_{q^{n}}left[x,yright]$ has no roots if and only if $q neq 2$ and $mathbb{F}_{q^{n}}$ has no square roots of $-3$.
$endgroup$
– Adam Higgins
Jan 23 at 9:33
add a comment |
$begingroup$
Unless $q = 3$, I can't see how $x=y$ would produce roots, other than $x=y=0$...
$endgroup$
– Dirk Liebhold
Jan 23 at 9:32
$begingroup$
Ignoring the solution $x=y=0$. By the quadratic formula $x^{2} + xy + y^{2} = 0$ only when $x = left( frac{-1 pm sqrt{-3}}{2} right)y$. Thus $x^{2} + xy + y^{2} = 0$ as a polynomial in $mathbb{F}_{q^{n}}left[x,yright]$ has no roots if and only if $q neq 2$ and $mathbb{F}_{q^{n}}$ has no square roots of $-3$.
$endgroup$
– Adam Higgins
Jan 23 at 9:33
$begingroup$
Unless $q = 3$, I can't see how $x=y$ would produce roots, other than $x=y=0$...
$endgroup$
– Dirk Liebhold
Jan 23 at 9:32
$begingroup$
Unless $q = 3$, I can't see how $x=y$ would produce roots, other than $x=y=0$...
$endgroup$
– Dirk Liebhold
Jan 23 at 9:32
$begingroup$
Ignoring the solution $x=y=0$. By the quadratic formula $x^{2} + xy + y^{2} = 0$ only when $x = left( frac{-1 pm sqrt{-3}}{2} right)y$. Thus $x^{2} + xy + y^{2} = 0$ as a polynomial in $mathbb{F}_{q^{n}}left[x,yright]$ has no roots if and only if $q neq 2$ and $mathbb{F}_{q^{n}}$ has no square roots of $-3$.
$endgroup$
– Adam Higgins
Jan 23 at 9:33
$begingroup$
Ignoring the solution $x=y=0$. By the quadratic formula $x^{2} + xy + y^{2} = 0$ only when $x = left( frac{-1 pm sqrt{-3}}{2} right)y$. Thus $x^{2} + xy + y^{2} = 0$ as a polynomial in $mathbb{F}_{q^{n}}left[x,yright]$ has no roots if and only if $q neq 2$ and $mathbb{F}_{q^{n}}$ has no square roots of $-3$.
$endgroup$
– Adam Higgins
Jan 23 at 9:33
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
$textbf{EDIT:}$ As @JyrkiLahtonen pointed out in the comments, there is a much simpler argument here. $mathbb{F}_{q^{n}}$ contains a primitive third root of unity if and only if $3$ divides $q^{n} - 1$. This is because the multiplicative group of a field of size $q^{n}$ is always cyclic of order $q^{n} - 1$, and a cyclic group contains an element of prime order $p$ for every prime dividing its size. Thus $x^{2} + xy + y^{2}$ has non-zero solutions in $mathbb{F}_{q^{n}}$ whenever $q^{n} equiv 1 (text{mod} 3)$. Thus if $q equiv 1 (text{mod} 3)$ then our equation has non-zero solutions, else $q equiv 2 (text{mod} 3)$ and then $q^{n} equiv 1 (text{mod} 3)$ if and only if $n$ is even. Giving the complete solution that this equation has no non-zero solutions only when $q equiv 2 (text{mod} 3)$ and $n$ is odd.
I'm gonna leave my original attempt up in case it is at all enlightening for anyone.
Following on from my answer in the comments. Ignoring the solution $x=y=0$ which you have for every $q$, and suppose also for now that $q neq 2$. Then by the quadratic formula $x^{2} + xy + y^{2} = 0$ only when
$$
x = left( frac{-1 pm sqrt{-3}}{2} right) y,
$$
and so are interested when the field $mathbb{F}_{q^{n}}$ contains square roots of $-3$. Let us first consider the case $n=1$. I'm not sure how much elementary number theory you know, but the problem of whether or not the finite field of a prime number of elements contains the square root of a number is given the Legendre symbol. That is for $q$ a prime number, and $a$ an integer, then
$$
left( frac{a}{q} right) = left{ begin{array}{l l}
1, & text{if} a notequiv 0 (text{mod} q) text{is a quadratic residue in} mathbb{F}_{q} \
-1, & text{if} a notequiv 0 (text{mod} q) text{is not a quadratic residue in} mathbb{F}_{q} \
0, & text{if} a equiv 0 (text{mod} q)
end{array}right.
$$
where the phrase "quadratic residue" exactly means that it is the square of something in that field. Thus this problem is reduced this figuring out the value of $left( frac{-3}{q} right)$. This symbol has the following properties.
$$
left( frac{1}{q} right) = 1 text{for all primes} q,
$$
$$
left( frac{ab}{q} right) = left( frac{a}{q} right) left( frac{b}{q} right) text{for all integers} a,b text{and primes} q,
$$
$$
left( frac{a + kq}{q} right) = left(frac{a}{q}right) text{for all integers} a,k text{and primes} q.
$$
We also have quadratic reciprocity. That is, if $p,q$ are two distinct odd primes then
$$
left( frac{p}{q} right)left( frac{q}{p} right) = (-1)^{frac{(p-1)(q-1)}{4}}
$$
Using these properties we can see that (so long as $q neq 3$)
$$
left( frac{-3}{q} right) = left( frac{-1}{q} right)left( frac{3}{q} right) = (-1)^{frac{q-1}{2}}left( frac{-1}{q} right)left( frac{q}{3} right)
$$
Now using these (and maybe Euler's Criterion , one works out that
$$
left( frac{-1}{q} right) = left{ begin{array}{l l}
1, & text{if} q equiv 1 (text{mod} 4) \
-1,& text{if} q equiv 3 (text{mod} 4)
end{array}right.
$$
and
$$
left( frac{3}{q} right) = left{ begin{array}{l l}
1, & text{if} q equiv 1,11 (text{mod} 12) \
-1,& text{if} q equiv 5,7 (text{mod} 12)
end{array}right.
$$
This allows us to calculate that
$$
left( frac{-3}{q} right) = left{ begin{array}{l l}
1, & text{if} q equiv 1,7 (text{mod} 12) \
-1,& text{if} q equiv 5,11 (text{mod} 12)
end{array}right.
$$
This answers your question when $n=1$. When $n = 2$ we need to use a little bit of algebra. Again suppose that $q neq 2$, and suppose we have a case where $mathbb{F}_{q}$ does not have a square root of $-3$, then $x^{2} + 3$ is irreducible in $mathbb{F}_{q}[x]$, and so can be used to generated the field extension $mathbb{F}_{q^{2}}$ over $mathbb{F}_{q}$, thus since all finite fields of the same order are isomorphic $mathbb{F}_{q^{2}}$ must always contain a square root of $-3$. Thus any field extension of $mathbb{F}_{q^{2}}$ contains a square root of $-3$ and thus $mathbb{F}_{q^{n}}$ contains a square root of $-3$ whenever $n$ is even.
I know this isn't a complete answer, but I hope it goes some way to showing the sorts of things you need to think about when tackling this question. See if you can use these ideas to tackle the case when $n$ is not even, or when $q = 2, 3$.
answered Jan 23 at 10:20
Adam HigginsAdam Higgins
613113
$endgroup$
2
$begingroup$
This is the right idea. It might be simpler to explain that $Bbb{F}_{q^n}$ contains $sqrt{-3}$ if and only if it contains a third primitive root of unity $omega=(-1+sqrt{-3})/2$ if and only if $3mid q^n-1$ (by cyclicity of $Bbb{F}_{q^n}^*$).
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:23
1
$begingroup$
Yes. The group $Bbb{F}_{q^n}^*$ is cyclic of order $q^n-1$ even when $q=2$. And a cyclic group has elements of order three iff the order is a multiple of three.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:27
1
$begingroup$
Of course, $Bbb{F}_q[sqrt{-3}]$ is always a quadratic extension at worst, so we can also say that $omega$ is in there whenever either $qequiv1pmod3$ or $n$ is even.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:28
1
$begingroup$
Yeah I caught the case that $n$ is even. Just missed the much simpler argument about $mathbb{F}_{q^{n}}^{times}$ being cyclic, and a cyclic groups contains an element of prime order for every prime dividing the size of the group.
$endgroup$
– Adam Higgins
Jan 23 at 10:29
1
$begingroup$
@AdamHiggins But when $q=2$ we cannot use the quadratic formula ?
$endgroup$
– user621824
Jan 23 at 11:13
|
show 7 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3084256%2fcondition-for-roots-of-x2xyy2-in-mathbbf-qnx-y%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
$textbf{EDIT:}$ As @JyrkiLahtonen pointed out in the comments, there is a much simpler argument here. $mathbb{F}_{q^{n}}$ contains a primitive third root of unity if and only if $3$ divides $q^{n} - 1$. This is because the multiplicative group of a field of size $q^{n}$ is always cyclic of order $q^{n} - 1$, and a cyclic group contains an element of prime order $p$ for every prime dividing its size. Thus $x^{2} + xy + y^{2}$ has non-zero solutions in $mathbb{F}_{q^{n}}$ whenever $q^{n} equiv 1 (text{mod} 3)$. Thus if $q equiv 1 (text{mod} 3)$ then our equation has non-zero solutions, else $q equiv 2 (text{mod} 3)$ and then $q^{n} equiv 1 (text{mod} 3)$ if and only if $n$ is even. Giving the complete solution that this equation has no non-zero solutions only when $q equiv 2 (text{mod} 3)$ and $n$ is odd.
I'm gonna leave my original attempt up in case it is at all enlightening for anyone.
Following on from my answer in the comments. Ignoring the solution $x=y=0$ which you have for every $q$, and suppose also for now that $q neq 2$. Then by the quadratic formula $x^{2} + xy + y^{2} = 0$ only when
$$
x = left( frac{-1 pm sqrt{-3}}{2} right) y,
$$
and so are interested when the field $mathbb{F}_{q^{n}}$ contains square roots of $-3$. Let us first consider the case $n=1$. I'm not sure how much elementary number theory you know, but the problem of whether or not the finite field of a prime number of elements contains the square root of a number is given the Legendre symbol. That is for $q$ a prime number, and $a$ an integer, then
$$
left( frac{a}{q} right) = left{ begin{array}{l l}
1, & text{if} a notequiv 0 (text{mod} q) text{is a quadratic residue in} mathbb{F}_{q} \
-1, & text{if} a notequiv 0 (text{mod} q) text{is not a quadratic residue in} mathbb{F}_{q} \
0, & text{if} a equiv 0 (text{mod} q)
end{array}right.
$$
where the phrase "quadratic residue" exactly means that it is the square of something in that field. Thus this problem is reduced this figuring out the value of $left( frac{-3}{q} right)$. This symbol has the following properties.
$$
left( frac{1}{q} right) = 1 text{for all primes} q,
$$
$$
left( frac{ab}{q} right) = left( frac{a}{q} right) left( frac{b}{q} right) text{for all integers} a,b text{and primes} q,
$$
$$
left( frac{a + kq}{q} right) = left(frac{a}{q}right) text{for all integers} a,k text{and primes} q.
$$
We also have quadratic reciprocity. That is, if $p,q$ are two distinct odd primes then
$$
left( frac{p}{q} right)left( frac{q}{p} right) = (-1)^{frac{(p-1)(q-1)}{4}}
$$
Using these properties we can see that (so long as $q neq 3$)
$$
left( frac{-3}{q} right) = left( frac{-1}{q} right)left( frac{3}{q} right) = (-1)^{frac{q-1}{2}}left( frac{-1}{q} right)left( frac{q}{3} right)
$$
Now using these (and maybe Euler's Criterion , one works out that
$$
left( frac{-1}{q} right) = left{ begin{array}{l l}
1, & text{if} q equiv 1 (text{mod} 4) \
-1,& text{if} q equiv 3 (text{mod} 4)
end{array}right.
$$
and
$$
left( frac{3}{q} right) = left{ begin{array}{l l}
1, & text{if} q equiv 1,11 (text{mod} 12) \
-1,& text{if} q equiv 5,7 (text{mod} 12)
end{array}right.
$$
This allows us to calculate that
$$
left( frac{-3}{q} right) = left{ begin{array}{l l}
1, & text{if} q equiv 1,7 (text{mod} 12) \
-1,& text{if} q equiv 5,11 (text{mod} 12)
end{array}right.
$$
This answers your question when $n=1$. When $n = 2$ we need to use a little bit of algebra. Again suppose that $q neq 2$, and suppose we have a case where $mathbb{F}_{q}$ does not have a square root of $-3$, then $x^{2} + 3$ is irreducible in $mathbb{F}_{q}[x]$, and so can be used to generated the field extension $mathbb{F}_{q^{2}}$ over $mathbb{F}_{q}$, thus since all finite fields of the same order are isomorphic $mathbb{F}_{q^{2}}$ must always contain a square root of $-3$. Thus any field extension of $mathbb{F}_{q^{2}}$ contains a square root of $-3$ and thus $mathbb{F}_{q^{n}}$ contains a square root of $-3$ whenever $n$ is even.
I know this isn't a complete answer, but I hope it goes some way to showing the sorts of things you need to think about when tackling this question. See if you can use these ideas to tackle the case when $n$ is not even, or when $q = 2, 3$.
answered Jan 23 at 10:20
Adam HigginsAdam Higgins
613113
$endgroup$
2
$begingroup$
This is the right idea. It might be simpler to explain that $Bbb{F}_{q^n}$ contains $sqrt{-3}$ if and only if it contains a third primitive root of unity $omega=(-1+sqrt{-3})/2$ if and only if $3mid q^n-1$ (by cyclicity of $Bbb{F}_{q^n}^*$).
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:23
1
$begingroup$
Yes. The group $Bbb{F}_{q^n}^*$ is cyclic of order $q^n-1$ even when $q=2$. And a cyclic group has elements of order three iff the order is a multiple of three.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:27
1
$begingroup$
Of course, $Bbb{F}_q[sqrt{-3}]$ is always a quadratic extension at worst, so we can also say that $omega$ is in there whenever either $qequiv1pmod3$ or $n$ is even.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:28
1
$begingroup$
Yeah I caught the case that $n$ is even. Just missed the much simpler argument about $mathbb{F}_{q^{n}}^{times}$ being cyclic, and a cyclic groups contains an element of prime order for every prime dividing the size of the group.
$endgroup$
– Adam Higgins
Jan 23 at 10:29
1
$begingroup$
@AdamHiggins But when $q=2$ we cannot use the quadratic formula ?
$endgroup$
– user621824
Jan 23 at 11:13
|
show 7 more comments
$begingroup$
$textbf{EDIT:}$ As @JyrkiLahtonen pointed out in the comments, there is a much simpler argument here. $mathbb{F}_{q^{n}}$ contains a primitive third root of unity if and only if $3$ divides $q^{n} - 1$. This is because the multiplicative group of a field of size $q^{n}$ is always cyclic of order $q^{n} - 1$, and a cyclic group contains an element of prime order $p$ for every prime dividing its size. Thus $x^{2} + xy + y^{2}$ has non-zero solutions in $mathbb{F}_{q^{n}}$ whenever $q^{n} equiv 1 (text{mod} 3)$. Thus if $q equiv 1 (text{mod} 3)$ then our equation has non-zero solutions, else $q equiv 2 (text{mod} 3)$ and then $q^{n} equiv 1 (text{mod} 3)$ if and only if $n$ is even. Giving the complete solution that this equation has no non-zero solutions only when $q equiv 2 (text{mod} 3)$ and $n$ is odd.
I'm gonna leave my original attempt up in case it is at all enlightening for anyone.
Following on from my answer in the comments. Ignoring the solution $x=y=0$ which you have for every $q$, and suppose also for now that $q neq 2$. Then by the quadratic formula $x^{2} + xy + y^{2} = 0$ only when
$$
x = left( frac{-1 pm sqrt{-3}}{2} right) y,
$$
and so are interested when the field $mathbb{F}_{q^{n}}$ contains square roots of $-3$. Let us first consider the case $n=1$. I'm not sure how much elementary number theory you know, but the problem of whether or not the finite field of a prime number of elements contains the square root of a number is given the Legendre symbol. That is for $q$ a prime number, and $a$ an integer, then
$$
left( frac{a}{q} right) = left{ begin{array}{l l}
1, & text{if} a notequiv 0 (text{mod} q) text{is a quadratic residue in} mathbb{F}_{q} \
-1, & text{if} a notequiv 0 (text{mod} q) text{is not a quadratic residue in} mathbb{F}_{q} \
0, & text{if} a equiv 0 (text{mod} q)
end{array}right.
$$
where the phrase "quadratic residue" exactly means that it is the square of something in that field. Thus this problem is reduced this figuring out the value of $left( frac{-3}{q} right)$. This symbol has the following properties.
$$
left( frac{1}{q} right) = 1 text{for all primes} q,
$$
$$
left( frac{ab}{q} right) = left( frac{a}{q} right) left( frac{b}{q} right) text{for all integers} a,b text{and primes} q,
$$
$$
left( frac{a + kq}{q} right) = left(frac{a}{q}right) text{for all integers} a,k text{and primes} q.
$$
We also have quadratic reciprocity. That is, if $p,q$ are two distinct odd primes then
$$
left( frac{p}{q} right)left( frac{q}{p} right) = (-1)^{frac{(p-1)(q-1)}{4}}
$$
Using these properties we can see that (so long as $q neq 3$)
$$
left( frac{-3}{q} right) = left( frac{-1}{q} right)left( frac{3}{q} right) = (-1)^{frac{q-1}{2}}left( frac{-1}{q} right)left( frac{q}{3} right)
$$
Now using these (and maybe Euler's Criterion , one works out that
$$
left( frac{-1}{q} right) = left{ begin{array}{l l}
1, & text{if} q equiv 1 (text{mod} 4) \
-1,& text{if} q equiv 3 (text{mod} 4)
end{array}right.
$$
and
$$
left( frac{3}{q} right) = left{ begin{array}{l l}
1, & text{if} q equiv 1,11 (text{mod} 12) \
-1,& text{if} q equiv 5,7 (text{mod} 12)
end{array}right.
$$
This allows us to calculate that
$$
left( frac{-3}{q} right) = left{ begin{array}{l l}
1, & text{if} q equiv 1,7 (text{mod} 12) \
-1,& text{if} q equiv 5,11 (text{mod} 12)
end{array}right.
$$
This answers your question when $n=1$. When $n = 2$ we need to use a little bit of algebra. Again suppose that $q neq 2$, and suppose we have a case where $mathbb{F}_{q}$ does not have a square root of $-3$, then $x^{2} + 3$ is irreducible in $mathbb{F}_{q}[x]$, and so can be used to generated the field extension $mathbb{F}_{q^{2}}$ over $mathbb{F}_{q}$, thus since all finite fields of the same order are isomorphic $mathbb{F}_{q^{2}}$ must always contain a square root of $-3$. Thus any field extension of $mathbb{F}_{q^{2}}$ contains a square root of $-3$ and thus $mathbb{F}_{q^{n}}$ contains a square root of $-3$ whenever $n$ is even.
I know this isn't a complete answer, but I hope it goes some way to showing the sorts of things you need to think about when tackling this question. See if you can use these ideas to tackle the case when $n$ is not even, or when $q = 2, 3$.
answered Jan 23 at 10:20
Adam HigginsAdam Higgins
613113
$endgroup$
2
$begingroup$
This is the right idea. It might be simpler to explain that $Bbb{F}_{q^n}$ contains $sqrt{-3}$ if and only if it contains a third primitive root of unity $omega=(-1+sqrt{-3})/2$ if and only if $3mid q^n-1$ (by cyclicity of $Bbb{F}_{q^n}^*$).
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:23
1
$begingroup$
Yes. The group $Bbb{F}_{q^n}^*$ is cyclic of order $q^n-1$ even when $q=2$. And a cyclic group has elements of order three iff the order is a multiple of three.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:27
1
$begingroup$
Of course, $Bbb{F}_q[sqrt{-3}]$ is always a quadratic extension at worst, so we can also say that $omega$ is in there whenever either $qequiv1pmod3$ or $n$ is even.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:28
1
$begingroup$
Yeah I caught the case that $n$ is even. Just missed the much simpler argument about $mathbb{F}_{q^{n}}^{times}$ being cyclic, and a cyclic groups contains an element of prime order for every prime dividing the size of the group.
$endgroup$
– Adam Higgins
Jan 23 at 10:29
1
$begingroup$
@AdamHiggins But when $q=2$ we cannot use the quadratic formula ?
$endgroup$
– user621824
Jan 23 at 11:13
|
show 7 more comments
$begingroup$
$textbf{EDIT:}$ As @JyrkiLahtonen pointed out in the comments, there is a much simpler argument here. $mathbb{F}_{q^{n}}$ contains a primitive third root of unity if and only if $3$ divides $q^{n} - 1$. This is because the multiplicative group of a field of size $q^{n}$ is always cyclic of order $q^{n} - 1$, and a cyclic group contains an element of prime order $p$ for every prime dividing its size. Thus $x^{2} + xy + y^{2}$ has non-zero solutions in $mathbb{F}_{q^{n}}$ whenever $q^{n} equiv 1 (text{mod} 3)$. Thus if $q equiv 1 (text{mod} 3)$ then our equation has non-zero solutions, else $q equiv 2 (text{mod} 3)$ and then $q^{n} equiv 1 (text{mod} 3)$ if and only if $n$ is even. Giving the complete solution that this equation has no non-zero solutions only when $q equiv 2 (text{mod} 3)$ and $n$ is odd.
I'm gonna leave my original attempt up in case it is at all enlightening for anyone.
Following on from my answer in the comments. Ignoring the solution $x=y=0$ which you have for every $q$, and suppose also for now that $q neq 2$. Then by the quadratic formula $x^{2} + xy + y^{2} = 0$ only when
$$
x = left( frac{-1 pm sqrt{-3}}{2} right) y,
$$
and so are interested when the field $mathbb{F}_{q^{n}}$ contains square roots of $-3$. Let us first consider the case $n=1$. I'm not sure how much elementary number theory you know, but the problem of whether or not the finite field of a prime number of elements contains the square root of a number is given the Legendre symbol. That is for $q$ a prime number, and $a$ an integer, then
$$
left( frac{a}{q} right) = left{ begin{array}{l l}
1, & text{if} a notequiv 0 (text{mod} q) text{is a quadratic residue in} mathbb{F}_{q} \
-1, & text{if} a notequiv 0 (text{mod} q) text{is not a quadratic residue in} mathbb{F}_{q} \
0, & text{if} a equiv 0 (text{mod} q)
end{array}right.
$$
where the phrase "quadratic residue" exactly means that it is the square of something in that field. Thus this problem is reduced this figuring out the value of $left( frac{-3}{q} right)$. This symbol has the following properties.
$$
left( frac{1}{q} right) = 1 text{for all primes} q,
$$
$$
left( frac{ab}{q} right) = left( frac{a}{q} right) left( frac{b}{q} right) text{for all integers} a,b text{and primes} q,
$$
$$
left( frac{a + kq}{q} right) = left(frac{a}{q}right) text{for all integers} a,k text{and primes} q.
$$
We also have quadratic reciprocity. That is, if $p,q$ are two distinct odd primes then
$$
left( frac{p}{q} right)left( frac{q}{p} right) = (-1)^{frac{(p-1)(q-1)}{4}}
$$
Using these properties we can see that (so long as $q neq 3$)
$$
left( frac{-3}{q} right) = left( frac{-1}{q} right)left( frac{3}{q} right) = (-1)^{frac{q-1}{2}}left( frac{-1}{q} right)left( frac{q}{3} right)
$$
Now using these (and maybe Euler's Criterion , one works out that
$$
left( frac{-1}{q} right) = left{ begin{array}{l l}
1, & text{if} q equiv 1 (text{mod} 4) \
-1,& text{if} q equiv 3 (text{mod} 4)
end{array}right.
$$
and
$$
left( frac{3}{q} right) = left{ begin{array}{l l}
1, & text{if} q equiv 1,11 (text{mod} 12) \
-1,& text{if} q equiv 5,7 (text{mod} 12)
end{array}right.
$$
This allows us to calculate that
$$
left( frac{-3}{q} right) = left{ begin{array}{l l}
1, & text{if} q equiv 1,7 (text{mod} 12) \
-1,& text{if} q equiv 5,11 (text{mod} 12)
end{array}right.
$$
This answers your question when $n=1$. When $n = 2$ we need to use a little bit of algebra. Again suppose that $q neq 2$, and suppose we have a case where $mathbb{F}_{q}$ does not have a square root of $-3$, then $x^{2} + 3$ is irreducible in $mathbb{F}_{q}[x]$, and so can be used to generated the field extension $mathbb{F}_{q^{2}}$ over $mathbb{F}_{q}$, thus since all finite fields of the same order are isomorphic $mathbb{F}_{q^{2}}$ must always contain a square root of $-3$. Thus any field extension of $mathbb{F}_{q^{2}}$ contains a square root of $-3$ and thus $mathbb{F}_{q^{n}}$ contains a square root of $-3$ whenever $n$ is even.
I know this isn't a complete answer, but I hope it goes some way to showing the sorts of things you need to think about when tackling this question. See if you can use these ideas to tackle the case when $n$ is not even, or when $q = 2, 3$.
answered Jan 23 at 10:20
Adam HigginsAdam Higgins
613113
$endgroup$
$textbf{EDIT:}$ As @JyrkiLahtonen pointed out in the comments, there is a much simpler argument here. $mathbb{F}_{q^{n}}$ contains a primitive third root of unity if and only if $3$ divides $q^{n} - 1$. This is because the multiplicative group of a field of size $q^{n}$ is always cyclic of order $q^{n} - 1$, and a cyclic group contains an element of prime order $p$ for every prime dividing its size. Thus $x^{2} + xy + y^{2}$ has non-zero solutions in $mathbb{F}_{q^{n}}$ whenever $q^{n} equiv 1 (text{mod} 3)$. Thus if $q equiv 1 (text{mod} 3)$ then our equation has non-zero solutions, else $q equiv 2 (text{mod} 3)$ and then $q^{n} equiv 1 (text{mod} 3)$ if and only if $n$ is even. Giving the complete solution that this equation has no non-zero solutions only when $q equiv 2 (text{mod} 3)$ and $n$ is odd.
I'm gonna leave my original attempt up in case it is at all enlightening for anyone.
Following on from my answer in the comments. Ignoring the solution $x=y=0$ which you have for every $q$, and suppose also for now that $q neq 2$. Then by the quadratic formula $x^{2} + xy + y^{2} = 0$ only when
$$
x = left( frac{-1 pm sqrt{-3}}{2} right) y,
$$
and so are interested when the field $mathbb{F}_{q^{n}}$ contains square roots of $-3$. Let us first consider the case $n=1$. I'm not sure how much elementary number theory you know, but the problem of whether or not the finite field of a prime number of elements contains the square root of a number is given the Legendre symbol. That is for $q$ a prime number, and $a$ an integer, then
$$
left( frac{a}{q} right) = left{ begin{array}{l l}
1, & text{if} a notequiv 0 (text{mod} q) text{is a quadratic residue in} mathbb{F}_{q} \
-1, & text{if} a notequiv 0 (text{mod} q) text{is not a quadratic residue in} mathbb{F}_{q} \
0, & text{if} a equiv 0 (text{mod} q)
end{array}right.
$$
where the phrase "quadratic residue" exactly means that it is the square of something in that field. Thus this problem is reduced this figuring out the value of $left( frac{-3}{q} right)$. This symbol has the following properties.
$$
left( frac{1}{q} right) = 1 text{for all primes} q,
$$
$$
left( frac{ab}{q} right) = left( frac{a}{q} right) left( frac{b}{q} right) text{for all integers} a,b text{and primes} q,
$$
$$
left( frac{a + kq}{q} right) = left(frac{a}{q}right) text{for all integers} a,k text{and primes} q.
$$
We also have quadratic reciprocity. That is, if $p,q$ are two distinct odd primes then
$$
left( frac{p}{q} right)left( frac{q}{p} right) = (-1)^{frac{(p-1)(q-1)}{4}}
$$
Using these properties we can see that (so long as $q neq 3$)
$$
left( frac{-3}{q} right) = left( frac{-1}{q} right)left( frac{3}{q} right) = (-1)^{frac{q-1}{2}}left( frac{-1}{q} right)left( frac{q}{3} right)
$$
Now using these (and maybe Euler's Criterion , one works out that
$$
left( frac{-1}{q} right) = left{ begin{array}{l l}
1, & text{if} q equiv 1 (text{mod} 4) \
-1,& text{if} q equiv 3 (text{mod} 4)
end{array}right.
$$
and
$$
left( frac{3}{q} right) = left{ begin{array}{l l}
1, & text{if} q equiv 1,11 (text{mod} 12) \
-1,& text{if} q equiv 5,7 (text{mod} 12)
end{array}right.
$$
This allows us to calculate that
$$
left( frac{-3}{q} right) = left{ begin{array}{l l}
1, & text{if} q equiv 1,7 (text{mod} 12) \
-1,& text{if} q equiv 5,11 (text{mod} 12)
end{array}right.
$$
This answers your question when $n=1$. When $n = 2$ we need to use a little bit of algebra. Again suppose that $q neq 2$, and suppose we have a case where $mathbb{F}_{q}$ does not have a square root of $-3$, then $x^{2} + 3$ is irreducible in $mathbb{F}_{q}[x]$, and so can be used to generated the field extension $mathbb{F}_{q^{2}}$ over $mathbb{F}_{q}$, thus since all finite fields of the same order are isomorphic $mathbb{F}_{q^{2}}$ must always contain a square root of $-3$. Thus any field extension of $mathbb{F}_{q^{2}}$ contains a square root of $-3$ and thus $mathbb{F}_{q^{n}}$ contains a square root of $-3$ whenever $n$ is even.
I know this isn't a complete answer, but I hope it goes some way to showing the sorts of things you need to think about when tackling this question. See if you can use these ideas to tackle the case when $n$ is not even, or when $q = 2, 3$.
answered Jan 23 at 10:20
Adam HigginsAdam Higgins
613113
edited Jan 23 at 14:22
answered Jan 23 at 10:20
Adam HigginsAdam Higgins
613113
answered Jan 23 at 10:20
Adam HigginsAdam Higgins
613113
answered Jan 23 at 10:20
Adam HigginsAdam Higgins
613113
613113
2
$begingroup$
This is the right idea. It might be simpler to explain that $Bbb{F}_{q^n}$ contains $sqrt{-3}$ if and only if it contains a third primitive root of unity $omega=(-1+sqrt{-3})/2$ if and only if $3mid q^n-1$ (by cyclicity of $Bbb{F}_{q^n}^*$).
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:23
1
$begingroup$
Yes. The group $Bbb{F}_{q^n}^*$ is cyclic of order $q^n-1$ even when $q=2$. And a cyclic group has elements of order three iff the order is a multiple of three.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:27
1
$begingroup$
Of course, $Bbb{F}_q[sqrt{-3}]$ is always a quadratic extension at worst, so we can also say that $omega$ is in there whenever either $qequiv1pmod3$ or $n$ is even.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:28
1
$begingroup$
Yeah I caught the case that $n$ is even. Just missed the much simpler argument about $mathbb{F}_{q^{n}}^{times}$ being cyclic, and a cyclic groups contains an element of prime order for every prime dividing the size of the group.
$endgroup$
– Adam Higgins
Jan 23 at 10:29
1
$begingroup$
@AdamHiggins But when $q=2$ we cannot use the quadratic formula ?
$endgroup$
– user621824
Jan 23 at 11:13
|
show 7 more comments
2
$begingroup$
This is the right idea. It might be simpler to explain that $Bbb{F}_{q^n}$ contains $sqrt{-3}$ if and only if it contains a third primitive root of unity $omega=(-1+sqrt{-3})/2$ if and only if $3mid q^n-1$ (by cyclicity of $Bbb{F}_{q^n}^*$).
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:23
1
$begingroup$
Yes. The group $Bbb{F}_{q^n}^*$ is cyclic of order $q^n-1$ even when $q=2$. And a cyclic group has elements of order three iff the order is a multiple of three.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:27
1
$begingroup$
Of course, $Bbb{F}_q[sqrt{-3}]$ is always a quadratic extension at worst, so we can also say that $omega$ is in there whenever either $qequiv1pmod3$ or $n$ is even.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:28
1
$begingroup$
Yeah I caught the case that $n$ is even. Just missed the much simpler argument about $mathbb{F}_{q^{n}}^{times}$ being cyclic, and a cyclic groups contains an element of prime order for every prime dividing the size of the group.
$endgroup$
– Adam Higgins
Jan 23 at 10:29
1
$begingroup$
@AdamHiggins But when $q=2$ we cannot use the quadratic formula ?
$endgroup$
– user621824
Jan 23 at 11:13
2
2
$begingroup$
This is the right idea. It might be simpler to explain that $Bbb{F}_{q^n}$ contains $sqrt{-3}$ if and only if it contains a third primitive root of unity $omega=(-1+sqrt{-3})/2$ if and only if $3mid q^n-1$ (by cyclicity of $Bbb{F}_{q^n}^*$).
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:23
$begingroup$
This is the right idea. It might be simpler to explain that $Bbb{F}_{q^n}$ contains $sqrt{-3}$ if and only if it contains a third primitive root of unity $omega=(-1+sqrt{-3})/2$ if and only if $3mid q^n-1$ (by cyclicity of $Bbb{F}_{q^n}^*$).
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:23
1
1
$begingroup$
Yes. The group $Bbb{F}_{q^n}^*$ is cyclic of order $q^n-1$ even when $q=2$. And a cyclic group has elements of order three iff the order is a multiple of three.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:27
$begingroup$
Yes. The group $Bbb{F}_{q^n}^*$ is cyclic of order $q^n-1$ even when $q=2$. And a cyclic group has elements of order three iff the order is a multiple of three.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:27
1
1
$begingroup$
Of course, $Bbb{F}_q[sqrt{-3}]$ is always a quadratic extension at worst, so we can also say that $omega$ is in there whenever either $qequiv1pmod3$ or $n$ is even.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:28
$begingroup$
Of course, $Bbb{F}_q[sqrt{-3}]$ is always a quadratic extension at worst, so we can also say that $omega$ is in there whenever either $qequiv1pmod3$ or $n$ is even.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 10:28
1
1
$begingroup$
Yeah I caught the case that $n$ is even. Just missed the much simpler argument about $mathbb{F}_{q^{n}}^{times}$ being cyclic, and a cyclic groups contains an element of prime order for every prime dividing the size of the group.
$endgroup$
– Adam Higgins
Jan 23 at 10:29
$begingroup$
Yeah I caught the case that $n$ is even. Just missed the much simpler argument about $mathbb{F}_{q^{n}}^{times}$ being cyclic, and a cyclic groups contains an element of prime order for every prime dividing the size of the group.
$endgroup$
– Adam Higgins
Jan 23 at 10:29
1
1
$begingroup$
@AdamHiggins But when $q=2$ we cannot use the quadratic formula ?
$endgroup$
– user621824
Jan 23 at 11:13
$begingroup$
@AdamHiggins But when $q=2$ we cannot use the quadratic formula ?
$endgroup$
– user621824
Jan 23 at 11:13
|
show 7 more comments
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3084256%2fcondition-for-roots-of-x2xyy2-in-mathbbf-qnx-y%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Unless $q = 3$, I can't see how $x=y$ would produce roots, other than $x=y=0$...
$endgroup$
– Dirk Liebhold
Jan 23 at 9:32
$begingroup$
Ignoring the solution $x=y=0$. By the quadratic formula $x^{2} + xy + y^{2} = 0$ only when $x = left( frac{-1 pm sqrt{-3}}{2} right)y$. Thus $x^{2} + xy + y^{2} = 0$ as a polynomial in $mathbb{F}_{q^{n}}left[x,yright]$ has no roots if and only if $q neq 2$ and $mathbb{F}_{q^{n}}$ has no square roots of $-3$.
$endgroup$
– Adam Higgins
Jan 23 at 9:33