It seems the most usual way to define matrix similarity is as follows:
"Let $A$ and $A'$ be two n-by-n matrices, we say they are similar if there exist some invertible n-by-n matrix $P$ such that $A=PA'P^{-1}$"
However in my first course of linear algebra we defined it this way:
"Let $A$ and $A'$ be two n-by-n matrices, we say they are similar if there exist two invertible n-by-n matrices $C$ and $D$ such that $A=CA'D^{-1}$"
And I guess the reason we defined it this way was because we were thinking of matrices as representing linear transformations, so from that definition (the latter one) we deduced that if $A$ and $A'$ were two matrices associated to a linear operator in different bases, then $C$ and $D$ were just the change of basis matrices.
Now, what I want to understand is how can I find a matrix $P$, like in the first definition, given the matrices $C$ and $D$ of the second definition, is $P$ a function of $C$ and $D$? I want to prove the equivalence between both definitions, the implication from the first one to the second one is obvious, but I don't realize how to prove the other implication.
The first definition you cite is the usual definition for matrix similiarity, under this definition, two matrices are similar, if they can represent the same linear transformation $V \to V$ under a change of basis, where in domain and codomain the same basis is used.
The second definition defines another thing, two matrices fulfilling it are usually called equivalent, not similar. Two matrices are equivalent if they can represent the same linear transformation $V \to W$ under a change of basis in domain and codomain, where both bases are unrelated.
For example $$ A = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}, \quad B = \begin{pmatrix} 1 & 0\\ 0 & 0\end{pmatrix} $$ and not similar, but equivalent.