Why is the function $f(x)=x^3 \pmod{10}$ periodic with this strange property?
I've noticed that the function $f(x)=x^3 \pmod{10}$ is periodic. For example, listing mod(x^3,10) we get:
0,1,8,7,4,5,6,3,2,9,0,1,8,7,4,5,6,3,2,9,0,1,8,7,4,5,6,3,2,9,0,1,8,7,4,5,6,3,2,9,0,1,8,7,4,5,6,3,2,9What's weird, though, is that the period contains all numbers from the image of the function exactly once. Why does that happen?
$\endgroup$ 33 Answers
$\begingroup$Short answer: because $10$ is squarefree and $3$ is relatively prime to $\phi(10) = \phi(5\cdot 2) = 4$.
If $m = p^2q$ is not squarefree, then $x^3$ will never be congruent to $p$ mod $m$, since if $m\vert (x^3-p)$, then $p\vert x$, leading to a contradiction since $p^2\nmid (x^3-p)$.
If $m$ is squarefree and 3 is relatively prime to $\phi(m)$, then $f(x)=x^3$ is a bijection; it is enough to show that every $0\leq a < m$ has a cube root mod $m$.
As Quiochu suggests, if $m$ is prime and 3 is relatively prime to $\phi(m)$, then there exist nonnegative integers $x,y$ with $3x = \phi(m)y+1$. Therefore for all $0\leq a < m$, $$(a^x)^3 = (a^{\phi(m)})^ya = a,$$ so every $a$ has a cube root $a^x$.
Now suppose $m=p_1 p_2\ldots p_k$ is squarefree but composite. Since 3 is relatively prime to $\phi(m)$, it is relatively prime to all $\phi(p_i)$. Then for every $0\leq a < m$, by the above you can find a cube root of $a$ mod $p_i$.
By the Chinese remainder theorem, there thus exists a $b$ with $$b^3 \equiv a \pmod {p_i}$$ for every $p_i$, and $b^3 \equiv a \pmod m$.
$\endgroup$ 3 $\begingroup$It has period dividing 10 because you are reducing things modulo 10. Modulo 10 is a congruence meaning that when arithmetic operations (addition, subtraction, multiplication, division by invertible things) are used with arguments that are equivalent modulo 10, the results are also equivalent modulo 10. e.g.
$$ a \equiv a' \mod 10 \qquad \text{and} \qquad b \equiv b' \mod 10 $$
imply
$$ a + b \equiv a' + b' \mod 10 $$
The fact your function takes every value modulo 10 can be thought of as a mild coincidence. It could have happened that way, or it could have happened otherwise, and it happened to happen that way for 10.
However, we can analyze when it happens. Consider
$$ f(x) = x^n \mod m$$
and we want this to take on every value modulo $m$.
One important idea is the Chinese Remainder Theorem; in this case, if $m = pq$ where $p$ and $q$ are relatively prime, then $f(x)$ has the property we desire if and only if both
$$ x^n \mod p \qquad \text{and} \qquad x^n \mod q $$
have the property. In this case, you can check:
- $x^3 \mod 2 = 0, 1, 0, 1, \cdots$
- $x^3 \mod 5 = 0, 1, 3, 2, 4, 0, 1, 3, 2, 4, \cdots$
Now, if $m = p^k$ where $p$ is a prime, then we need $k = 1$ or $n = 1$. If both $k > 1$ and $n>1$, then $p^n$ is divisible by $p^2$, and so is $p^n \bmod m$. Therefore, we can never have $x^n \equiv p \bmod m$.
Now, consider the case where $m$ is prime. An argument involving Euler's theorem implies that $f(x)$ has the property we want if and only if $\gcd(n, m-1) = 1$.
It turns out we can combine the above information into a single test: for $n > 1$ we have
- $f(x) = x^n \bmod m$ has the desired property iff $m$ is squarefree and $\gcd(n, \varphi(m)) = 1$.
Now, let's construct an example! Let $m = 3 \cdot 5 \cdot 7$. We need $n$ to be relatively prime to $2$, $4$, and $6$. The smallest value of $n$ bigger than $1$ that we can choose is 5: I claim the function
$$ f(x) = x^5 \bmod 105 $$
has the same property you observed: it has period 105, and it also takes every value modulo $105$.
This short python command tests my claim that it takes every value:
>>> len({ pow(x,5,105) for x in range(105) }) == 105
Trueand that a smaller value doesn't work:
>>> len({ pow(x,3,105) for x in range(105) })
45Oblique to the original question, but it may help if you want to explore further.
The integers modulo $10$ form a ring. This is true whatever the modulus. Basically that means that addition, subtraction, and multiplication work properly, including the distributive property. There may be $ab=0$ without $a=0$ or $b=0$. Being a ring means that $x^3 \pmod {10}=(x \pmod {10})^3 \pmod {10}$ or, informally, you can strip off all the digits except the units before cubing, then strip them off again after. What you have observed is that the function $x^3 \pmod {10}$ is injective.
$\endgroup$
