Facebook Page
Twitter
RSS
+ Reply to Thread
Page 1 of 2 12 LastLast
Results 1 to 10 of 17
  1. MHB Master
    MHB Site Helper
    MHB Math Scholar

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    2,483
    Thanks
    533 times
    Thanked
    4,408 times
    Thank/Post
    1.775
    Awards
    MHB University Math Award (2018)  

MHB Humor Award (2017)  

MHB Discrete Mathematics Award (2017)  

MHB Chat Room Award (2016)  

MHB Humor Award (2016)
    #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. # ADS
    Circuit advertisement
    Join Date
    Always
    Posts
    Many
     

  3. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    Klaas van Aarsen's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Leiden
    Posts
    8,404
    Thanks
    5,436 times
    Thanked
    14,620 times
    Thank/Post
    1.740
    Awards
    MHB Pre-University Math Award (2018)  

MHB Model Helper Award (2017)  

MHB Best Ideas (2017)  

MHB Analysis Award (2017)  

MHB Calculus Award (2017)
    #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 by Klaas van Aarsen; May 11th, 2016 at 15:40. Reason: Fix

  4. MHB Master
    MHB Site Helper
    MHB Math Scholar

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    2,483
    Thanks
    533 times
    Thanked
    4,408 times
    Thank/Post
    1.775
    Awards
    MHB University Math Award (2018)  

MHB Humor Award (2017)  

MHB Discrete Mathematics Award (2017)  

MHB Chat Room Award (2016)  

MHB Humor Award (2016)
    #3 Thread Author
    Quote Originally Posted by I like Serena View Post
    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}$.

    Quote Originally Posted by I like Serena View Post
    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. MHB Master
    MHB Global Moderator
    MHB Math Scholar
    MHB POTW Director
    Euge's Avatar
    Status
    Offline
    Join Date
    Jun 2014
    Posts
    1,883
    Thanks
    1,884 time
    Thanked
    4,945 times
    Thank/Post
    2.626
    Awards
    MHB Topology and Advanced Geometry Award (2017)  

MHB Analysis Award (2017)  

MHB Advanced Algebra Award (2016)  

MHB Topology and Advanced Geometry Award (2015)  

MHB Analysis Award (2015)
    #4
    Quote Originally Posted by Evgeny.Makarov View Post
    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$.

  6. MHB Master
    MHB Site Helper
    MHB Math Scholar

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    2,483
    Thanks
    533 times
    Thanked
    4,408 times
    Thank/Post
    1.775
    Awards
    MHB University Math Award (2018)  

MHB Humor Award (2017)  

MHB Discrete Mathematics Award (2017)  

MHB Chat Room Award (2016)  

MHB Humor Award (2016)
    #5 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 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?

    Quote Originally Posted by Euge View Post
    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. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    Klaas van Aarsen's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Leiden
    Posts
    8,404
    Thanks
    5,436 times
    Thanked
    14,620 times
    Thank/Post
    1.740
    Awards
    MHB Pre-University Math Award (2018)  

MHB Model Helper Award (2017)  

MHB Best Ideas (2017)  

MHB Analysis Award (2017)  

MHB Calculus Award (2017)
    #6
    Quote 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.


    Quote Originally Posted by Evgeny.Makarov View Post
    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}$.
    Quote Originally Posted by Evgeny.Makarov View Post
    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. MHB Master
    MHB Global Moderator
    MHB Math Scholar
    MHB POTW Director
    Euge's Avatar
    Status
    Offline
    Join Date
    Jun 2014
    Posts
    1,883
    Thanks
    1,884 time
    Thanked
    4,945 times
    Thank/Post
    2.626
    Awards
    MHB Topology and Advanced Geometry Award (2017)  

MHB Analysis Award (2017)  

MHB Advanced Algebra Award (2016)  

MHB Topology and Advanced Geometry Award (2015)  

MHB Analysis Award (2015)
    #7
    Quote Originally Posted by Evgeny.Makarov View Post
    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}\}$.

  9. MHB Master
    MHB Site Helper
    MHB Math Scholar

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    2,483
    Thanks
    533 times
    Thanked
    4,408 times
    Thank/Post
    1.775
    Awards
    MHB University Math Award (2018)  

MHB Humor Award (2017)  

MHB Discrete Mathematics Award (2017)  

MHB Chat Room Award (2016)  

MHB Humor Award (2016)
    #8 Thread Author
    Quote Originally Posted by I like Serena View Post
    Yes, the sequence is eventually periodic, with some period that divides $\phi(n)$.
    Quote Originally Posted by Euge View Post
    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. MHB Master
    MHB Global Moderator
    MHB Math Scholar
    MHB POTW Director
    Euge's Avatar
    Status
    Offline
    Join Date
    Jun 2014
    Posts
    1,883
    Thanks
    1,884 time
    Thanked
    4,945 times
    Thank/Post
    2.626
    Awards
    MHB Topology and Advanced Geometry Award (2017)  

MHB Analysis Award (2017)  

MHB Advanced Algebra Award (2016)  

MHB Topology and Advanced Geometry Award (2015)  

MHB Analysis Award (2015)
    #9
    Quote Originally Posted by Evgeny.Makarov View Post
    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$.

  11. MHB Master
    MHB Site Helper
    MHB Math Scholar

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    2,483
    Thanks
    533 times
    Thanked
    4,408 times
    Thank/Post
    1.775
    Awards
    MHB University Math Award (2018)  

MHB Humor Award (2017)  

MHB Discrete Mathematics Award (2017)  

MHB Chat Room Award (2016)  

MHB Humor Award (2016)
    #10 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.

    Quote Originally Posted by Evgeny.Makarov View Post
    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 by Evgeny.Makarov; May 13th, 2016 at 19:25.

Similar Threads

  1. sum of k-powers and divisibility
    By Bibubo in forum Number Theory
    Replies: 8
    Last Post: December 3rd, 2014, 14:45
  2. [SOLVED] Powers of polylogarithms
    By ZaidAlyafey in forum Calculus
    Replies: 12
    Last Post: December 8th, 2013, 14:35
  3. Sum of fourth powers of N
    By mathworker in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 18
    Last Post: June 17th, 2013, 03:51
  4. Powers of Matrices
    By Petrus in forum Linear and Abstract Algebra
    Replies: 3
    Last Post: April 21st, 2013, 02:03
  5. [SOLVED] powers of z-1
    By dwsmith in forum Analysis
    Replies: 13
    Last Post: February 5th, 2012, 07:56

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards