For all integers $x,y,z$, let \[S(x,y,z) = (xy - xz, yz-yx, zx - zy).\] Prove that for all integers $a$, $b$ and $c$ with $abc>1$, and for every integer $n\geq n_0$, there exists integers $n_0$ and $k$ with $0<k\leq abc$ such that \[S^{n+k}(a,b,c) \equiv S^n(a,b,c) \pmod {abc}.\] ($S^1 = S$ and for every integer $m\geq 1$, $S^{m+1} = S \circ S^m.$ $(u_1, u_2, u_3) \equiv (v_1, v_2, v_3) \pmod M \Longleftrightarrow u_i \equiv v_i \pmod M (i=1,2,3).$)
Problem
Source: Turkey TST 2001 - P3
Tags: modular arithmetic, parameterization, number theory proposed, number theory
20.07.2013 17:41
The problems asks to find the period of $S$. After some $n_0$, the modular sequence $S_{n_0}, S_{n_0 + 1}, S_{n_0 + 2}, \dots, S_{n_0 + abc}, S_{n_0 + abc +1}, \dots$ is periodic. Normally, there are $(a\cdot b\cdot c)\cdot (a\cdot b\cdot c) \cdot (a\cdot b\cdot c) = a^3b^3c^3$ triples in $\mod abc$. So we showed that for $0<k\leq a^3b^3c^3$, $S$ is periodic. But we can do better. If $S_0 = (a,b,c)$, the first parameter of each $S_i$ should be multiple of $a$ because by definition $S_1 = (ab-ac, bc-ba, ca-cb)$. Same for the other parameters. So in $\mod abc$, there are $bc$ ways to select the first parameter. So our value set for the parameters has at most $bc\cdot ac \cdot ab = a^2b^2c^2$. We can do better. Since the sum of parameters of $S$ is $ab-ac+bc-ba+ca-cb=0$; if we choose the first two parameters of $S$, the third will be automatically congruent to $ -a-b \mod {abc}$. So there are at most $bc\cdot ac = abc\cdot c$. In fact, it is $abc\cdot \min(a,b,c)$. Can we get out of this ugly $\min$ part? We can do better. Since the first parameter is multiple of $a$, the second is multiple of $b$, and the third is multiple of $c$, and sum of them is $0$; but we count more. For all pairs $(a,b)$, we find $c$ from $a+b+c \equiv 0 \pmod {abc}$, but this third parameter is not multiple of $c$. Lemma: Let $\gcd (a,b,c)=1$, $0\leq x < rbc$, and $0\leq y < rac $. $ax+by \equiv 0 \pmod c$ has $r^2abc$ solutions. Proof: Let $\gcd (b,c)=d$. By definition $\gcd (a,d)=1$. Let $x=0$. $by \equiv 0 \pmod c \Rightarrow d\cdot \frac bd \cdot y \equiv 0 \pmod c$. $\Rightarrow \frac bd \cdot y \equiv 0 \pmod {\frac cd} \Rightarrow y \equiv 0 \pmod {\frac cd}$. So # of $y$'s for $x=0$ is $\frac {rac}{\frac cd} = rad$. Since $ax+by \equiv 0 \pmod d$ and $b \equiv 0 \pmod d$, $ax \equiv 0 \pmod d$. Also we have $\gcd (a,d)=1$, $x\equiv 0 \pmod d$. # of $x$'s is $\frac{rbc}{d}$. So there are $\frac{rbc}{d}\cdot rad = r^2abc$ integer pairs $(x,y)$. $\blacksquare$ Back to the original problem: Let $\gcd (a,b,c)=r$. In that case, Let $a = r\alpha$, $b = r\beta$, $c = r\theta$. So $\gcd(\alpha, \beta, \theta) = 1$. $S_0 = (a,b,c) \Rightarrow S_1 = (r\alpha r\beta - r\alpha r\theta, r\beta r\theta - r\beta r\alpha, r\theta r\alpha - r\theta r \beta)$. Since $abc = r^3\alpha\beta \theta$ and the first parameter is always multiple of $r^2 \alpha$, there are $\frac {r^3\alpha \beta \theta}{r^2\alpha} = r\beta \theta$ ways to select the first parameter. Using above lemma for $\gcd(\alpha, \beta, \theta) = 1$, $0\leq x < r\beta\theta$, and $0\leq y < r\alpha\theta$, we get $r^2\alpha \beta \theta$ solutions. $r^2 \alpha \beta \theta \leq r^3 \alpha \beta \theta = abc$. So the sequence $S$ can get at most $abc$ different values. $\blacksquare$