2
$\begingroup$

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$?

3 Answers 3

1

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$.

1

$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$.

  • 0
    +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.2012-06-24
1

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$.