On the distinctness of primitive sequences over Z/(p ^e q) modulo 2

Abstract

Let N be an integer greater than 1 and Z/(N) the integer residue ring modulo N. Extensive experiments seem to imply that primitive sequences of order n≥2 over Z/(N) are pairwise distinct modulo 2. However, efforts to obtain a formal proof have not been successful except for the case when N is an odd prime power integer. Recent research has mainly focussed on the case of square-free odd integers with several special conditions. In this paper we study the problem over Z/(p ^e q), where p and q are two distinct odd primes, e is an integer greater than 1. We provide a sufficient condition to ensure that primitive sequences generated by a primitive polynomial over Z/(p ^e q) are pairwise distinct modulo 2.

1 Introduction

Throughout the paper, for any integer N≥2, let Z/(N) be the integer residue ring modulo N. We always choose {0,1,...,N−1} as the representatives of the ring Z/(N). Thus a sequence $\underline {a}$ over Z/(N) is usually viewed as an integer sequence over {0,1,...,N−1}. Moreover, for an integer a and a positive integer b≥2, we denote the least nonnegative residue of a modulo b by [a]_{mod b} . Similarly, for an integer sequence $\underline {a}=(a(t))_{t\geq 0}$ , we denote $[\underline {a}]_{\bmod {b}}=([a(t)]_{\bmod {b}})_{t\geq 0}$.

In September 2011, a set of two cryptographic algorithms was accepted by 3GPP SA3 as a new inclusion in the LTE standards. It consists of a confidentiality algorithm named 128-EEA3 and an integrity algorithm named 128-EIA3, both of which are based on a core stream cipher algorithm named ZUC [1]. ZUC algorithm adopts primitive sequences over the prime field Z/(2³¹−1) as driving sequences. Cryptographic analyses [??1, Section 12] show that those driving sequences have a significant contribution to algorithm’s resistance against bit-oriented cryptographic attacks, including fast correlation attacks, linear distinguishing attacks and algebraic attacks. Note that we can derive 31 sequences totally from the 2-adic expansion of $\underline {a}=\underline {a}_{0}+\underline {a}_{1}\cdot 2+{\cdots } +\underline {a}_{30}\cdot 2^{30}$, called the 2-adic coordinate sequences of $\underline {a}.$ The essential rationality for the application of primitive sequences over Z/(2³¹−1) is that they are pairwise distinct modulo 2 [??3, Theorem 4.2] i.e. $\underline {a}=\underline {b}$ iff $[\underline {a}]_{\bmod {2}}=[\underline {b}]_{\bmod {2}}$, where $\underline {a}$ and $\underline {b}$ are two primitive sequences over Z/(2³¹−1) generated by a primitive polynomial. Such “distinctness property” guarantees that the 31 binary sequences $\underline {a}_{0},{\ldots } ,\underline {a}_{30}$ have the following two important properties: (1) all of their periods are equal to the period of $\underline {a}$; (2) each $\underline {a}_{k}$ uniquely determine the original primitive sequence $\underline {a}$, see [??1 Page18] and [??2, Corollary 1, Remark 1] for more details.

Generally, for an integer e≥2, if primitive sequences (its definition is given in Subsection 2.1 ) over Z/(2^e−1) are pairwise distinct modulo 2, then their 2-adic coordinate sequences also enjoy the two properties as mentioned above. We note that, however, primitive sequences over Z/(2^e−1) are not always pairwise distinct modulo 2. For example, $\underline {a}=\left (1,5,4,20,16,17,{\ldots } \right )$ and $\underline {b}=\left ( 11,13,2,10,8,19,{\ldots } \right )$ are two distinct primitive sequences of order 1 generated by x−5 over Z/(2⁶−1), it is easy to verify that $[\underline {a}]_{\bmod {2}}=[\underline {b}]_{\bmod {2}}$. On the other hand, to the best of our knowledge, no counterexample has been found until now if the order of primitive sequences is greater than 1. It seems to imply that primitive sequences of order n≥2 over Z/(2^e−1) are pairwise distinct modulo 2. Unfortunately, efforts to obtain a formal proof have not been successful.

Recent study indicates that the problem of modulo-2 distinctness over Z/(2^e−1) seems not easier than over Z/(N) except for some special e (see, for example, [2] ), where N is an odd integer. Additionally, since whether the property of modulo-2 distinctness holds for Z/(N) is also of interest in mathematics, the study of modulo-2 distinctness over Z/(2^e−1) is generally turned to the case of Z/(N).

The known results for the problem over Z/(N) mainly rely on the factorization of N. The case that N is an odd prime power integer has been completely solved in [3].

Theorem 1

([3, Theorem 4.2]) Let p ^e be an odd prime power and $f\left ( x\right )$ a primitive polynomial of degree n over Z/(p^e). Then $\underline {a}=\underline {b}$ iff $[\underline {a} ]_{\bmod {2}}=[\underline {b}]_{\bmod {2}}$ , where $\underline {a}$ and $\underline {b}$ are two primitive sequences generated by f(x) over Z/(p^e).

Besides, several results for square-free N can be found in [4–8]. But there is no known result in the case when N is neither square-free nor prime power.

