MHB Exploring the Periodicity of Powers in Modular Arithmetic

[Evgeny.Makarov]

This is a basic question about the behavior of $a^k$ for $a\in\mathbb{Z}/n\mathbb{Z}$ and $k=1,2,\dots$. I know that Fermat's little theorem says $a^{p-1}=1$ in $\mathbb{Z}/p\mathbb{Z}$ for prime $p$; thus, the sequence $1,a,a^2,a^3,\dots$ is periodic with period at most $p-1$. More generally, by Euler's theorem $a^{\varphi(n)}=1$ in $\mathbb{Z}/n\mathbb{Z}$ if $(a,n)=1$, so $1,a,a^2,a^3,\dots$ is periodic with period at most $\varphi(n)$. But what happens when $(a,n)\ne1$?

The motivation for the question is to find out the general form of a polynomial in $\mathbb{Z}/n\mathbb{Z}[x]$.

 

[I like Serena]

Hi Evgeny,

Suppose $(a,n)=d$, then:
$$(a/d)^{\phi(n/d)} \equiv 1 \pmod{n/d}
\quad\Rightarrow\quad (a/d)^{\phi(n/d)} d \equiv d \pmod{n} $$

Btw, we also have the more general form of Fermat's little theorem:
$$a^p \equiv a \pmod p$$

 

[Evgeny.Makarov]

Suppose $(a,n)=d$, then:
$$(a/d)^{\phi(n/d)} \equiv 1 \pmod{n/d}
\quad\Rightarrow\quad (a/d)^{\phi(n/d)} d \equiv d \pmod{n} $$

How does it help figuring out what happens with the powers of $a$? What I want to prove at a minimum is that $a^n\in\{a^0,\dots,a^{n-1}\}$. Therefore, in considering an arbitrary polynomial in $\mathbb{Z}/n\mathbb{Z}[x]$ it is sufficient to consider only powers up to $n-1$, i.e., an arbitrary polynomial is $c_0+c_1x+\dots+c_{n-1}x^{n-1}$.

Btw, we also have the more general form of Fermat's little theorem:
$$a^p \equiv a \pmod p$$

This does not hold for all $p$, and for prime $p$ how is it more general than $a^{p-1} \equiv 1 \pmod p$ since one can multiply or divide both sides by $a$?

 

[Euge]

This is a basic question about the behavior of $a^k$ for $a\in\mathbb{Z}/n\mathbb{Z}$ and $k=1,2,\dots$. I know that Fermat's little theorem says $a^{p-1}=1$ in $\mathbb{Z}/p\mathbb{Z}$ for prime $p$; thus, the sequence $1,a,a^2,a^3,\dots$ is periodic with period at most $p-1$. More generally, by Euler's theorem $a^{\varphi(n)}=1$ in $\mathbb{Z}/n\mathbb{Z}$ if $(a,n)=1$, so $1,a,a^2,a^3,\dots$ is periodic with period at most $\varphi(n)$. But what happens when $(a,n)\ne1$?

The motivation for the question is to find out the general form of a polynomial in $\mathbb{Z}/n\mathbb{Z}[x]$.

If $(a,n) \neq 1$, periodicity of $a$ is not guaranteed. For example, when $n = 8$ and $a = 6$, we have $a^3 = 0$, so there exists no positive integer $n$ such that $a^n = 1$.

 

[Evgeny.Makarov]

I am studying discrete functions. There is a theorem that every function $f:(\mathbb{Z}/p\mathbb{Z})^k\to\mathbb{Z}/p\mathbb{Z}$ can be represented as a polynomial iff $p$ is prime. When $p$ is not prime, some functions can be represented as polynomials, and some, such as $\max(x,y)$, cannot. One can determine if a function $f(x)$ can be represented as a polynomial using the method of undetermined coefficients: simply consider a polynomial with unknown coefficients, substitute different arguments for $x$ and equate it to the value of $f(x)$. If the resulting system of linear equations on coefficients has a solution, then $f(x)$ can be represented as a polynomial.

In considering an arbitrary polynomial, I need to know its degree. I believe that in $\mathbb{Z}/n\mathbb{Z}$ for any $n$, whether prime or not, in the case of a single-variable polynomial it is sufficient to consider $c_0+c_1x+\dots+c_{n-1}x^{n-1}$ because $x^n=x^k$ for some $k<n$. Therefore, the sequence $x^0,x^1,\dots$ is eventually periodic, and the whole period occurs before $x^n$. Is this so?

If $(a,n) \neq 1$, periodicity of $a$ is not guaranteed. For example, when $n = 8$ and $a = 6$, we have $a^3 = 0$, so there exists no positive integer $n$ such that $a^n = 1$.

OK, but the sequence is eventually periodic starting from $6^3=0$. For $n=8$ we have $x^5=x^3$, so it is sufficient to consider polynomials of degree 4.

 

[I like Serena]

This does not hold for all $p$, and for prime $p$ how is it more general than $a^{p-1} \equiv 1 \pmod p$ since one can multiply or divide both sides by $a$?

