As pointed out in fibonatic's answer, you didn't actually use the Nyquist stability criterion by just computing gain or phase margins. The latter cannot generally be used to check the stability of a system. Instead, gain and phase margins are used to describe the robustness of a stable system with respect to changes in gain or phase. This means that the use of gain and phase margins assumes stability a priori.
The Nyquist stability criterion uses the trace of the open loop transfer function $G(s)$ in the complex plane to check the stability of the corresponding closed-loop transfer function.
The figures below show the traces of $G(s)$ for two different values of $K$ ($K=5$ and $K=15$). The traces show the behavior of $G(s)$ for $s=j\omega$ with $\omega$ moving from $-\infty$ to $\infty$. What is not shown in the plots is the path connecting the branches labeled $\omega=0^-$ and $\omega=0^+$. That path is a circle with an infinite radius moving clockwise $1.5$ times around the origin of the complex plane. That means that in the left plot, which corresponds to an unstable system, the point $-1+j0$ (the red cross) is encircled twice in a clockwise fashion. Consequently, according to the Nyquist stability criterion, the closed-loop transfer function has two poles in the right half-plane. The plot on the right shows the trace of a stable system. There is no clockwise encirclement of the point $-1+j0$, i.e., that point is always to the left of the trace.
Note that for the stable system (the plot on the right), the point where the phase of $G(j\omega)$ equals $\pm 180$ degrees, i.e., the point where the trace crosses the real axis lies to the left of $-1+j0$, i.e., it corresponds to a magnitude $|G(j\omega)|>1$. This means that the gain margin is negative even though the system is stable. Consequently, a negative gain margin does not generally imply that the system is unstable, and, vice-versa, form the left plot we see that a positive gain margin does not generally imply stability.