This paper studies the problem over Z/(p ^e q), where p and q are two distinct odd primes, e is an integer greater than 1. Utilizing the same technology of decimation proposed in our previous work [9] and the Chinese Remainder Theorem, we provide a sufficient condition to ensure that primitive sequences generated by a primitive polynomial $f\left (x\right )$ over Z/(p ^e q) are pairwise distinct modulo 2, see Theorem 2 for details.

The rest of the paper is organized as follows. In Section 2 we present some necessary preliminaries. In Section 3 we establish the main results of this paper.

2 Preliminaries

2.1 Primitive polynomials and primitive sequences

Let N be an integer greater than 1. If a sequence $\underline {a}$ over Z/(N) satisfies

$$a(i+n)=[c_{n-1}a(i+n-1)+{\ldots} +c_{1}a(i+1)+c_{0}a(i)]_{\bmod{N}} $$

for any integer i≥0, where n is a positive integer and c ₀,c ₁,…,c _n−1∈Z/(N) are constant coefficients, then $\underline {a}$ is called a linear recurring sequence of order n over Z/(N) generated by f(x)=x ⁿ−c _n−1 x ⁿ⁻¹−…−c ₀ (or $\underline {a}$ is a sequence of order n over Z/(N) for simplicity), and f(x) is called a characteristic polynomial of $\underline { a}$. A characteristic polynomial of $\underline {a}$ with the least degree is called a minimal polynomial. Note that, generally speaking, a minimal polynomial of a sequence over Z/(N) is not necessarily unique. For example, both x ²−x−1 and x ²−4x−1 are the minimal polynomials of the sequence (0,3,3,6,0,6,6,3,...) over Z/(9) whose period is equal to 8. For convenience, the set of sequences generated by f(x) over Z/(N) is generally denoted by G(f(x),N).

Let $f\left (x\right )$ be a monic polynomial of degree n over Z/(N). If $f\left (0\right )$ is an invertible element in Z/(N), that is gcd (f(0),N)=1, then there exists a positive integer T such that x ^T−1 is divisible by f(x) in Z/(N)[x]. The minimum of such T is called the period of $f\left (x\right )$ over Z/(N) and denoted by $per\left (f\left (x\right ) ,N\right )$. In the case when N is a prime power integer, say N=p ^e, it is known that $per\left (f\left (x\right ) ,p^{e}\right ) \leq p^{e-1}(p^{n}-1)$, see [10]. If $per\left (f\left (x\right ),p^{e}\right )=p^{e-1}(p^{n}-1)$, then $f\left (x\right )$ is called a primitive polynomialof order n over Z/(p ^e). A sequence $\underline {a}$ over Z/(p ^e) is called a primitive sequence of order n if $\underline {a}$ is generated by a primitive polynomial of degree n over Z/(p ^e) and $[\underline {a}]_{\bmod {p}}$ is not an all-zero sequence. In the case when N is an arbitrary integer, assume $N=p_{1}^{e_{1}}p_{2}^{e_{2}}{\cdots } p_{r}^{e_{r}}$ is the canonical factorization of N. A monic polynomial $f\left ( x\right )$ of degree n over Z/(N) is called a primitive polynomialif for every $i\in \left \{1,2,{\ldots } ,r\right \}$, $f\left (x\right ) (\bmod {p_{i}^{e_{i}}})$ is a primitive polynomial of degree n over $\mathbf {Z}/(p_{i}^{e_{i}})$. A sequence $\underline {a}$ over Z/(N) is called a primitive sequence of order n if $\underline {a}$ is generated by a primitive polynomial of degree n over Z/(N) and $[\underline {a}]_{\bmod {p_{i}}}$ is not an all-zero sequence for every $i\in \left \{1,2,\ldots , r\right \}$, that is, $[\underline {a}]_{\bmod {p_{i}^{e_{i}}}}$ is a primitive sequence of order n over $\mathbf {Z}/(p_{i}^{e_{i}})$. For convenience, the set of primitive sequences generated by a primitive polynomial $f\left (x\right )$ over Z/(N) is generally denoted by $G^{\prime }(f(x),N)$.

2.2 Element distribution properties of sequences over Z/(p ^e)

Let p ^e be a prime power integer. For a sequence $\underline {a}=(a(t))_{t\geq 0}$ over Z/(p ^e), if we write each a(t) in its unique p-adic expansion as a(t)=a ₀(t)+a ₁(t)⋅p+…+a _e−1(t)⋅p ^e−1, where a _i (t)∈{0,1,…,p−1} for i∈{0,1,…,e−1}, then the p-ary sequence $\underline {a}_{i}=(a_{i}(t))_{t\geq 0}$ is called the i-th coordinate sequence of $\underline {a}$.

It is clear that if $f\left (x\right )$ is a polynomial over Z/(p ^e), then $f\left (x\right )$ is also a polynomial over Z/(p ⁱ) with its coefficients modulo p ⁱ for 1≤i≤e−1.

Definition 1

