Exploring the Periodicity of Powers in Modular Arithmetic

  • MHB
  • Thread starter Evgeny.Makarov
  • Start date
  • Tags
    Elements
In summary, the behavior of $a^k$ for $a\in\mathbb{Z}/n\mathbb{Z}$ and $k=1,2,\dots$ is determined by Fermat's little theorem and Euler's theorem. However, if $(a,n)\ne1$, periodicity of $a$ is not guaranteed. When considering arbitrary polynomials in $\mathbb{Z}/n\mathbb{Z}[x]$, it is sufficient to consider only powers up to $n-1$. The theorem that every function $f:(\mathbb{Z}/p\mathbb{Z})^k\to\mathbb{Z}/p\mathbb{Z}$ can be represented as
  • #1
Evgeny.Makarov
Gold Member
MHB
2,436
4
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]$.
 
Physics news on Phys.org
  • #2
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:
  • #3
I like Serena said:
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}$.

I like Serena said:
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$?
 
  • #4
Evgeny.Makarov said:
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$.
 
  • #5
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?

Euge said:
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.
 
  • #6
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.
Evgeny.Makarov said:
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}$.

Evgeny.Makarov said:
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)$.
 
  • #7
Evgeny.Makarov said:
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}\}$.
 
  • #8
I like Serena said:
Yes, the sequence is eventually periodic, with some period that divides $\phi(n)$.

Euge said:
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?
 
  • #9
Evgeny.Makarov said:
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
I am sorry, my question about the second quote from post #8 was trivial, but the question from post #5 is still unanswered.

Evgeny.Makarov said:
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$.
 
Last edited:
  • #11
Evgeny.Makarov said:
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$?
 
  • #12
Evgeny.Makarov said:
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.
 
  • #13
Euge said:
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.

I like Serena said:
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.
 
  • #14
Evgeny.Makarov said:
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$.
 
  • #15
Euge said:
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.

Euge said:
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?
 
  • #16
Evgeny.Makarov said:
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.

Evgeny.Makarov said:
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$.
 
  • #17
Thanks a lot, Euge and ILS.
 

Related to Exploring the Periodicity of Powers in Modular Arithmetic

1. What does "Powers of elements in Z/nZ" mean?

The powers of elements in Z/nZ refer to the possible results when raising an element in the set Z/nZ to a certain exponent. Z/nZ is the set of integers modulo n, which means it only contains the remainders of integers when divided by n. The powers of elements in Z/nZ can be calculated using modular arithmetic.

2. How do you calculate the powers of elements in Z/nZ?

To calculate the powers of elements in Z/nZ, you can use modular exponentiation. This involves taking the element to a certain exponent, then finding the remainder when divided by n. This remainder is the power of the element in Z/nZ.

3. What is the significance of powers of elements in Z/nZ?

The powers of elements in Z/nZ have many applications in number theory and cryptography. They can be used to solve equations and prove theorems in number theory, and are also crucial in various encryption algorithms in cryptography.

4. Can all elements in Z/nZ be raised to any power?

No, not all elements in Z/nZ can be raised to any power. The powers of an element in Z/nZ are limited by the order of the element, which is the smallest positive integer k such that the element raised to the power of k is congruent to 1 modulo n.

5. How are the powers of elements in Z/nZ related to group theory?

The powers of elements in Z/nZ are closely related to group theory, as Z/nZ is an example of a cyclic group. The powers of an element in Z/nZ form a subgroup of the group, and the order of an element determines the order of the subgroup it generates.

Similar threads

  • Linear and Abstract Algebra
Replies
15
Views
1K
  • Math Proof Training and Practice
3
Replies
80
Views
4K
  • Linear and Abstract Algebra
Replies
4
Views
2K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
6
Views
2K
Replies
14
Views
3K
  • Linear and Abstract Algebra
Replies
11
Views
3K
  • Calculus and Beyond Homework Help
Replies
3
Views
633
  • Linear and Abstract Algebra
Replies
4
Views
2K
  • Linear and Abstract Algebra
Replies
17
Views
4K
Back
Top