Two Matrices $A$ and $B$ are similar if and only if their characteristic Matrices $xI_n-A$ and $xI_n-B$ are equivalent. As a part of an advanced junior undergraduate Linear Algebra course we're trying to prove the following statement: "Two Matrices $A$ and $B$ are similar if and only if their characteristic Matrices $xI_n-A$ and $xI_n-B$ are equivalent." where as $A,B \in K^{n \times n}$ , $xI_n-A \in K[x]$ , $K $ is a Field and $K[x]$ is the polynomial ring over $K$.
Equivalence of   $xI_n-A$ and $xI_n-B$ in $K[x]$ is defined as:  $xI_n-A$ and $xI_n-B$ are equivalent if there exists invertible matrices $S$ and $T$ in $K[x]$ such that $S(xI_n-B)T=xI_n-A$ 
The first direction of the proof is quite easy, the second one however is much more difficult, in the textbook the lecturer uses an algebraic proof, without explaining the motivation behind it.
Here's an overview of the Proof
"$\Rightarrow$" There is an invertible Matrix $S$ such that $S^{-1}AS=B$, multiplication of $S^{-1}(xI_n-A)S$  yields $xI_n-B$
"$\Leftarrow$"  Let $S,T$ be invertible Matrices in $K[x]^{n\times n}$ such that  $S(xI_n-B)T=xIn-A$ 
For every Matrix $C \in K[x]^{n \times n}$ there are Matrices $C_i \in K^{n \times n}$ such that $C= \sum_{x=0}^{m}x^iC_i$
Using this definition we get: $C(A)= \sum_{x=0}^{m}A^iC_i \in K^{n\times n}$ for $A \in K^{n \times n}$
Which implies that for Matrices $C,D \in K[x]^{n\times n}$ and $A \in K^{n \times n}$:
$$
\begin{align*}(C+D)(A) = C(A) + D(A)\end{align*}
$$
$$
\begin{align*}(C \cdot D)(A) = (C(A)\cdot D)(A)\end{align*}
$$
One can verify that $A \cdot S(A) = S(A) \cdot B \quad$ (1) and using induction we get $A^i \cdot S(A) = S(A) \cdot B^i \quad , \forall i \in \mathbb{N}$ 
We now prove that $S(A)$ is invertible. Because $S \in K[x]^{n\times n}$ is invertible there is $C \in K[x]^{n\times n}$ such that $S \cdot C= I_n$ using the previous results one can verify that $S(A) \cdot C(B)= I_n$ which implies that $S(A)$ is invertible which implies using (1) that  $S(A)^{-1} \cdot A \cdot S(A) =B$ and thus the result.
So here is my question: how could an undergraduate student come up with the idea for such proof, what are the main ideas/observations that could lead to it?
If there is actually no intuition behind the proof, do you know of any alternative solutions to prove it? I've tried to work on it myself but I didn't come far, the reason is that we used this proof to use the Smith Normal form to build the theory of the rational/Frobenius normal form and then the Jordan normal form that's why I would appreciate a proof that doesn't assume the rational form
 A: I will answer the second part of your question, that is, I will give an alternative solution to prove it. 
The alternative solution rests on an interesting interpretation of equivalence, and an interpretation of similarity. 
Here's the interpretation : 

Let $R$ be a ring (commutative, with unit) and $M,N\in M_n(R)$. Then if $M,N$ are equivalent, the quotient $R$-modules $R^n/MR^n$ and $R^n/NR^n$ are isomorphic. 

This is almost obvious (in fact it's even true more generally, as you can allow $M,N$ not to be square matrices): Let $P,Q \in GL_n(R)$ be such that $PM = NQ$. Then you have a commutative square $\require{AMScd} \begin{CD} R^n @>M>> R^n \\
@VQVV @VPVV \\
R^n @>N>>R^n\end{CD}$
Since $P,Q$ are isomorphisms, it follows that the cokernels of $M,N$ are isomorphic, that is $R^n/MR^n \cong R^n/NR^n$. Explicitly, the isomorphism is given by $[v] \mapsto [Pv]$ (*).
Now here's the interpretation of similar matrices : if $M\in M_n(R)$ is a matrix, then $R^n$ has an induced $R[x]$ module structure, defined by $P\cdot v  = P(M)v$. I'll denote this by $R^n_M$ (this is not a standard notation, as far as I know)

Let $R$ be a ring (commutative, with unit) and $M,N\in M_n(R)$. Then $M,N$ are similar if and only if the induced $R[x]$-modules $R^n_M$ and $R^n_N$ are isomorphic. 

The proof is easy : if $PM= NP$ with $P\in GL_n(R)$ then the following diagram commutes 
$\require{AMScd} \begin{CD} R^n @>M>> R^n \\
@VPVV @VPVV \\
R^n @>N>>R^n\end{CD}$
from which it follows by an easy induction that $P: R^n_M\to R^n_N$ is an $R[x]$-module morphism (and it is then obviously an isomorphism). 
Conversely, let $f: R^n_M\to R^n_N$ be an isomorphism. In particular it is an $R$-module ismorphism $R^n\to R^n$ so it is represented by some $P\in GL_n(R)$. Then since it is an $R[x]$-isomorphism, $f(xv) = xf(v)$ so $PM = NP$, and $M,N$ are similar. 
We are now ready to assemble these two interpretations to give a proof. 
Suppose $xI_n - M, xI_n - N$ are equivalent. Then we apply the first result to $R= K[x]$ to get that the $K[x]$-modules $K[x]^n/(xI_n - M)K[x]^n$ and $K[x]^n/(xI_n-N)K[x]^n$ are isomorphic. But now (exercise !) $K[x]^n/(xI_n - M)K[x]^n \cong K^n_M$ as $K[x]$-modules, and similarly $K[x]^n/(xI_n-N)K[x]^n\cong K^n_N$. 
So all in all, $K^n_M \cong K^n_N$ as $K[x]$-modules. We may now apply the second interpretation to $R=K$ to conclude that $N,M$ are similar. 
This may seem like a more complicated proof, but it is more conceptual and in fact it is more intuitive, as it doesn't rely on computations whose origin we may not understand but on important interpretations of equivalence and similarity. 
Now if you try to explicit out some concrete computations from this conceptual proof, you will end up with the same computations as those your lecturer gave you. 
Quite concretely, if $P(xI_n - M) = (xI_n-N)Q$ with $P,Q\in GL_n(K[x])$, and if you follow "my" proof, the matrix you get is the matrix of $[v]\mapsto [Pv]$ in $K[x]^n/(xI_n-M)K[x]^n\to K[x]^n/(xI_n-N)K[x]^n$. But if you write out $P= \sum_k x^k P_k$, then $Pe_i = \sum_k x^k P_k e_i = \sum_k M^k P_ke_i$ modulo $xI_n = M$, so that the matrix that this proof spits out is precisely what your lecturer called $P(M)$. So in fact, without knowing it at first, I answered your first question (or at least tried to): I gave the conceptual reason for this choice, so in a sense I gave some intuition for these computations.
(*) if you're not comfortable with all this abstract stuff you can give a very hands-on proof : this is well-defined because if $v = Mw$ then $Pv = PMw = NQw$ so if $[v] = 0, [Pv] = 0$ as well; it is surjective because $P$ is; and if $[Pv] = 0$ then $Pv = Nw$ for some $w$, so $Pv = NQQ^{-1}w = PMQ^{-1}w $ so $v= MQ^{-1}w$ and so $[v] = 0$