A monic polynomial $f\left (x\right )$ of degree n over Z/(p ^e) is called a basic irreducible polynomial if $f\left (x\right )$ is an irreducible polynomial of degree n over Z/(p).

Remark 1

Basic irreducible polynomials are also called Galois polynomials, for example, see [12].

If $f\left (x\right )$ is a basic irreducible polynomial over Z/(p ^e), then it is clear that $f\left (x\right )$ is also a basic irreducible polynomial over Z/(p ⁱ) for 1≤i≤e−1. Moreover, any primitive polynomial over Z/(p ^e) is a basic irreducible polynomial over Z/(p ^e), but the converse is not true.

We first present an element distribution property for linear recurring sequences generated by basic irreducible polynomials over Z/(p ^e).

Lemma 1

([11, Proposition 1]) Let $f\left (x\right )$ be a basic irreducible polynomial of degree n over Z/(p^e) and $\underline {a}\in G(f(x),p^{e})$ with $\underline {a}_{0}\neq \underline {0}$ , where $\underline {a}_{0}$ is the 0-th coordinate sequence of $\underline {a}$ . If

$$per\left( f\left( x\right),p\right) \geq \left( p^{e}-1\right) p^{n/2+e-1} \text{,} $$

then every element of Z/(p ^e) appears at least once in $\underline {a}$.

For a sequence $\underline {a}=(a(t))_{t\geq 0}$ and a positive integer s, we denote by $\underline {a}^{\left (s\right )}$ the s-fold decimation of $\underline {a}$, i.e. $\underline {a}^{\left (s\right )}=(a(st))_{t\geq 0}$. Next we will show that if $\underline {a}$ is a primitive sequence of order n over Z/(p ^e) and s is a positive integer satisfying $\frac { p^{n}-1}{\gcd \left (p^{n}-1,s\right ) }>p^{n/2}$, then the minimal polynomial of $\underline {a}^{\left (s\right )}$ over Z/(p ^e) is unique and is a basic irreducible polynomial of degree n.

Proposition 1

Let p ^e be a prime power and $f\left (x\right )$ a primitive polynomial of degree n over Z/(p ^e). Let $\underline {a}\in G^{\prime }(f(x),p^{e})$ and s a positive integer. If

$$\frac{p^{n}-1}{\gcd \left( p^{n}-1,s\right)}>p^{n/2}\text{,} $$

then the minimal polynomial of $\underline {a}^{\left (s\right ) }$ over Z/(p ^e) is unique and is a basic irreducible polynomial of degree n only depending on f(x). Moreover, let g(x) be the minimal polynomial of $\underline {a}^{\left (s\right )}$ over Z/(p ^e). Then

$$per\left( g\left( x\right) ,p^{e}\right)= \frac{p^{e-1}(p^{n}-1)}{\gcd\left( p^{e-1}(p^{n}-1),s\right)}\ and\ per\left( g\left( x\right) ,p \right)= \frac{p^{n} -1}{\gcd \left( p^{n}-1,s\right)} \text{.} $$

Proof

See Appendix A. □

Combining Lemma 1 with Proposition 1, we can immediately obtain Lemma 2 as follows.

Lemma 2

Let $f\left (x\right )$ be a primitive polynomial of degree n ≥ 2 over Z/(p ^e) and $\underline {a}\in G^{\prime }(f(x),p^{e})$. Let s be a positive integer. If

$$\frac{p^{n}-1}{\gcd \left( p^{n}-1,s\right)} \geq \left( p^{e}-1\right) p^{\left( n/2+e-1\right)} \text{,} $$

then every element of Z/(p ^e) appears at least once in $\underline {a}^{\left (s\right )}$.

Let $\underline {a}=(a(t))_{t\geq 0}$ and $\underline {b}=(b(t))_{t\geq 0}$ be two sequences over Z/(p ^e). If there exists u,v∈Z/(p ^e) , not both equal to 0, such that $[u\cdot \underline {a}+v\cdot \underline {b}]_{\bmod {p^{e}}}=\underline {0}$, that is $\phantom {\dot {i}\!}[u\cdot a(t)+v\cdot b(t)]_{\bmod {p^{e}}}=0$ for any integer t≥0, then we say that $\underline {a}$ and $\underline {b}$ are linearly dependent over Z/(p ^e). Otherwise, we say that $\underline {a}$ and $\underline {b}$ are linearly independent over Z/(p ^e). For the case when e=1, if $\underline {a}$ and $\underline {b}$ are linearly dependent over Z/(p), and additionally $\underline {b}\neq \underline {0}$, then it follows that $\underline {a}=[\lambda \cdot \underline {b}]_{\bmod {p}}$ for some λ∈Z/(p). However, this is not true for the case when e>1. For instance, let $\underline {a}=\left (0,1,2,3,{\ldots } \right )$ and $\underline {b}= \left (3,2,1,0,{\ldots } \right )$ be two sequences with period 4 over Z/(9), it is easy to verify that $\underline {a}$ and $\underline {b}$ are linearly dependent over Z/(9), but there does not exist λ∈Z/(9) such that $\underline {a}=[\lambda \cdot \underline {b}]_{\bmod {9}}$.

We now present an element distribution property for two linearly independent sequences over Z/(p ^e).

