Determine all totally multiplicative and non-negative functions $f\colon\mathbb{Z}\rightarrow \mathbb{Z}$ with the property that if $a, b\in \mathbb{Z}$ and $b\neq 0$, then there exist integers $q$ and $r$ such that $a-qb+r$ and $f(r)<f(b)$.
To determine all totally multiplicative and non-negative functions \( f: \mathbb{Z} \rightarrow \mathbb{Z} \) with the given properties, we will analyze the conditions step by step.

1. **Totally Multiplicative Property**:
   A function \( f \) is totally multiplicative if for all \( a, b \in \mathbb{Z} \), we have:
   \[
   f(a \cdot b) = f(a) \cdot f(b)
   \]

2. **Non-negative Function**:
   The function \( f \) is non-negative, meaning \( f(n) \geq 0 \) for all \( n \in \mathbb{Z} \).

3. **Division Algorithm Property**:
   For any \( a, b \in \mathbb{Z} \) with \( b \neq 0 \), there exist integers \( q \) and \( r \) such that:
   \[
   a = qb + r \quad \text{and} \quad f(r) < f(b)
   \]
   Here, \( r \) is the remainder when \( a \) is divided by \( b \), and \( 0 \leq r < |b| \).

4. **Initial Conditions**:
   From the given information, we have:
   \[
   f(0) = 0, \quad f(1) = f(-1) = 1, \quad f(x) = f(-x)
   \]

5. **Behavior for Positive Integers**:
   We are given that \( f(n) \geq \log_2(n+1) \) for \( n > 0 \).

Let's analyze these conditions in detail:

### Step-by-Step Analysis:

1. **Function at Zero**:
   \[
   f(0) = 0
   \]
   This is given directly.

2. **Function at One and Negative One**:
   \[
   f(1) = 1 \quad \text{and} \quad f(-1) = 1
   \]
   This is also given directly.

3. **Symmetry Property**:
   \[
   f(x) = f(-x)
   \]
   This implies that \( f \) is an even function.

4. **Totally Multiplicative Property**:
   For any \( a, b \in \mathbb{Z} \):
   \[
   f(a \cdot b) = f(a) \cdot f(b)
   \]

5. **Division Algorithm Property**:
   For any \( a, b \in \mathbb{Z} \) with \( b \neq 0 \), there exist integers \( q \) and \( r \) such that:
   \[
   a = qb + r \quad \text{and} \quad f(r) < f(b)
   \]
   Since \( 0 \leq r < |b| \), we need \( f(r) < f(b) \).

### Guessing the Form of \( f \):

Given the properties, let's test the guess \( f(n) = |n|^c \) where \( c \in \mathbb{Z}^* \).

1. **Check Totally Multiplicative Property**:
   \[
   f(a \cdot b) = |a \cdot b|^c = |a|^c \cdot |b|^c = f(a) \cdot f(b)
   \]
   This holds for any \( c \in \mathbb{Z}^* \).

2. **Check Non-negative Property**:
   \[
   f(n) = |n|^c \geq 0
   \]
   This holds for any \( c \in \mathbb{Z}^* \).

3. **Check Division Algorithm Property**:
   For \( a = qb + r \) with \( 0 \leq r < |b| \):
   \[
   f(r) = |r|^c < |b|^c = f(b)
   \]
   This holds for any \( c \in \mathbb{Z}^* \).

4. **Check Initial Conditions**:
   \[
   f(0) = 0^c = 0, \quad f(1) = 1^c = 1, \quad f(-1) = |-1|^c = 1
   \]
   These conditions are satisfied.

5. **Check Behavior for Positive Integers**:
   \[
   f(n) = |n|^c \geq \log_2(n+1)
   \]
   For \( c \geq 1 \), this inequality holds for all \( n > 0 \).

Thus, the function \( f(n) = |n|^c \) where \( c \in \mathbb{Z}^* \) satisfies all the given conditions.

The final answer is \( \boxed{ f(n) = |n|^c } \) where \( c \in \mathbb{Z}^* \).