I know that two permutations are conjugate if they have the same cycle structure. For example $\sigma_{1} = (1,2,3)(4,5,6)(8,9,12)$ and $\sigma_{2}=(4,5,1)(2,3,8)(12,9,7)$ are adjoin.
Is it true to say that two permutations are conjugate if they have the same order? the order of $\sigma_{1}$ and $\sigma_2$ is $3$ so it fits. But is it true for all permutations?
No. In $S_4$, $(1\ \ 2)$ and $(1\ \ 2)(3\ \ 4)$ both have order $2$, but they are not conjugate.