# Fixed Points of the Dickson Polynomials of the Second Kind

Authors: Adama Diene; Mohamed A. Salim
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

The permutation behavior of Dickson polynomials of the first kind has been extensively studied, while such behavior for Dickson polynomials of the second kind is less known. Necessary and sufficient conditions for a polynomial of the second kind to be a permutation over some finite fields have been established by Cohen, Matthew, and Henderson. We introduce a new way to define these polynomials and determine the number of their fixed points.


---

## Body

## 1. Introduction

Letp be a prime, e≥1, q=pe, and let 𝔽q be the field of q elements. Denote the greatest integer function of n by ⌊n⌋. For a fixed a∈𝔽q, the polynomials
(1)Dk(x,a)=∑j=1⌊k/2⌋‍kk-j(k-jj)(-a)jxk-2j,Ek(x,a)=∑j=1⌊k/2⌋‍(k-jj)(-a)jxk-2j
are called the Dickson polynomials of the first and second kind, respectively.It is well known (see [1]) that for any x∈𝔽q, there exists u∈𝔽q2 such that x=u+au-1 and the Dickson polynomials may be expressed as
(2)Dk(x,a)=uk+aku-k,Ek(x,a)={uk+1-ak+1u-(k+1)u-au-1,ifu2≠a,(k+1)(±a)k,otherwise.
For a∈𝔽q*, denote
(3)η(a)={1,ifaisasquare,-1,otherwise.According to [2], if η(a)=1 and q is odd, then the sign class of k is defined to be the set A={(±k1,±k2,±k3)∈ℤ3} if k satisfies the following congruences:
(4)k1≡k+1(modp),k2≡k+1(modq-12),k3≡k+1(modq+12).
If η(a)=-1 and q is odd, then the sign class of k is defined to be the set A={(±k1,±k2)∈ℤ2} if k satisfies the following congruences:
(5)k1≡k+1(modq-1),k2≡k+1(modq+1).IfEk(x,1) is a permutation over 𝔽q, then k belongs to the class sign (2,2,2) (see Henderson and Matthews [3]). Moreover (see Cohen in [4]), these conditions are necessary for q∈{p,p2}, where p is an odd prime. Henderson and Matthew extended this result to all squares a such that q∈{p,p2}. Later they found new classes of permutation polynomials of the type Ek(x,1) over 𝔽q. They proved that for q=3e, Ek(x,1) permutes the elements of 𝔽q if the sign class of k contains one of the following triples:(i)
{2,10,10} for e=3;(ii)
{2,4,4} for e odd;(iii)
{2,((3s-1)/2)-1+1,((3t-1)/2)-1+1}, where gcd(s,e)=gcd(t,2e)=1.They also proved that ifq=5e and if k belongs either to the sign class of {2,2,(q-1)/4} or {2,2,2}, then Ek(x,1) permute the elements of 𝔽q. In general, for a large prime number p, few permutation polynomials of the form Ek(x,a) have been identified.Fora∈{-1,0,1}, the cycle structure of Dk(x,a) is well known. It was established by Ahmad in [5] for a=0 and later by Lidl and Mullen [6] for a∈{-1,1}. But the cycle structure of Ek(x,a) remains unknown. We look partially to it by determining the number of fixed points of Ek(x,a) over 𝔽q for the Dickson polynomials of the second kind that are permutation polynomials over 𝔽q. For a=1, it is well known that the first and second Chebyshev polynomials Tn(x) and Un(x), over the field ℤp, are, respectively, conjugates of Dk(x,1) and Ek(x,1). Namely, we have
(6)Dk(x,1)=2Tk(x2),Ek(x,1)=Uk(x2),
where
(7)Tk(x)=cos(karccos(x)),Uk(cos(θ))=sin((k+1)θ)sin(θ),(k∈ℤ).
We use these relations between Dickson polynomials and Chebyshev polynomials along with a new approach to define Tn(x) and Un(x) over ℤp to give a new approach of the Dickson polynomials Dk(x,1) and Ek(x,1) on ℤp in Section 2. In Section 3, we study the number of fixed points of Ek(x,a).


## 2. The Dickson PolynomialsDk(x,1) and Ek(x,1)

Now we present a theoretical approach of the family of Dickson polynomialsDk(x,1) and Ek(x,1) on ℤp, which are essentially the first and the second Chebyshev polynomials Tn(x) and Un(x) over ℤp. We will provide a better way to look at these polynomials which can help to find many known properties. Let us recall that the first and the second Chebyshev polynomials defined in (7) can also be, respectively, defined by the following linear recurrence relations:
(8)T0(x)=1,T1(x)=x,Tk(x)=2xTk-1(x)-Tk-2(x),(9)U0(x)=1,U1(x)=2x,Uk(x)=2xUk-1(x)-Uk-2(x).
Obviously, Dk(x,1)=2Tk(x/2), Ek(x,1)=Uk(x/2) and they can be derived as conjugates of Tk(x) and Uk(x), respectively. This implies that Dk(x,1) and Tk(x), as permutations of ℤp, have the same number of cycles with the same length when written as a product of disjoint cycles, likewise for Ek(x,1) and Uk(x). Therefore to understand the permutation structure of Dk(x,1) and Ek(x,1), it suffices to know that of Tk(x) and Uk(x).Putℝp=ℤp[z]/(z2+1). The structure of ℝp depends on whether -1 is a square in ℤp or not. For a given ring R, we denote their group of units by U(R).Lemma 1.
Letp≡1(mod4). If 1-x2 is a square in ℤp, that is, 1-x2=y2 for some y∈ℤp, then there exists a group homomorphism N:U(ℝp)→U(ℤp), such that for any x+yz∈Ker(N), the following equation
(10)(x+yz)k=Pk(x,y)+Qk(x,y)z
holds, where Tk(x)=Pk(x,y) and Uk(x)=(1/y)Qk(x,y).Proof.
Ifp≡1(mod4), then -1 is a square in ℤp. Let ±w be its roots in ℤp. Then ℝp≅ℤp⊕ℤp, so |U(ℝp)|=(p-1)2. If X∈ℝp, then X can be expressed as X=a+bz, where a,b∈ℤp. Let N be the mapping from ℝp to ℤp defined by
(11)N(a+bz)=a2+b2.
Clearly, N is a surjective group homomorphism from U(ℝp) to U(ℤp). If x+yz∈Ker(N), then (x+yz)-1=x-yz. Furthermore, Ker(N)≅U(ℤp) and it has order p-1. If
(12)(x+yz)n=Pn(x,y)+Qn(x,y)z,(x+yz∈Ker(N)),
then
(13)(x+yz)n+1=(Pn(x,y)+Qn(x,y)z)(x+yz)=(xPn(x,y)-yQn(x,y))+(xQn(x,y)+yPn(x,y))z.
Therefore, Pn(x,y) and Qn(x,y) satisfy the recurrence relations
(14)Pn+1(x,y)=(x+y)xPn(x,y)-yQn(x,y),Qn+1(x,y)=xQn(x,y)+yPn(x,y),
where
(15)P1(x)=x,P2(x)=2x2-1,Pp(x)=x,Pk+n(x)=Pn(x),1yQ1(x)=1,1yQ2(x)=2x,1yQp(x)=1,1yQk+n(x)=Qn(x),
and k is the order of x+yz. That is, Pn(x,y) and Qn(x,y)/y satisfy the recurrence (8), which means that Tn(x)=Pn(x,y) is the first coordinate of (x+yz)n and
(16)Un(x)=Qn(x,y)y.
Notice that Qn(x,y) is uniquely determined by Pn(x,y) up to a sign and we have
(17)T1(x)=x,T2(x)=2x2-1,Tp(x)=x,Tk+n(x)=Tn(x),U1(x)=1,U2(x)=2x,Up(x)=1,Uk+n(x)=Un(x),
where k is the order of x+yz.Remark 2.
Let FC be the set of all the first coordinates of the elements inKer(N). FC contains (p+1)/2=(p-1)/2+1 elements including 0 and 1. Those elements are x in ℤp for which 1-x2 is a square in ℤp. Moreover, FC is invariant under the actions of Tn and Un. For a given element u in FC, we can find an element v in FC such that u+vz is in Ker(N). The mapping which sends u+vz to u+vwu-vw is an isomorphism from Ker(N) to U(ℤp). Therefore, the order of u+vz is simply determined by the least common multiple of the order of u+vw and u-vw. However, since in ℤp, (u+vw)(u-vw)=1, the kernel Ker(N) is cyclic. For any element u+vz in Ker(N), if u+vw=g, a generator of the group U(ℤp), then u+vz is a generator of Ker(N).Lemma 3.
Letp≡3(mod4). If 1-x2 is a square in ℤp, that is, 1-x2=y2 for some y∈ℤp, then there exists a group homomorphism N:U(ℝp)→U(ℤp), such that
(18)(x+yz)n=Pn(x,y)+Qn(x,y)z,(x+yz∈Ker(N)),
where Tn(x)=Pn(x,y) and Un(x)=Qn(x,y)/y.Proof.
In this case,-1 is not a square in ℤp, and |ℝp|=p2. Therefore, |U(ℝp)|=p2-1. Again we can express every element X∈ℝp as X=a+bz, where a,b∈ℤp.  Let N:ℝp→ℤp be a map, defined by N(a+bz)=a2+b2. Clearly, N is a surjective group homomorphism from U(ℝp) to U(ℤp). The inverse of x+yz∈Ker(N) is (x+yz)-1=x-yz and for each element x+yz∈Ker(N) if (x+yz)n=Pn(x,y)+Qn(x,y), then
(19)(x+yz)n+1=(Pn(x,y)+Qn(x,y)z)(x+yz)=(xPn(x,y)-yQn(x,y))+(xQn(x,y)+yPn(x,y))z.
Therefore, Pn(x,y) and Qn(x,y) satisfy the recurrence relations
(20)Pn+1(x,y)=(x,y)xPn(x,y)-yQn(x,y),Qn+1(x,y)=xQn(x,y)+yPn(x,y),
where
(21)P1(x)=x,P2(x)=2x2-1,Pp+1(x)=1,Pp+2(x)=x,Pk-n(x)=Pn(x),1yQ1(x)=1,1yQ2(x)=2x,1yQp+2(x)=1,1yQp+3(x)=2x,1yQk+n(x)=Qn(x),
and k is the order of x+yz. That is, Tn(x)=Pn(x,y) is the first coordinate of (x+yz)n and Qn(x,y) is uniquely determined by Pn(x,y) up to a sign. Un=Qn(x,y)/y is the second Chebyshev polynomial. In this case, Ker(N) is a cyclic group of order p+1, which also implies that
(22)Tp+1(x)=1,Tp+2(x)=x,Tk-n(x)=Tn(x),Up+2(x)=1,Tp+3(x)=2x,Tk-n(x)=Tn(x),
where k is the order of x+yz.Remark 4.
SinceKer(N) is a cyclic group, a good way to find a generator is to first find the generator of U(ℝp) and then take the (p-1)th power. If we let again FC to be the set of all the first coordinates of the elements of Ker(N), then it contains ((p+1)/2)+1 elements including 0 and1. The Ker(N) includes all the elements x in ℤp for which 1-x2 is a square in ℤp. It is invariant under the actions of Tn and Un.Finally, we assume that1-x2 is not a square in ℤp. Put
(23)ℤ-p=ℤp[y][y2-(1-x2)].
Clearly, ℤ-p is a field of p2 elements and ℤp can be embedded in ℤ-p in the conventional way. For convenience, we will treat ℤp as a subset of ℤ-p according to the standard embedding. Here, -1 becomes naturally a square in ℤ-p, and ±y are the two square roots of (1-x2) in ℤ-p. The group of units U(ℤ-p) of ℤ-p is a cyclic group of order p2-1. Let ℍp=ℤ-p[z]/(z2+1). Then ℍp is a ring but not a field. Let 𝕊-p denote the subset of all elements in ℍp of the form of a+byz where a,b∈ℤp. Clearly, 𝕊-p is a subring of ℍp.Lemma 5.
Letp≡1(mod4). There exists a group homomorphism N:U(𝕊-p)→U(ℤp), such that
(24)(x+yz)n=Pn(x,y)+Qn(x,y)z,(x+yz∈Ker(N)),
where Tn(x)=Pn(x,y) and Un(x)=Qn(x,y)/y.Proof.
In this case,-1 is a square in ℤp and the equation a2+b2(1-x2)=0  has no nonzero solutions for a,b∈ℤp. Therefore, 𝕊-p is a field.
LetN be the mapping from U(𝕊-p) to U(ℤ-p), defined by
(25)N(a+byz)=a2+b2(1-x2).
Clearly, N is a surjective group homomorphism from U(𝕊-p) to U(ℤ-p). Moreover, Ker(N) is a cyclic group of order p+1, and for every element x+yz∈Ker(N), (x+yz)-1=x-yz and for each element of the form x+yz∈Ker(N) if
(26)(x+yz)n=Pn(x,y)+Qn(x,y),
then
(27)(x+yz)n+1=(Pn(x,y)+Qn(x,y)z)(x+yz)=(xPn(x,y)-yQn(x,y))cc+(xQn(x,y)+yPn(x,y))z.
Therefore, Pn(x,y) and Qn(x,y) satisfy the recurrence relations
(28)Pn+1(x,y)=(x,y)xPn(x,y)-yQn(x,y),Qn+1(x,y)=xQn(x,y)+yPn(x,y),
where
(29)P1(x)=x,P2(x)=2x2-1,Pp+1(x)=1,Pp+2(x)=x,Pk-n(x)=Pn(x),1yQ1(x)=1,1yQ2(x)=2x,1yQp+2(x)=1,1yQp+3(x)=2x,1yQk+n(x)=Qn(x),
and k is the order of x+yz. That is, Tn(x)=Pn(x,y) is the first coordinate of (x+yz)n and Qn(x,y) is uniquely determined by Pn(x,y) up to a sign. Un(x)=Qn(x,y)/y is the second Chebyshev polynomial. Since Ker(N) is a cyclic group of order p+1, we have
(30)Tp+1(x)=1,Tp+2(x)=x,Tk-n(x)=Tn(x),Up+2(x)=1,Tp+3(x)=2x,Uk-n(x)=Un(x),
where k is the order of x+yz.Remark 6.
We can find a generator ofKer(N) by raising to the (p-1)th a generator of U(𝕊-p). If FCK-p denotes the set of all the first coordinates of the elements of Ker(N), then it contains (p+1)/2+1 elements including ±1, but not 0. FCK-p without the elements ±1 consists of all the elements x in ℤp for which 1-x2 is not a square in ℤp.Lemma 7.
Letp≡3(mod4). There exists a group homomorphism N:U(ℝp)→U(ℤp), such that Tn(x)=Pn(x,y) and Un(x)=Qn(x,y)/y, whenever x+yz∈Ker(N) and (x+yz)n=Pn(x,y)+Qn(x,y)z.Proof.
Here, we know that-1 is not a square in ℤp and a2+b2(1-x2)=0 has nonzero solutions for a and b. The total number of solutions is 2p-1. Therefore, 𝕊-p is not a field.
LetN:𝕊-p→ℤ-p* be a map, defined by
(31)N(a+byz)=a2+b2(1-x2).
Clearly, N is a surjective group homomorphism from U(𝕊-p) to U(ℤ-p). Also Ker(N) is a cyclic group of order p-1 and for every element x+yz∈Ker(N), (x+yz)-1=x-yz. Furthermore, if
(32)(x+yz)n=Pn(x,y)+Qn(x,y)(x+yz∈Ker(N)),
then
(33)(x+yz)n+1=(Pn(x,y)+Qn(x,y)z)(x+yz)=(xPn(x,y)-yQn(x,y))cc+(xQn(x,y)+yPn(x,y))z.
Therefore, Pn(x,y) and Qn(x,y) satisfy the recurrence relations
(34)Pn+1(x,y)=(x,y)xPn(x,y)-yQn(x,y),Qn+1(x,y)=xQn(x,y)+yPn(x,y),
where
(35)P1(x)=x,P2(x)=2x2-1,Pp+1(x)=1,Pp+2(x)=x,Pk-n(x)=Pn(x),1yQ1(x)=1,1yQ2(x)=2x,1yQp+2(x)=1,1yQp+3(x)=2x,1yQk+n(x)=Qn(x),
and k is the order of x+yz. That is,
(36)Tp-1(x)=1,Tp(x)=x,Tk-n(x)=Tn(x),Up+2(x)=1,Up+3(x)=2x,Uk-n(x)=Un(x),
where k is the order of x+yz.Remark 8.
As in Remark6, finding a generator u+vz for Ker(N) is equivalent to finding a generator g in U(𝕊-p) such that g=u+vw. If FC𝕂-p denotes the set of all the first coordinates of the elements of Ker(N), then it contains (p+1)/2 elements including ±1, but not 0. FC𝕂-p without the element ±1 consists of all the elements x in ℤp for which 1-x2 is not a square in ℤp.As corollaries of the previous discussion, we obtain the following.Corollary 9.
Ifp≡1(mod4), then the number of elements x∈ℤp  for which 1-x2 is a square in ℤp is (p+1)/2.
Ifp≡3(mod4), then the number of elements x∈ℤp  for which 1-x2 is a square in ℤp is (p+3)/2.


## 3. Number of Fixed Points ofEk(x,a)

Since Dickson permutation polynomials are closed under composition of polynomials if and only ifa=0,1, or -1 (see [7]), we will only focus on these 3 cases.The case whena=0 was proven by Ahmad [5]. His proof can also be found in [6]. The theorem is formulated as follows.Theorem 10.
The number of fixed points ofEk(x,0) over 𝔽q is given by
(37)gcd(q-1,k-1)+1.In the next two theorems, we treat the casesa=1 and a=-1. Their proofs follow the lines of the one of Lidl and Mullen [6] for the Dickson polynomials of the first kind.Theorem 11.
Forx≠±2, the number of fixed points of Ek(x,1) over 𝔽q is given by
(38)12[gcd(q+1,k-1)+gcd(q+1,2(k+3))c+gcd(q-1,k-1)+gcd(q-1,2(k+3))c-gcd(q+1,k+3)-gcd(q-1,k+3)]-ε1,
where
(39)ε1={5,ifpandnareodd,8∣q+1,and8∣n-1,1,ifpandnareodd,8∤q+1,and8∤n-1,0,ifpisoddandnareeven.Proof.
First we can notice that the only permutation polynomials of the formEk(x,1) over 𝔽q found are those for which q is odd and k belongs to the class sign (2,a,b), where a,b vary depending on if q=p,  p2, 3e, or 5e. Let α∈𝔽q be a fixed point of Ek(x,1). That is for all these permutations, we must have
(40)k+1≡2(modp),k+1≡-2(modq-12).
Then we have Ek(α,1)=α; that is,
(41)uk+1-u-(k+1)u-u-1=u+1u,
which leads to
(42)uk+1-1uk+1-u2+1u2=0.
Hence, we get
(43)(uk+3+1)(uk-1-1)=0.
LetM={u∈𝔽q2:uq-1=1oruq+1=1} be the set of all solutions of the q quadratic equations of the form x2-αx+1=0, with α∈𝔽q. Recall that if ω is a primitive element of 𝔽q2 and if M1={ω(q-1)r:r=0,1,…,q} and M2={ω(q+1)s:s=0,1,…,q-2}, then M=M1∪M2 and M1∩M2={±1}. Also, u is a solution of x2-αx+1=0 if and only if u-1 is also a solution. So each fixed point α∈𝔽q is associated with a pair (u,u-1) in M. Therefore, the number of solutions is equal to half the sum of the solutions in both M1 and M2 excluding the common solutions.
Nowω(q-1)r∈M1 is a solution if and only if ω(q-1)r(k+3)=-1  or  ω(q-1)r(k-1)=1.
Hence, we have(44)2r(k+3)≡0(modq+1)orr(k-1)≡0(modq+1).
The numbers of solutions of these congruences in M1 excluding the common solutions are, respectively, gcd(q+1,2(k+3))-gcd(q+1,k+3) and gcd(q+1,k-1)-2 if p and n are odd. Therefore, the number of fixed points associated to the elements in M1 is
(45)12[gcd(q+1,2(k+3))-gcd(q+1,k+3)c+gcd(q+1,k-1)-2].
Similarly, if p and n are odd, the number of fixed points associated to elements in M2 excluding the common solutions is
(46)12[gcd(q-1,2(k+3))-gcd(q-1,q+3)-1c+gcd(q-1,k-1)-2].
Using the same argument, the numbers of solutions of these congruences in M1 excluding the common solutions are, respectively, gcd(q+1,2(k+3))-gcd(q+1,k+3)  and gcd(q+1,k-1)-2 if p and n are even. Therefore, the number of fixed points associated to elements in M1 is
(47)12[gcd(q+1,2(k+3))-gcd(q+1,k+3)-1].
Similarly, if  p and n are even, the number of fixed points associated to elements in M2 excluding the common solutions is
(48)12[gcd(q-1,2(k+3))-gcd(q-1,q+3)-1].
To complete the proof, we need to subtract the number of solutions when ω(q-1)r(k+3)=-1 andω(q-1)r(k-1)=1 at the same time. These are given by [7] and are equal to
(49){8,ifpandnareodd,8∣q+1,and8∣n-1,0,otherwise.
Combine all the results above to conclude the answer. The case where q is even is pointless since in this case no permutation has been found.Theorem 12.
The number of fixed points ofEk(x,-1) over 𝔽q is given by
(50)12[a1·gcd(k+3,2(q+1))+a2·gcd(k+3,q-1)c+a3·gcd(k-1,2(q+1))+gcd(k-1,q-1)]-ε-1,
where
(51)a1={1,ifυ2(q+1)=υ2(k+3),0,otherwise,a2={1,ifυ2(k+3)≤υ2(q-1)-1,0,otherwise,a3={1,ifυ2(q+1)<υ2(k-1),0,otherwise,ε-1={2,ifq≡1(mod4),0,otherwise.Proof.
First of all, notice that for all permutationsEk(x,-1) over 𝔽q found so far, k is an odd integer. Let α∈𝔽q be a fixed point of the permutation Ek(x,-1) over 𝔽q. Then, Ek(α,-1)=α; that is,
(52)Ek(x,-1)=uk+1-u-(k+1)u+u-1=u-1u,
which implies
(53)uk+1-u-(k+1)=u2-u-2.
Hence, we have
(54)(uk+3+1)(uk-1-1)=0.
Let ω be a primitive element of 𝔽q2. So we get M1(-1)={ω(q-1)r/2:r=1,3,...,2q+1}, M2(-1)={ω(q+1)s:s=0,1,....,q-2}, and M(-1)=M1(-1)∪M2(-1). For i=0,1, let ui=ω(q2-1)(1+2i)/4. From [6], we have M1(-1)∩M2(-1)={u1,u2} if q≡1(mod4) and M1(-1)∩M2(-1)=∅ if q≡3(mod4). Therefore, as it was mentioned in [6], if we defined
(55)N3(-1)={u1,u2}ifq≡1(mod4),N3(-1)=∅ifq≡3(mod4)
and if
(56)N1(-1)=M1(-1)∖N3(-1),N2(-1)=M2(-1)∖N3(-1),
then
(57)M(-1)=N1(-1)∪N2(-1)∪N3(-1)
is a disjoint union.
Finally, from again [6], for u∈𝔽q, if u=u-1, then  u∈N3(-1). Now a solution u of (uk+3+1)(uk-1-1)=0 is a solution of both (uk+3+1) and (uk-1-1) if and only if u∈N3(-1). Therefore, the number of solutions of (54) is the sum of the solutions in N1(-1),N2(-1), and N3(-1).
Letυp(m) denote the highest power of p dividing m if m≠0 and set υp(0)=∞. An element u∈M1(-1) is a solution of uk+3+1=0 if and only if
(58)r(k+3)≡q+1(mod2(q+1)),
which has solutions if and only if gcd(k+3,2(q+1)) divides (q+1) if and only if υ2(k+3)≤υ2(q+1).
Letd=gcd(k+3,2(q+1)). It is easy to see that
(59)υ2(d)=min{υ2(k+3),υ2(2(q+1))}=υ2(k+3).
Also let α,β∈ℤ, such that α(k+3)+2β(q+1)=d. Then the solutions of (58) are
(60)r=α(q+1)d+2(q+1)di,(i=0,…,d-1).
Using the same argument as in [6], α should be odd, because otherwise
(61)υ2(d)≥min{υ2(k+3)+1,υ2(2(q+1))+1}>υ2(k+3).
Now υ2(q+1/d)=υ2(q+1)-υ2(d)=υ2(q+1)-υ2(k+1). Therefore, (q+1) divides d if and only if υ2(q+1)=υ2(k+3) and (58) has an odd solution r if and only if υ2(q+1)=υ2(k+3). In this case, we have exactly gcd(k+3,2(q+1)) solutions.
An elementu∈M2(-1) is a solution of uk+3+1=0 if and only if
(62)(ω(q+1)s)k+3=-1,
if and only if  ((ω(q+1)s)k+3)2=1(mod(q2-1)), if and only if  (ω(q+1)s(k+3))2=1(modq2-1), if and only if
(63)2(q+1)s(k+3)=0(mod(q2-1)),
if and only 2s(k+3)=q-1(mod(q-1)), and if and only if
(64)s(k+3)=q-12(mod(q-1)).
The last equation has a solution if and only if gcd(k+3,q-1)) divides (q-1)/2, which is equivalent to the condition υ2(k+3)≤υ2(q-1)-1. Then the total number of those solutions is gcd(k+3,q-1).
An elementu∈M1(-1) is a solution of uk-1-1=0 if and only if
(65)ω(k-1)(q-1)r/2=1(mod(q2-1))
if and only if
(66)r(k-1)≡0(mod2(q+1)),
which has gcd((k-1),2(q+1)) solutions if it is solvable.
Ifd=gcd(k-1,2(q+1)), then
(67)υ2(d)=min{υ2(k-1),υ2(2(q+1))}=υ2(2(q+1)),
which implies that 2(q+1)/d is odd. But this can occur if and only if υ2(q+1)<υ2(k-1), and the solutions of 8 in this case are
(68)r=2(q+1)di,(i=0,…,d-1).
An element u∈M2(-1) is a solution of uk-1-1=0 if and only if (ω(q+1)s)k-1=1, if and only if
(69)s(k-1)≡q-1(modq-1),
if and only if
(70)s(k-1)≡0(modq-1),
which has gcd(k-1,q-1) solutions.
To complete the proof, notice that by a similar method to that of the casea=1, u is a solution of uk+3+1=0 (resp., uk-1-1=0) if and only if -u-1 is also a solution, and the set of solutions of (58) and (66) on N3(-1) is the set of all solutions of uk+3+1=0 and uk-1-1=0 on N3(-1), which is empty if  q≡3(mod4) and is equal to {u1,u2} if q≡1(mod4).



---

*Source: 472350-2013-04-08.xml*