Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $G=\mathbf{Z}/18\mathbf{Z}\times \mathbf{Z}/60\mathbf{Z}$ and consider the group homomorphism $f\colon G\to G\colon x\mapsto 4x$. In other words, $f(x)=x+x+x+x$.

Let $f^k$ denote the $k$-th composite of $f$ with itself, where $f^1=f$. How can I find the smallest $k\ge2$ such that $f^k=f$?

share|cite|improve this question

$f$ is a surjective mapping of $G$ onto the subgroup $\mathbb{Z}/9\mathbb{Z} \times \mathbb{Z}/15\mathbb{Z}$ and is bijective there. In this ring you want to find $k \ge 2$ minimal such that $f^{k-1} = id$, so $4^{k-1} = 1$.

The order of $4$ in $\mathbb{Z}/9\mathbb{Z}$ is $3$ and the order of $4$ in $\mathbb{Z}/15\mathbb{Z}$ is 2, so you will need $6 | k-1$. The smallest such $k$ is $7$.

share|cite|improve this answer
+1 for beating me by 54 seconds. A nice trick to move it to that subgroup. Not necessary, of course, but it is easier to compute the order of an element in a group, and that is the largest subgroup with the property that the restriction of $f$ to it is bijective. – Jyrki Lahtonen Jun 24 '12 at 19:49

The $k^{th}$ iterate $f^k$ maps the element $(a,b)\mapsto (4^ka, 4^kb)$. In particular this has to hold, when $a=1=b$, so we need to have $4^k\equiv4$ modulo both $18$ and $60$. This is clearly also sufficient.

Modulo $60$ the powers of $4$ repeat cyclically: $4,16,64\equiv4, 16,\ldots$, so here any odd $k$ works. Modulo $18$ the powers repeat in a 3-cycle: $4,16,64=10,40=4$, so $k$ needs to be A) odd, B) congruent to $1\pmod3$. The smallest such $k$ is $7$.

share|cite|improve this answer

Note that $f(a,b)=(4a,4b)$, and thus $f^k(a,b)=(4^ka,4^kb)$. Therefore, $f^k=f$ only when $4^ka=4a$ for all $a\in \mathbb{Z}/18\mathbb{Z}$, and $4^kb=4b$ for all $b\in\mathbb{Z}/60\mathbb{Z}$. If this is true for $a=1$ and $b=1$, then it is true for all $a$ and $b$; and certainly the reverse implication is true.

Thus, we want the smallest $k$ such that $4^k\equiv 4\bmod 18$ and $4^k\equiv 4\bmod 60$. To finish, prove that $$4^k\equiv \begin{cases} 10\bmod 18 & \text{ if }k\equiv 0\bmod 3,\\ 4\bmod 18&\text{ if }k\equiv 1\bmod 3,\\ 16\bmod 18&\text{ if }k\equiv 2\bmod 3\end{cases}$$ and $$4^k\equiv \begin{cases} 16\bmod 60 & \text{ if }k\equiv 0\bmod 2,\\ 4\bmod 60&\text{ if }k\equiv 1\bmod 2\end{cases}$$ and find the smallest $k\geq 2$ such that $k\equiv 1\bmod 3$ and $k\equiv 1\bmod 2$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.