Clearly, $f(0)=0$ and $f(\pm 1)=1$. The problem rephrases as follows: For each $a,b$, there exists $s\equiv a(\bmod\; b)$ or $s\equiv -a(\bmod\; b)$ such that $f(s)<f(b)$. From now on, we will be only working with positive variables. Let $\alpha(p)=\log_p(f(p))$. Case 1: There exists $p$ such that $\alpha(q)\ge \alpha(p)$ for all primes $q$ Claim: There exists at most one prime $q$ such that $\alpha(q)>\alpha(p)$. Proof: Suppose there are two such primes, call $q_1, q_2$. We select $b=p^k$. Clearly, for all $a>b$, $$f(a)=\prod\limits_{r\mid a} r^{\alpha(r) \nu_p(a)} \ge \left( \prod\limits_{r\mid a} r^{\nu_p(a)} \right)^{\alpha(p)} = a^{\alpha(p)} > b^{\alpha(p)} = f(b)$$ Therefore, we only need to focus on $a$ and $p^k-a$ for some $0<a<p^k$. We select $$a\equiv 0(\bmod\; q_1^{e_1})$$and $$a\equiv -p^k (\bmod\; q_2^{e_2})$$ Where $q_j^{e_j (\alpha(q_j)-\alpha(p))} \ge 3^{1+\alpha(p)}$ for $j=1,2$. If $k$ is large, we can guarantee $q_1^{e_1}q_2^{e_2} < p^{\frac k2}$, and therefore we can make sure $\frac b3 < a <\frac b2$. This means $$\prod\limits_{r\mid a} r^{\alpha(r) \nu_p(a)} \ge \left( \prod\limits_{r\mid a} r^{\nu_p(a)} \right)^{\alpha(p)} q_1^{e_1 (\alpha(q_1)-\alpha(p))} \ge \left(\frac{p^k}{3}\right)^{\alpha(p)} q_1^{e_1 (\alpha(q_1)-\alpha(p))}$$ $$\ge f(p^k) 3^{-\alpha(p) + 1 + \alpha(p)}$$ Similarly, $f(p^k-a) > f(p^k)$, so the claim is true. Therefore, there exists constants $c<d$ such that $\alpha(p)=c$ for all $p\ne q$, and $\alpha(q)=d$. One can check this function actually works; it suffices to check for $\gcd(a,b)=1$. If $q\nmid b$ then at least one of $a, b-a$ is not divisible by $q$ so we are good. Case 2: There exists an infinite sequence of primes $p_1, p_2, \cdots$ such that $\alpha(p_j)$ strictly decreases as $j$ increases. Claim: $f(b) > \min\{ f(s), f(b-s)\}$ for all $0<s<b$. Proof: The main observation is that there exists an infinite chain $x_1<x_2<\cdots$ such that $f(x_1)>f(x_2)>\cdots$ and $f(R(x_{i+1},x_i)) \ge f(x_i) \forall i\in \mathbb{N}$. Suppose $f(s), f(b-s) \ge f(b) > f(s+kb)$. Set $x_1=b, x_2=s+kb$. I have $x_i, x_{i+1}$ where $f(R(x_{i+1},x_i)) \ge f(x_i) > f(x_{i+1})$. If $f(x_{i+1}) \ge f(x_{i+1}-x_i)$, replace $x_{i+1}$ with $x_{i+1}-x_i$. This way, in the end, $x_{i+1}>x_i$ since $f(x_{i+1}) < f(x_i)$. Thus, $f(x_{i+1}) \le \min\{f(x_{i+1}-x_i), f(x_i)\}$. If I plug $a=x_i, b=x_{i+1}$ then there exists $r\equiv x_i$ or $r\equiv x_{i+1}-x_i (\bmod\; x_{i+1})$ such that $f(r)<f(x_{i+1})$. Set $x_{i+2}=r$ and we can verify $f(R(x_{i+2},x_{i+1})) \ge f(x_{i+1}) > f(x_{i+2})$, completing the "inductive step" Clearly there cannot be an infinite chain of length greater than $f(b)$, so it cannot exist.

