Tessellate S.T.E.M.S. (2019) - Mathematics - Category A (School) - Set 5 - Objective Problem 2

Number Theory Level 3

Let $n$ be a positive integer such that there exists a function $f: \mathbb{Z}_n \longrightarrow \mathbb{Z}_n$ satisfying $f(x) \neq x = f(f(x)) = f(f(f(x+1)+1)+1)$ for all $x \in \mathbb{Z}_n$ . Then find the set of possible remainders obtained on dividing $n$ by $4$ . (Here, $Z_n$ denotes the set of equivalence classes under the equivalence relation $(a,b):n|(a-b)$ , closed under addition, multiplication and taking additive inverses.)

This problem is a part of Tessellate S.T.E.M.S. (2019)

0,1,3, 2,3 0,1,2 2

1 solution

A Former Brilliant Member
Jan 4, 2019

what is obvious is that elements of $\mathbb{Z}_n$ should be in pairs (because of $f(x)\neq x = f(f(x))$ ), with respect to the function $f(x)$ , which automatically implies that $n$ is an even number. In other words, we have only cycles of two with respect to $f(x)$ .

The condition $f(f(f(x+1)+1)+1)=x \ \forall x\in \mathbb{Z}_n$ gives the clue that the number of cycles (of length 2) should be a multiple of $3$ . So, $n=2.3.k=6.k$ .

$6k \equiv 0,2 \ (mod \ 4)$ . The last option is the only option that is compatible with our result.

Tessellate S.T.E.M.S. (2019) - Mathematics - Category A (School) - Set 5 - Objective Problem 2

1 solution

0 pending reports