Lemma 3

([12, Corollary 5]) Let $f\left (x\right )$ be a basic irreducible polynomial of degree n over Z/(p ^e) and $\underline {a},\underline {b}\in G(f(x),p^{e})$ . If $\underline {a}$ and $\underline {b}$ are linearly independent over Z/(p ^e) and

$$per \left( f \left( x\right), p\right) \geq \left( p^{2e}-1\right) p^{n/2+e-1} \text{,} $$

then for any u,v ∈ Z/(p ^e), there exists an integer t ≥ 0 such that $a\left (t\right )=u, b\left (t\right )=v$.

Combining Lemma 3 with Proposition 1, we can immediately obtain Lemma 4 as follows.

Lemma 4

Let $f\left (x\right )$ be a primitive polynomial of degree n over Z/(p ^e ) and $\underline {a},\underline {b}\in G^{\prime }(f(x),p^{e})$. Let s be a positive integer. If $\underline {a}^{(s)}$ and $\underline {b}^{(s)}$ are linearly independent over Z/(p ^e) and

$$\frac{p^{n}-1}{\gcd \left( p^{n}-1,s\right)}\geq \left( p^{2e}-1\right) p^{\left( n/2+e-1\right)} \text{,} $$

then for any u,v ∈ Z/(p ^e), there exists an integer t ≥ 0 such that a ^(s) (t) = u, b ^(s) (t) = v.

3 Distinctness of primitive sequences over Z/(p ^e q) modulo 2

Throughout this section, we always assume that p and q are two fixed distinct odd primes, e is an integer greater than 1.

We make our main result explicit in the following statement.

Theorem 2

Let f(x) be a primitive polynomial of degree n ≥ 2 over Z/(p ^e q). If both of the following two conditions hold: (i) $\frac {p^{n}-1}{\gcd (p^{n}-1,q^{n}-1)}\geq \left ( p^{e}-1\right ) p^{\left (n/2+e-1\right )}$ , (ii) $\frac {q^{n}-1}{\gcd (q^{n}-1,p^{e-1}(p^{n}-1))}\geq \left ( q^{2}-1\right ) q^{n/2}$ , then for $\underline {a},\underline {b}\in G^{\prime }(f(x),p^{e}q)$ , $\underline {a}=\underline {b}$ if and only if $[\underline {a}]_{\bmod {2}}=[\underline {b}]_{\bmod {2}}$.

Proof

The necessary condition is trivial. It suffices to prove that, under the above two conditions, $[\underline {a}]_{\bmod {2}}=[\underline {b}]_{\bmod {2}}$ implies that $\underline {a}=\underline {b}$. □

Let $\underline {a},\underline {b}\in G^{\prime }(f(x),p^{e}q)$ be distinct primitive sequences with $[\underline {a}]_{\bmod {2}}=[\underline {b}]_{\bmod {2}}$. Then we will show a contradiction. Using the Chinese Remainder Theorem we have

$$\begin{array}{@{}rcl@{}} \underline{a} &=& \left[q\cdot \underline{u}_{a}+p^{e}\cdot \underline{v}_{a} \right]_{\bmod{p^{e}q}}\text{,} \end{array} $$

(1)

$$\begin{array}{@{}rcl@{}} \underline{b} &=& \left[ q\cdot \underline{u}_{b}+p^{e}\cdot \underline{v}_{b} \right]_{\bmod{p^{e}q}}\text{,} \end{array} $$

(2)

where $\underline {u}_{a}, \underline {u}_{b}\in G^{\prime }(f(x),p^{e})$ and $\underline {v}_{a}, \underline {v}_{b}\in G^{\prime }(f(x),q)$.

Case 1: $\underline {u}_{a}=\underline {u}_{b}$ and $\underline {v}_{a}\neq \underline {v}_{b}\qquad$

By Theorem 1, there exists an integer t≥0 such that

$$ \lbrack v_{a} \left( t\right) ]_{\bmod{2}}\neq \lbrack v_{b} \left( t\right) ]_{\bmod{2}}\text{.} $$

(3)

Let $L^{t}\underline {u}_{a}=(u_{a}(t+s))_{s\geq 0}$ be the t-shift of $\underline {u}_{a}$. Then it is clear that $L^{t}\underline {u}_{a}\in G^{\prime }(f(x),p^{e})$. Let $\underline {c}$ be the $\left ( q^{n}-1\right )$-fold decimation of $L^{t}\underline {u}_{a}$, i.e.

$$\underline{c}=\left( u_{a}\left( t+k\cdot \left( q^{n}-1\right)\right)\right)_{k\geq 0}.$$

Then by Condition (i) and Lemma 2, there exists an integer k ^∗≥0 such that $c\left ( k^{\ast }\right )=0$, which yields

$$u_{a}\left( t+k^{\ast} \cdot \left( q^{n}-1\right)\right)=u_{b}\left( t+k^{\ast}\cdot \left( q^{n}-1\right)\right)= 0\text{.} $$

Therefore, by (1) and (2) together with $per(\underline {v}_{a})=per(\underline {v}_{b})=q^{n}-1,$ we obtain that