Yes, we're talking about a prime $p$.
Your version has the unmentioned restriction that it only holds if $(a,p)=1$.
The $a^{p} \equiv a \pmod p$ version holds for any $a$.

Note that if $(a,p)\ne 1$, that means that $a$ is a multiple of $p$, and then dividing by $a$ actually means:
$$a^{p-1} \equiv 1 \equiv 0 \pmod 1$$
which is rather useless.

How does it help figuring out what happens with the powers of $a$? What I want to prove at a minimum is that $a^n\in\{a^0,\dots,a^{n-1}\}$. Therefore, in considering an arbitrary polynomial in $\mathbb{Z}/n\mathbb{Z}[x]$ it is sufficient to consider only powers up to $n-1$, i.e., an arbitrary polynomial is $c_0+c_1x+\dots+c_{n-1}x^{n-1}$.

OK, but the sequence is eventually periodic starting from $6^3=0$. For $n=8$ we have $x^5=x^3$, so it is sufficient to consider polynomials of degree 4.

Ah okay.
Yes, the sequence is eventually periodic, with some period that divides $\phi(n)$.

 

[Euge]

In considering an arbitrary polynomial, I need to know its degree. I believe that in $\mathbb{Z}/n\mathbb{Z}$ for any $n$, whether prime or not, in the case of a single-variable polynomial it is sufficient to consider $c_0+c_1x+\dots+c_{n-1}x^{n-1}$ because $x^n=x^k$ for some $k<n$. Therefore, the sequence $x^0,x^1,\dots$ is eventually periodic, and the whole period occurs before $x^n$. Is this so?

Yes. This has to do with the monoidal structure of $\Bbb Z/n\Bbb Z$ under multiplication. Given $a\in \Bbb Z/n\Bbb Z$, the cyclic submonoid $\langle a \rangle$ generated by $a$ has order $k \le n$. By closure under multiplication in $\langle a\rangle$, it follows that $a^{k+1} = a^k a, a^{k+2} = a^{k+1}a,\ldots, a^n = a^{n-1}a$ belong to $\langle a\rangle$. Thus $a^n\in \{1,a,\ldots, a^{n-1}\}$.

 

[Evgeny.Makarov]

Yes, the sequence is eventually periodic, with some period that divides $\phi(n)$.

Given $a\in \Bbb Z/n\Bbb Z$, the cyclic submonoid $\langle a \rangle$ generated by $a$ has order $k \le n$.

Thanks, ILS and Euge. Could you point to theorems that support the quoted claims or say what the idea of the proof is?

 

[Euge]

Thanks, ILS and Euge. Could you point to theorems that support the quoted claims or say what the idea of the proof is?

Every finite monoid is periodic. That is, given a finite monoid $(M,\cdot,e)$ and $a\in M$, the set $\langle a\rangle :=\{a^m :m\in \Bbb N_0\}$ is finite.

Proof. Since $M$ is a monoid, closure under $\cdot$ is satisfied; so $a^2 = a\cdot a \in M$ and inductively, for all $m\in \Bbb N_0$, $a^m\in M$. The sequence $\{e,a,a^2,\ldots\}$ is therefore a subset of $M$, which is finite since $M$ is finite. QED

The set $\langle a\rangle$ is a monoid in its own right and is called the cyclic submonoid generated by $a$.

 

[Evgeny.Makarov]

I am sorry, my question about the second quote from post #8 was trivial, but the question from post #5 is still unanswered.

In considering an arbitrary polynomial, I need to know its degree. I believe that in $\mathbb{Z}/n\mathbb{Z}$ for any $n$, whether prime or not, in the case of a single-variable polynomial it is sufficient to consider $c_0+c_1x+\dots+c_{n-1}x^{n-1}$ because $x^n=x^k$ for some $k<n$. Therefore, the sequence $x^0,x^1,\dots$ is eventually periodic, and the whole period occurs before $x^n$. Is this so?

When I am wondering about $x^n=x^k$ for some $k<n$, I need to know that this holds for all $x$ and the same $k$. Then I don't need to consider polynomials whose degree is higher than $n-1$. That is, if I prove that some function is not represented by a polynomial of degree $n-1$, it is not represented by any polynomial. If all is known is that $x^n=x^k$ for some $k<n$ that may depend on $x$, for all I know $f(x)=x^n$ may be a different function, distinct from all previous degrees of $x$.

 

[Euge]

I am sorry, my question about the second quote from post #8 was trivial, but the question from post #5 is still unanswered.

When I am wondering about $x^n=x^k$ for some $k<n$, I need to know that this holds for all $x$ and the same $k$. Then I don't need to consider polynomials whose degree is higher than $n-1$.

A polynomial over $\Bbb Z/2\Bbb Z$ cannot be satisfied by both $1$ and $0$ and also be degree one, so did you mean you want to consider polynomials whose degree does not exceed $n$?

 

[I like Serena]

I am sorry, my question about the second quote from post #8 was trivial, but the question from post #5 is still unanswered.

