Find Jordan Decomposition of $\left(\begin{smallmatrix} 4 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 3 \end{smallmatrix}\right)$ over $\mathbb{F}_5$ 
Find the Jordan decomposition of
$$
A := \begin{pmatrix} 4 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 3 \end{pmatrix}
\in M_3(\mathbb{F}_5),
$$
where $\mathbb{F}_5$ is the field modulo 5.

What I've done so far
The characteristic polynomial is
\begin{equation}
P_A(t) = (4 - t)(1-t)(3-t) - (1-t)
= -t^3 + 8t^2-18t+1
\equiv 4t^3 + 3t^2 + 2t + 1 \mod5.
\end{equation}
Therefore, $\lambda = 1$ is a zero of $P_A$, since $4+3+2+1 = 10 \equiv 0 \mod 5$.
By polynomial division one obtains
$$
P_A(t)
= (t + 4)(4t^2 + 2t + 4)
= (t + 4)(t + 4) (4t + 1)
\equiv 4 (t + 4)^3
$$
Therefore $\lambda = 1$ is the only eigenvalue of $A$.
To find the eigenspace we calculate the kernel of $A + 4 E_3$ and obtain
$$
\text{span}\left( \begin{pmatrix} 1 \\ 0 \\ 2 \end{pmatrix}, \begin{pmatrix} 1 \\ 1 \\ 2 \end{pmatrix} \right)
$$
Since $(A + 4 E_3)^2 = 0$, the kernel of $(A + 4 E_3)^2$ is the whole space.
Now, I choose $v := (1, 0, 0) \in \text{ker}(A + 4 E_3)^2$ such that $v \not\in \text{ker}(A + 4 E_3)$.
We calculate $(A + 4E)v = (3, 0, 1)$ and then
$$
(A + 4E)
\begin{pmatrix} 3 \\ 0 \\ 1\end{pmatrix}
= \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix},
$$
but the zero vector can't be a basis vector of our Jordan decomposition.
Have I made a mistake in my calculations?
 A: Your calculations are fine. However, by definition of kernels, an element of the kernel of $(A+4E)^2$ vanishes when applying $A+4E$ to it twice, so you should not be surprised. You just made the wrong conclusion. The eigenvector $(3,0,1)$ together with the generalized eigenvector $(1,0,0)$ form part of a Jordan basis giving you a Jordan block of size $2$. All you need to do is add another eigenvector which is linear independent to $(3,0,1)$, for example $(1,1,2)$.
Then
$$
\begin{pmatrix}
3 & 1 & 1 \\
0 & 0 & 1 \\
1 & 0 & 2
\end{pmatrix}^{-1}
\begin{pmatrix}
4 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 3
\end{pmatrix}
\begin{pmatrix}
3 & 1 & 1 \\
0 & 0 & 1 \\
1 & 0 & 2
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix}.
$$
A: Since $(A-I)(1,0,0)^T=(3,0,1)^T=3(1,0,2)^T$, a desired ordered basis is given by $\{(1,0,2)^T,\frac13(1,0,0)^T,(1,1,2)^T\}=\{(1,0,2)^T,(2,0,0)^T,(1,1,2)^T\}$.
A: You want three independent vectors, $v_1,v_2,v_3$ that have the properties:
$$Av_1=v_1, Av_2=v_2+v_1, Av_3=v_3.\tag{1}$$
For $v_2=(1,0,0)^T$ not in the eigenspace, we get $v_1=Av_2-v_2=(3,0,1)^T$ [*] and then you need a $v_3$ which is in the eigenspace of $A$ but not a multiple of $v_1.$ We'll choose $v_3=(0,1,0)^T.$ Then if $$S=\begin{pmatrix}v_1&v_2&v_3\end{pmatrix}=\begin{pmatrix}3&1&0\\0&0&1\\1&0&0\end{pmatrix}$$ then we can show:
$$J=\begin{pmatrix}1&1&0\\0&1&0\\0&0&1\end{pmatrix}=S^{-1}AS$$
Since $Se_i=v_i$ and the equalities in (1) and and $S^{-1}v_i=e_i,$ so we get $$Je_1=e_1,Je_2=e_1+e_2,Je_3=e_3$$
Since $\det S = 1$ even in the integers, we can use Wolfram Alpha to invert $S$ over the integers and get $$S^{-1}=\begin{pmatrix}0&0&1\\1&0&-3\\0&1&0
\end{pmatrix}$$

[*] Note that since $(A-E_3)^2=0,$ you have $A^2-A=A-E_3$ and hence, when $v_1=Av_2-v_2,$ you have $Av_1=(A^2-A)v_2=(A-E_3)v_2=Av_2-v_2=v_1.$

We could have started with any $v_2$ not in the eigenspace. We'll always get some multiple of our original $v_1$ for $v_1.$ Then $v_3$ can be any of $20$ vectors in the eigenspace not a multiple of $v_1.$
A: Here is a 4th answer that takes into account that we are in a particular case yielding a reduction to a $2 \times 2$ matrix.
Indeed, up to a simultaneous permutation $P$ on lines and columns, $A=PBP^{-1}$ is similar to 
$$B:= \left(\begin{array}{cc|c} 4 & 1 & 0 \\ 1 & 3 & 0 \\ \hline 0 & 0 & 1 \end{array}\right)$$
On this form, we have reduced the issue to find a Jordan form for $2 \times 2$ upper block $U$.
A quick computation shows that $1$ is a double eigenvalue of $U$. 
The Jordan form of $U$ is :
$$\left(\begin{array}{cc} 1 & 1 \\ 0 & 1  \end{array}\right)$$
because (due to a quick reasoning, that has been developed in the other answers, but with simpler computations) :
$$\underbrace{\left(\begin{array}{cc} 1 & 2 \\ 2 & 0  \end{array}\right)}_{Q}\left(\begin{array}{cc} 1 & 1 \\ 0 & 1  \end{array}\right)\underbrace{\left(\begin{array}{cc} 0 & 3 \\ 3 & 1  \end{array}\right)}_{Q^{-1}}=\left(\begin{array}{cc} 4 & 1 \\ 1 & 3  \end{array}\right).$$
The Jordan form of $B$, which is the same as the Jordan form of $A$, is thus :
$$J:= \left(\begin{array}{cc|c} 1 & 1 & 0 \\ 0 & 1 & 0 \\ \hline 0 & 0 & 1 \end{array}\right).$$