$$\begin{array}{@{}rcl@{}} a\left( t+k^{\ast}\cdot \left( q^{n}-1\right)\right) &=& p^{e}\cdot v_{a}\left( t+k^{\ast}\cdot \left( q^{n}-1 \right)\right)=p^{e}v_{a}(t)\text{,} \\ b\left( t+k^{\ast }\cdot \left( q^{n}-1\right)\right) &=&p^{e}\cdot v_{b}(t+k^{\ast}\cdot \left( q^{n}-1\right)=p^{e}v_{b}\left( t\right) \text{.} \end{array} $$

Now (3) implies that

$$\left[ a\left( t+k^{\ast }\cdot \left( q^{n}-1\right)\right)\right]_{\bmod{2}}\neq \left[ b\left( t+k^{\ast }\cdot \left( q^{n}-1\right)\right)\right]_{\bmod{2}}\text{,} $$

a contradiction.

Case 2: $\underline {u}_{a}\neq \underline {u}_{b}$ and $\underline {v}_{a}=\underline {v}_{b}$

By Theorem 1, there exists an integer t ≥ 0 such that

$$ \lbrack u_{a}\left( t\right)]_{\bmod{2}}\neq \lbrack u_{b}\left( t\right)]_{\bmod{2}}\text{.} $$

(4)

Set $\underline {c}=(v_{a}(t+k\cdot p^{e-1}(p^{n}-1)))_{k\geq 0}$. Then it is clear that $\underline {c}$ is the (p ^e−1(p ⁿ−1))-fold decimation of $L^{t}\underline { v}_{a}$. Employing Condition (i) and Lemma 2, we know that there exists an integer k ^∗≥0 such that $c\left (k^{\ast }\right )=0$, which yields

$$v_{a}\left( t+k^{\ast } \cdot p^{e-1}\left( p^{n}-1\right)\right) =v_{b}\left( t+k^{\ast }\cdot p^{e-1}\left( p^{n}-1\right)\right)=0\text{.} $$

Similar to Case 1, we can deduce that

$$\left[ a(t+k^{\ast}\cdot p^{e-1}\left( p^{n}-1\right)\right]_{\bmod{2}}\neq \left[ b(t+k^{\ast}\cdot p^{e-1}\left( p^{n}-1\right) \right]_{\bmod{2}}\text{,} $$

which is a contradiction.

Case 3: $\underline {u}_{a}\neq \underline {u}_{b}$ and $\underline {v} _{a}\neq \underline {v}_{b}$

By Theorem 1, there exists an integer t≥0 such that

$$\vspace*{-12pt} \lbrack u_{a}\left( t\right) ]_{\bmod{2}}\neq \lbrack u_{b}\left( t\right) ]_{\bmod{2}}\text{.} $$

(5)

Set

$$\underline{c}= \left( v_{a}\left( t+k\cdot \left( p^{e-1}\left( p^{n}-1\right)\right)\right)\right)_{k\geq 0} $$

and

$$\underline{d}=\left( v_{b}\left( t+k\cdot \left( p^{e-1}\left( p^{n}-1\right)\right)\right)\right)_{k\geq 0}. $$

Then $\underline {c}$ and $\underline {d}$ are the $\left ( p^{e-1}\left (p^{n}-1\right )\right )$-fold decimation of $L^{t}\underline {v}_{a}$ and $L^{t}\underline {v}_{b}$, respectively. According to the proof of Case 1, it suffices to prove that there exists an integer k ^∗≥0 such that c(k ^∗)=d(k ^∗)=0. Consider the following two sub-cases.

(1)$\underline {c}$ and $\underline {d}$ are linearly independent over Z/(q).

By Condition (i i) and Lemma 4, there exists an integer k ^∗≥0 such that c(k ^∗)=d(k ^∗)=0.

(2)$\underline {c}$ and $\underline {d}$ are linearly dependent over Z/(q).

Combining Condition (i i) and Proposition 1 we have $\underline {d}\neq \underline {0}$, and

$$\underline{c}=[\lambda\cdot\underline{d}]_{\bmod{q}}$$

for some λ∈Z/(q). Then by Condition (i i) and Lemma 2, there exists an integer k ^∗≥0 such that d(k ^∗)=0, and hence c(k ^∗)=0.

Combining all the cases, we finish our proof.

Remark 2

Under the same conditions of Theorem 2, for $\underline {a}\in G^{\prime } (f(x),p^{e}q)$, we have

$$per([\underline{a}]_{\bmod{2}})=per(\underline{a})=\text{lcm} \left( p^{e-1}\cdot (p^{n}-1),q^{n}-1\right)\text{,} $$

where $per(\underline {a})$ is the period of sequence $\underline {a}$. In fact, the last equality is obvious by the definition of primitive sequences. It suffices to show the first equality. Firstly, it is clear that $per([\underline {a}]_{\bmod {2}})\leq per(\underline {a})$. On the other hand, since $L^{k}\underline {a}\neq \underline {a}$ for $0<k<per(\underline {a})$, where $L^{k}\underline {a}=(a(t+k))_{t\geq 0}$ is the k-shift of $\underline {a}$, it follows from Theorem 2 that $[L^{k} \underline {a}]_{\bmod {2}}\neq \lbrack \underline {a}]_{\bmod {2}}$ for $0<k<per(\underline {a})$ which implies that $per([\underline {a}]_{\bmod {2}}) \geq per(\underline {a})$.

