4
$\begingroup$

Let $x$, $y$, $n$ be positive integers, where $n$ and $y$ shall be constants and $x$ a variable. Then it is trivial that the period of

$x \bmod y$

in $x$ is $y$, since the function simply drops to zero and starts over when $x$ reaches $y$. Now, for me at least, it is much less obvious, what the period of

$x^n \bmod y$

in $x$ should be. Visually (looking at plots of the function at different $n$ and $y$) the results suggest that the period still stays $y$. How can I see that analytically?

  • 0
    I believe the functions in question are $f_1(x)=[x]_y$ and $f_2(x)=[x^n]_y$. Clearly $f_1$ is periodic with period $y$, as $f_1(x+y)=[x+y]_y=[x]_y=f_1(x)$ for all $x$, and also if $f_1(x+z)=f_1(x)_y$ for all $x$, then $y$ divides $z$; thus $z=y$ is the smallest positive integer with this property. It is also easily shown that $f_2(x+y)=[(x+y)^n]_y=[x^n]_y=f_2(x)$ for all $x$ (why?). What is the smallest positive $z$ so that $f_2(x+z)=f_2(x)$ for all $x$?2012-08-21

2 Answers 2

6

There are many cases where the period is $y$ (and, as Andre points out, many cases where it is not). If $y$ is squarefree (that is, if there is no integer $d\gt1$ such that $y$ is a multiple of $d^2$), then $x^n$ is zero if and only if $x$ is 0 (modulo $y$), so the period has to be $y$.

4

The period need not be $y$. For example, let $y=9$, and consider the function $x^3$. This has period $3$. One can build many similar examples.