Okay, okay, so the first quote may or may not be true - I'm not sure.
Either way, $\left< a \right>$ has a size that divides $\phi(n)$, which is the size of $(\mathbb Z/n \mathbb Z)^\times$.
That is, the number of distinct powers of $a$ divides $\phi(n)$.
That, at least, follows from Lagranges theorem.

 

[Evgeny.Makarov]

A polynomial over $\Bbb Z/2\Bbb Z$ cannot be satisfied by both $1$ and $0$ and also be degree one, so did you mean you want to consider polynomials whose degree does not exceed $n$?

For $\Bbb Z/2\Bbb Z$ we have $x^2=x^1$ for all $x$; therefore, the set of functions represented by polynomials from $\Bbb Z/2\Bbb Z[x]$ coincides with the set of functions represented by $\{a_0+a_1x\mid a_0,a_1\in\mathbb{Z}_2\}$. Considering polynomials of higher degrees does not increase the set of functions, though it increases the set of formal polynomials.

Either way, $\left< a \right>$ has a size that divides $\phi(n)$, which is the size of $(\mathbb Z/n \mathbb Z)^\times$.
That is, the number of distinct powers of $a$ divides $\phi(n)$.
That, at least, follows from Lagranges theorem.

This holds when $(a,n)=1$. For such $x$ we have $x^{\varphi(n)}=1$. If this happened for all $x$, there would be no reason to consider polynomials whose degree is $\varphi(n)$ or higher.

 

[Euge]

For $\Bbb Z/2\Bbb Z$ we have $x^2=x^1$ for all $x$; therefore, the set of functions represented by polynomials from $\Bbb Z/2\Bbb Z[x]$ coincides with the set of functions represented by $\{a_0+a_1x\mid a_0,a_1\in\mathbb{Z}_2\}$. Considering polynomials of higher degrees does not increase the set of functions, though it increases the set of formal polynomials.

We were looking at different things -- I considered only $\Bbb Z/2\Bbb Z[x]$ while you considered the quotient ring $(\Bbb Z/2\Bbb Z)[x]/(x^2 - x)$. In that case, I have a clearer idea what you're looking for algebraically. To my knowledge there is no guarantee that in general, the relation $x^n = x^k$ must hold over $\Bbb Z/n\Bbb Z$. But if $n \ge 2$, you may consider the polynomial

$$f(x) = \prod_{i = 1}^r (x^{p_i} - x)^{\alpha_i}$$

where $p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ is the prime factorization of $n$. It is satisfied by $\Bbb Z/n\Bbb Z$ and has degree $\sum_{i = 1}^r \alpha_i p_i$, which is less than or equal to $\prod_{i = 1}^r p_i^{\alpha_i} = n$.

 

[Evgeny.Makarov]

We were looking at different things -- I considered only $\Bbb Z/2\Bbb Z[x]$ while you considered the quotient ring $(\Bbb Z/2\Bbb Z)[x]/(x^2 - x)$.

The important thing is what claim is made about these objects. My claim is that both sets of polynomials give rise to the same set of functions.

But for $n > 2$, you may consider the polynomial

$$f(x) = \prod_{i = 1}^r (x^{p_i} - x)^{\alpha_i}$$

where $p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ is the prime factorization of $n$. It is satisfied by $\Bbb Z/n\Bbb Z$ has degree $\sum_{i = 1}^r \alpha_i p_i$, which is less than $\prod_{i = 1}^r p_i^{\alpha_i} = n$.

Do I understand correctly that $f(x)=0$ for every $x\in \mathbb{Z}/n\mathbb{Z}$ and therefore $x^{\sum_{i = 1}^r \alpha_i p_i}$ can be represented as a polynomial of a smaller degree? So the largest degree that has to be considered in an arbitrary polynomial is $\sum_{i = 1}^r \alpha_i p_i-1$. Is it easy to see that $f(x)=0$ for all $x$? Could you give a proof outline or reference?

 

[Euge]

Do I understand correctly that $f(x)=0$ for every $x\in \mathbb{Z}/n\mathbb{Z}$ and therefore $x^{\sum_{i = 1}^r \alpha_i p_i}$ can be represented as a polynomial of a smaller degree? So the largest degree that has to be considered in an arbitrary polynomial is $\sum_{i = 1}^r \alpha_i p_i-1$.

Yes, that's correct.

Is it easy to see that $f(x)=0$ for all $x$? Could you give a proof outline or reference?

It is a consequence of Fermat's little theorem. Let $x$ be an integer. Fix $i\in\{1,2,\ldots,r\}$. By Fermat's little theorem, $p_i$ divides $x^{p_i} - x$. Therefore $p_i^{\alpha_i}$ divides $(x^{p_i} - x)^{\alpha_i}$. Now then $p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ divides the product $\prod_{i = 1}^r (x^{p_i} - x)^{\alpha_i}$, that is, $n$ divides $f(x)$. Since $x$ was arbitrary, $f(x)$ is divisible by $n$ for all integers $x$. Reducing modulo $n$, $f(x) = 0$ for all $x\in \Bbb Z/n\Bbb Z$.

 

[Evgeny.Makarov]

Thanks a lot, Euge and ILS.