Remark 3

When n≤2(2e−1), Condition (i) fails to hold. In fact, if n≤2(2e−1), we have (note that both p and q are odd)

$$\frac{p^{n}-1}{\gcd (p^{n}-1,q^{n}-1)}<p^{n}/2\leq p^{n/2+2e-1}/2<\left( p^{e}-1\right) p^{\left( n/2+e-1\right)}\text{.} $$

Remark 4

The method above does not apply to the case of Z/(p ^e q ^r) if r>1. The obstacle is that in the Case 3 of our proof, if $\underline {c}$ and $\underline {d}$ are linearly dependent over Z/(q ^r) with r>1, then it is not true that $\underline {c}=[\lambda \cdot \underline {d}]_{\bmod {q^{r}}}$ for some λ∈Z/(q ^r).

The rest of this Section is devoted to the discussion of Conditions (i)- (i i) of Theorem 2.

When e=2, the proportions of $\left ( p,q\right )$ satisfying Conditions (i) and (i i) of Theorem 2 among 3 ≤ p ≠ q ≤ prime(5000) are tested under several ranges of n, where prime(k) is the k-th prime number, see the results in Table 1.

Table 1 Proportions of $\left (p,q\right )$ satisfying Conditions (i) and (i i) of Theorem 2 among 3≤p≠q≤p r i m e(5000)

Based on a result of Bugeaud, Corvaja and Zannier [13, Theorem 1], we will show that for given p,q,e, Conditions (i) and (i i) of Theorem 2 always hold for sufficiently large n.

Lemma 5

([13, Theorem 1]) If a and b are two multiplicatively independent integers greater than 1 (i.e. the only integer solution $\left (x,y\right )$ of the equation a ^x b ^y = 1 is $\left ( x,y\right ) =\left ( 0,0\right ))$, then for any given real number ε>0, there exists an integer N _ε such that

$$\gcd \left( a^{n}-1,b^{n}-1\right) <2^{n\varepsilon } $$

for n>N _ε .

Theorem 3

For given p,q,e, there exists an integer N such that Conditions (i) and (ii) of Theorem 2 always hold if n>N.

Proof

Since it is clear that p and q are multiplicatively independent, it follows from Lemma 5 that for a given real number ε>0, there exists a positive number N _ε such that

$$\gcd \left( p^{n}-1,q^{n}-1\right) <2^{\varepsilon \cdot n} $$

for n>N _ε . Therefore, when n>N _ε , we have

$$\begin{array}{@{}rcl@{}} \frac{p^{n}-1}{\gcd (p^{n}-1,q^{n}-1)}&> &\frac{p^{n}-1}{2^{\varepsilon \cdot n}}\text{,} \end{array} $$

(6)

$$\begin{array}{@{}rcl@{}} \frac{q^{n}-1}{\gcd (q^{n}-1,p^{e-1}(p^{n}-1))}&\geq &\frac{q^{n}-1}{p^{e-1}\gcd (p^{n}-1,q^{n}-1)}>\frac{q^{n}-1}{ p^{e-1}2^{\varepsilon \cdot n}}\text{.} \end{array} $$

(7)

Choose 0<ε<1/2, then it can be verified that

$$\begin{array}{@{}rcl@{}} \lim_{n\rightarrow +\infty }\frac{p^{n}-1}{2^{\varepsilon \cdot n}\cdot \left( p^{e}-1\right) p^{\left( n/2+e-1\right) }}&=&+\infty \text{,}\\ \lim_{n\rightarrow +\infty }\frac{q^{n}-1}{p^{e-1}2^{\varepsilon \cdot n}\cdot \left( q^{2}-1\right) q^{n/2}}&=&+\infty \text{.} \end{array} $$

Therefore there exists an integer $N^{\prime }$ such that for $n>N^{\prime },$

$$ \frac{p^{n}-1}{2^{\varepsilon \cdot n}}>\left( p^{e}-1\right) p^{\left( n/2+e-1\right)}~\text{and}~ \frac{q^{n}-1}{p^{e-1}2^{\varepsilon \cdot n}}> \left( q^{2}-1\right) q^{n/2}. $$

(8)

Set $N=\max \{N_{\varepsilon },N^{\prime }\}$. Then the result is obtained by combining (6), (7) and (8). □

Appendix A: proof of Proposition 1

We first briefly introduce Galois rings. The notation and definitions we will use here are from [12].