As $\mathbb{N}_{\geq 0}$ is well-ordered, there exists some $z\in \mathbb{Z}$ such that $f(z)$ is the minimum. If $z\neq 0$, then there exists some $q,r\in\mathbb{Z}$ such that $zq+r=0$ and $f(r)<f(z)$, which is a contradiction with the choice of $z$. Therefore $f(z)$ achieves its minimum exactly when $z=0$. Now by the complete multiplicativity, we have $f(0)f(a)=f(0)$ for all $a\in\mathbb{Z}$. Therefore either $f(0)=0$ or $f(a)=1$ for all $a\in\mathbb{Z}$. However, if $f(a)=1$ for all $a\in\mathbb{Z}$, then $f(z)$ achieves its minimum everywhere, which is a contradcition. As a consequence, $f(0)=0$. We also have $f(1)^2=f(1)$, and as $f(1)>f(0)$ we see $f(1)=1$. By $f(-1)^2=f(1)$ we now deduce that $f(-1)=1$. Now if $f(b)=1$ for some $b\in\mathbb{Z}$, then we see that $f(r)<f(b)$ implies $r=0$. This shows that $b$ divides all integers, and thus $|b|=1$.

Suppose for the sake of contradiction that there exists some pair $(b,r)$ of no-nnegative integers with $0\leq r<b$ and $f(r),f(b-r)\geq f(b)$. Among those pairs, choose one such that $f(b)$ is the minimum. By the assumption given by the problem, and also that $f$ is even, there exists $b'\in \mathbb{N}_{\geq 0}$ such that $b'\equiv \pm r\mod b$ and $f(b')<f(b)$. Choose the smallest $b'$ that satisfies those. By the choice of $(b,r)$, we see that $b'>b$. By the minimality of $b'$, we have $f(b'-b)\geq f(b)>f(b')$. Hence $(b',b)$ is another pair with $f(b),f(b'-b)\geq f(b')$. However, since $f(b')<f(b)$, this contradicts the choice of $(b,r)$. Therefore such pair does not exist.

Assume for the sake of contradiction that $\log_{p_2}f(p_2)>\log_{p_3}f(p_3)$. Let $\alpha = \log_{p_2}f(p_2)$ and $\beta = \log_{p_3}f(p_3)$. Let $k$ be a sufficiently large integer to be chosen later. Let $N$ be another sufficiently large integer to be chosen later. Let $n$ be the element in $[N]\backslash \{1\}$ that maximizes the pair $(-\log_nf(n),n)$ with respect to the lexicographical order. If $n\leq \sqrt{N}$, then we see that $\log_{n^2}f(n^2) = \frac{1}{2}\log_nf(n)^2 = \log_nf(n)$ and thus $(\log_{n^2}f(n^2),n^2)$ has an even larger lexicographical order, which is a contradiction. Therefore $n>\sqrt{N}$. Let $\gamma = \log_nf(n)$. Note that if $N>p_3$ then $\gamma\leq \beta$. Now consider the equation $p_1^kx+p_2^ky=n$. Since $\gcd(p_1^k, p_2^k)=1$, by Bezout's there exist $x_0,y_0\in \mathbb{Z}$ such that $p_1^kx_0+p_2^ky_0=n$. In general we thus have $x = x_0+p_2^kt$ and $y=y_0-p_1^kt$ for $t\in\mathbb{Z}$. Pick $t$ so that $|p_1^kx-n/2|\leq p_1^kp_2^k/2$. Then we have $p_1^kx, p_2^ky \geq (n-p_1^kp_2^k)/2$. We will now show that the pair $(n,p_1^kx)$ contradicts the previous lemma as long as we choose the parameters $k,N$ properly. Indeed, pick $k$ such that $p_1^{k(\alpha-\beta)}, p_2^{k(\alpha-\beta)}\geq 4^{\beta}$, and then pick $N\geq \max((2p_1^kp_2^k)^2,p_3)$. Then $n> 2p_1^kp_2^k$ and so $p_1^kx, p_2^ky>n/4$. Moreover, we have that $f(p_1^kx) = f(p_1)^kf(x)\geq p_1^{k\alpha}x^{\gamma}\geq p_1^{k(\alpha-\beta)}(p_1^kx)^{\gamma}\geq (4p_1^kx)^{\gamma}\geq n^{\gamma}=f(n)$. Similarly, $f(p_2^ky)\geq f(n)$. This contradicts the previous lemma, as desired.