
#1
May 11th, 2016,
11:55
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^{p1}=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 $p1$. 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]$.

May 11th, 2016 11:55
# ADS
Circuit advertisement

MHB Seeker
#2
May 11th, 2016,
13:07
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$$
Last edited by Klaas van Aarsen; May 11th, 2016 at 15:40.
Reason:
Fix

#3
May 11th, 2016,
16:03
Thread Author
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^{n1}\}$. Therefore, in considering an arbitrary polynomial in $\mathbb{Z}/n\mathbb{Z}[x]$ it is sufficient to consider only powers up to $n1$, i.e., an arbitrary polynomial is $c_0+c_1x+\dots+c_{n1}x^{n1}$.
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^{p1} \equiv 1 \pmod p$ since one can multiply or divide both sides by $a$?

MHB Master
#4
May 11th, 2016,
18:37
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^{p1}=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 $p1$. 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$.

#5
May 11th, 2016,
19:49
Thread Author
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 singlevariable polynomial it is sufficient to consider $c_0+c_1x+\dots+c_{n1}x^{n1}$ 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.

MHB Seeker
#6
May 11th, 2016,
21:03
Quote:
This does not hold for all $p$, and for prime $p$ how is it more general than $a^{p1} \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^{p1} \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^{n1}\}$. Therefore, in considering an arbitrary polynomial in $\mathbb{Z}/n\mathbb{Z}[x]$ it is sufficient to consider only powers up to $n1$, i.e., an arbitrary polynomial is $c_0+c_1x+\dots+c_{n1}x^{n1}$.
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)$.

MHB Master
#7
May 12th, 2016,
01:20
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 singlevariable polynomial it is sufficient to consider $c_0+c_1x+\dots+c_{n1}x^{n1}$ 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^{n1}a$ belong to $\langle a\rangle$. Thus $a^n\in \{1,a,\ldots, a^{n1}\}$.

#8
May 12th, 2016,
17:22
Thread Author
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?

MHB Master
#9
May 12th, 2016,
23:26
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$.

#10
May 13th, 2016,
19:15
Thread Author
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 singlevariable polynomial it is sufficient to consider $c_0+c_1x+\dots+c_{n1}x^{n1}$ 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 $n1$. That is, if I prove that some function is not represented by a polynomial of degree $n1$, 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$.
Last edited by Evgeny.Makarov; May 13th, 2016 at 19:25.