A Galois ring is a finite commutative ring R with identity 1 in which the set of all zero divisors has the form p R for some prime p. Primary examples of Galois rings are integer residue rings Z/(p ^e) and finite fields $GF\left (q\right )$ of q elements. A Galois ring R is uniquely determined up to isomorphism by its characteristic p ^e and the number of elements q ^e, where q=p ^r. Therefore in what follows we denote such a ring by $GR\left (q^{e},p^{e}\right )$. In particular, $GR\left (p^{e},p^{e}\right )=\mathbf {Z} /(p^{e})$. Let $R^{\prime }=GR\left (q^{en},p^{e}\right )$ be an extension of degree n of $R=GR\left ( q^{e},p^{e}\right )$. We denote by $\textmd {Aut}\left ( R^{\prime }/R\right )$ the set of all automorphisms of the ring $R^{\prime }$ that fix each element of R. The group $\textmd {Aut} \left (R^{\prime }/R\right )$ is a cyclic group of order n generated by some automorphism σ:

$$\textmd{Aut}\left( R^{\prime}/R\right) =<\sigma>= \left\{1,\sigma, {\ldots} ,\sigma^{n-1}\right\} \text{.} $$

Moreover, for $\alpha \in R^{\prime }$, $\ \sigma \left (\alpha \right ) =\alpha$ iff α∈R, see [14, Theorem 14.30].

If f(x) is a basic irreducible polynomial of degree n over Z/(p ^e), then all the roots of f(x) belong to $GR\left ( p^{en},p^{e}\right )$. Moreover if α is such a root in $GR\left (p^{en},p^{e}\right )$, then $\alpha ,\sigma \left (\alpha \right ) ,{\ldots } ,\sigma ^{n-1}\left (\alpha \right )$ are all the roots of f(x) in $GR\left (p^{en},p^{e}\right )$, where σ is the generator of the cyclic group $\textmd {Aut}\left (GR(p^{en},p^{e})/GR(p^{e},p^{e})\right )$.

To prove Proposition 1, we need the following four lemmas.

Lemma 6

([15, Theorem 2]) Let p ^e be a prime power and $f\left (x\right )$ a monic polynomial of degree n over Z/(p ^e) that has no multiple factors over Z/(p). Suppose α ₀ ,α ₁ ,…,α _n−1 are all roots of $f\left (x\right )$ in $GR\left (p^{em},p^{e}\right )$ for some integer m. Then for any $\underline {a}=(a(t))_{t\geq 0}\in G(f(x),p^{e})$ , there uniquely exists $\beta _{0},\beta _{1},{\ldots } ,\beta _{n-1}\in GR\left (p^{em},p^{e}\right )$ such that

$$ a\left( t\right) =\beta_{0}{\alpha_{0}^{t}}+\beta_{1}{\alpha_{1}^{t}}+{\ldots} +\beta_{n-1}\alpha_{n-1}^{t}\text{,}t \geq 0\text{.} $$

(9)

Inversely, if a sequence $\underline {a}=(a(t))_{t\geq 0}$ over Z/(p ^e) satisfies (9), then $\underline {a}\in G(f(x),p^{e})$.

Lemma 7

([16, Proposition 6.1]) Let p be a prime number and $f\left (x\right )$ a primitive polynomial of degree n ≥ 2 over Z/(p). Let $\underline {a}\in G^{\prime }(f(x),p)$ and s a positive integer. Then the minimal polynomial of $\underline {a}^{\left (s\right ) }$ is irreducible over Z/(p) with degree dividing n and

$$per \left( \underline{a}^{\left( s\right)}\right) =\frac{p^{n}-1}{\gcd \left( p^{n}-1,s\right)}\text{.} $$

Lemma 8

([17]) Let p ^e be a prime power and $\underline {a}=(a(t))_{t\geq 0}$ a sequence over Z/(p ^e). Then the minimal polynomial g(x) of $\underline {a}$ over Z/(p ^e) is unique iff g(x) is a basic irreducible polynomial.

Lemma 9

([18, Theorem 11.1]) Let p ^e be a prime power and $f\left (x\right )$ a basic irreducible polynomial of degree n over Z/(p ^e). Suppose α is a root of $f\left (x\right )$ in $GR\left (p^{en},p^{e}\right )$ , then per(f(x),p ^e ) = $ord\left (\alpha \right )$ , where $ord\left (\alpha \right )$ is the least positive integer s such that α ^s =1.

Now we start to prove Proposition 1.

Proof

(Proof of Proposition 1) Let g(x) be a minimal polynomial of $\underline {a}^{\left (s\right )}$ over Z/(p ^e). Then it is clear that $g\left (x\right ) \left (\bmod {~p}\right )$ is a characteristic polynomial of $\left [\underline {a}^{\left (s\right )} \right ]_{\bmod {p}}$ over Z/(p). By Lemma 8, it suffices to show that g(x) is a basic irreducible polynomial polynomial of degree n over Z/(p ^e) only depending on f(x).

Let h(x) be the minimal polynomial of $\left [\underline {a}^{\left (s\right )}\right ]_{\bmod {p}}$ over Z/(p). Then it follows from Lemma 7 that h(x) is irreducible over Z/(p) with degree dividing n and

$$per \left( \left[\underline{a}^{(s)}\right]_{\bmod{~p}}\right) =\frac{p^{n}-1}{\gcd \left( p^{n}-1,s\right)}\text{.} $$

