The basic of Euclidean algorithm more e.g. here. Having the polynomials $p,q$. We calculate
\begin{alignat*}{2}
p &= s_0\cdot q & &+ r_0\\
q &= s_1\cdot r_0 & &+ r_1\\
r_0 &= s_2 \cdot r_1 & &+ r_2\\
&\vdots & &\\
r_{n-3} &= s_{n-1}\cdot r_{n-2} & &+ r_{n-1}\\
r_{n-2} &= s_{n}\cdot r_{n-1} & &+ r_{n}.\\
\end{alignat*}
Each line means dividing one polynomial by other (you dividing $p$ by $q$ is the first row). $s_i$ and $r_j$ are also polynomials. $r_j$ are the remainders after the division. We do those steps while $r_n \neq 0$. If $r_n = 0$ then $\gcd{(p,q)} = r_{n-1}$.
Euclidean algorithm for $p(x), q(x)$.
$$
7x^3 + 6x^2 - 8x+4 = 7\cdot (x^3+x-2) + 6x^2-15x + 18
$$
So according to notation in the algorithm above $s_0(x) = 0$ and $r_0(x) = 6x^2-15x + 18$. No we divide $q(x)$ by $r_0(x)$
$$
x^3+x-2 = \left(\frac{1}{6}x + \frac{5}{12}\right)\cdot (6x^2-15x) + \frac{17}{4}x - \frac{19}{2}.
$$
So $s_1(x) = \frac{1}{6}x + \frac{5}{12}$ and $r_1(x) = \frac{17}{4}x - \frac{19}{2}$. Can you continue in this algorithm?
I found on the Web and, also on mathstack, several examples and I decided to write an answer.
Example of ring where the gcd of two elements doesn't exist:
Consider the ring $\Bbb Z[\sqrt{-d}]=\{a+bi\sqrt{-d} : a,b\in \Bbb Z\}$, $d\ge 3$ ($d$ free-square). Then in this paper D. Khurana has proved that:
Let $a$ be any rational integer such that $a\equiv d\quad (mod\quad 2)$ and let $a^2 + d = 2q$. Then the elements $2q$ and $(a+ i\sqrt{d})q$ do not have a $GCD$.
Two examples of ring where the lcm of two elements doesn’t exist:
I use the following theorem:
Let $D$ be a domain and $a,b\in D$.
Then, $\text{lcm}(a,b)$ exists if and only if for all $r\in D\setminus\{0\}$, $\gcd(ra,rb)$ exists.
$1)$Consider the ring $\Bbb Z[\sqrt{-d}]=\{a+bi\sqrt{-d} : a,b\in \Bbb Z\}$, $d\ge 3$ ($d$ free-square); and a rational integer $a$ such that $a\equiv d$ $(mod\quad 2)$, then $lcm(2,a+i\sqrt{d})$ doesn't exist. Indeed this follows from the previous theorem. Note that $GCD(2,a+i\sqrt{d})=1$.
$2)$ let $R$ be the subring of $\Bbb Z[x]$ consisting of the polynomials $\sum_i c_ix^i$ such that $c1$ is an even number. If we consider $p_1(x)=2$ and $p_2(x)=2x$, $lcm(p_1, p_2)$ doesn't exist.
Best Answer
In pretty much the same way -- by using Euclidean algorithm!
Dividing $f(x)$ by g(x) you get quotient 1 and remainder $x^2+x$, so you continue like this: $x^3+x^2+x+1=(x^3+1)\cdot1 + x^2+x$,
$x^3+1=(x^2+x)\cdot x + (-x^2+1)$,
$x^2+x = (-x^2+1)\cdot (-1) + x+1$,
$-x^2+1 = (x+1)\cdot (-x+1)$
so their gcd is $x+1$. Finding lcm now should not be hard.