# Thread: Powers of elements in Z/nZ

1. 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]$.

2.

3. 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$$

Originally Posted by I like Serena
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}$.

Originally Posted by I like Serena
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$?

5. Originally Posted by 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]$.
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$.

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?

Originally Posted by Euge
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.

7. Quote:
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.

Originally Posted by Evgeny.Makarov
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}$.
Originally Posted by Evgeny.Makarov
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)$.

8. Originally Posted by Evgeny.Makarov
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}\}$.

Originally Posted by I like Serena
Yes, the sequence is eventually periodic, with some period that divides $\phi(n)$.
Originally Posted by Euge
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?

10. Originally Posted by Evgeny.Makarov
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$.

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

Originally Posted by Evgeny.Makarov
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$.