Since $\frac {p^{n}-1}{\gcd \left (p^{n}-1,s\right )}>p^{n/2}$ by assumption, it follows that $\deg h\left (x\right ) =n$(for otherwise $\deg h(x)\leq n/2$, which yields $per\left ( \left [\underline {a}^{(s)}\right ]_{\bmod {p}}\right ) =per(h(x),p)\leq p^{n/2}-1$, a contradiction). Since $g\left (x\right ) \left (\bmod {~p}\right )$ is a characteristic polynomial of $\left [ \underline {a}^{\left (s\right )}\right ]_{\bmod {p}}$ over Z/(p), we have

$$ \deg g(x)=\deg \left( g(x)\left( \bmod{~p}\right)\right)\geq \deg h(x)=n\text{.} $$

(10)

On the other hand, let $R^{\prime }=GR\left ( p^{en},p^{e}\right )$, R=Z/(p ^e), and $\textmd {Aut}\left ( R^{\prime }/R\right )=<\sigma >$. Suppose α is a root of $f\left (x\right )$ in $R^{\prime }$, then $\alpha ,\sigma \left (\alpha \right ) ,{\ldots } ,\sigma ^{n-1}\left (\alpha \right )$ are all the roots of $f\left (x\right )$ in $R^{\prime }$. By Lemma 6 there uniquely exist $\beta _{0},\beta _{1},{\ldots } ,\beta _{n-1}\in R^{\prime }$ such that

$$a\left( t\right)=\beta_{0} \alpha^{t}+\beta_{1}(\sigma \left( \alpha \right))^{t}+{\ldots} +\beta_{n-1}(\sigma^{n-1}\left( \alpha \right))^{t} ~\text{for}~t\geq 0\text{,} $$

and so

$$ a^{\left( s\right)}\left( t\right)=a(st)=\beta_{0}(\alpha^{s})^{t}+\beta_{1}(\sigma \left( \alpha^{s}\right))^{t}+{\ldots} +\beta_{n-1}(\sigma^{n-1}\left( \alpha^{s}\right))^{t}~\text{for}~t\geq 0\text{.} $$

(11)

Let k be the least positive integer such that $\sigma ^{k}\left (\alpha ^{s}\right )=\alpha ^{s}$. It is clear that k∣n and $\alpha ^{s},\sigma \left (\alpha ^{s}\right ) ,{\ldots } ,\sigma ^{k-1}\left (\alpha ^{s}\right )$ are pairwise distinct. Then (11) can be rewritten as

$$a^{\left( s\right)}\left( t\right) =\beta_{0}^{\prime}(\alpha^{s})^{t}+\beta_{1}^{\prime}(\sigma \left( \alpha^{s}\right))^{t}+{\ldots} +\beta_{n-1}^{\prime}(\sigma^{k-1}\left( \alpha^{s}\right))^{t}~\text{for}~ t\geq 0\text{,} $$

where $\beta _{i}^{\prime }=\sum \limits _{j=0}^{\left (n/k\right )-1} \beta _{jk+i}$ for 0≤i≤k−1. Set

$$m(x)=\prod\limits_{i=0}^{k-1}\left( x-\sigma^{i}\left( \alpha^{s}\right) \right) \text{.} $$

Since $\sigma \left ( m(x)\right )=m(x)$ and m(x) is a monic polynomial over Z/(p ^e), it follows from Lemma 6 that m(x) is a characteristic polynomial of $\underline {a}^{\left (s\right )}$ over Z/(p ^e), and so

$$ \deg g(x)\leq \deg m\left( x\right)=k\leq n\text{.} $$

(12)

Combining (10) and (12) we obtain that $\deg g\left (x\right )=n$. Now we have

$$\deg \left( g(x)(\bmod{~p})\right)=\deg g(x)=n=\deg h(x)\text{,} $$

it follows that both $g(x)\left ( \bmod {~p}\right )$ and h(x) are the minimal polynomial of $\left [\underline {a}^{\left ( s\right ) }\right ]_{\bmod {p}}$ over Z/(p), and so we get that $g(x)\left (\bmod {~p}\right ) =h(x)$ (since it is well-known that the minimal polynomial of a sequence over the finite field Z/(p) is unique). Thus we have showed that $g\left (x\right )$ is a basic irreducible polynomial of degree n over Z/(p ^e), then by Lemma 8 the minimal polynomial of $\underline {a}^{\left (s\right )}$ over Z/(p ^e) is unique. Moreover, it can be seen from the process of the proof above that n=k and $g(x)=\prod \limits _{i=0}^{n-1}\left (x-\sigma ^{i} \left (\alpha ^{s}\right ) \right )$, and so g(x) is obviously only depending on f(x). Finally, by Lemma 9 we have

$$per(g(x),p^{e})=ord(\alpha^{s})=\frac{ord(\alpha)}{\gcd \left( ord(\alpha \right),s)}= \frac{per(f(x),p^{e})}{\gcd \left( per(f(x),p^{e}),s\right)}\text{,} $$

thus $per(g(x),p^{e})=\frac {p^{e-1}(p^{n}-1)}{\gcd \left (p^{e-1}(p^{n}-1),s\right )}$ . This completes the proof. □