How to show the two numbers are coprime?

Let $p$ be a prime common factor.

With a pocket calculator one can obtain the following.
$7^{13}+6=7(7^{12}-1)+13=13\left (7\frac{7^{12}-1}{13}+1\right)=13\times7453000801=13\times 61\times122180341$. The fact that the number $122180341$ is prime can be used to give a simple proof that there is no prime $p$. However, the issue is whether one can obtain this result without using a computer.

Let $g$ be the g.c.d. of $1001$ and $p-1$ and use Fermat's little theorem. Then $p=2kg+1$ for some positive integer $k$ and $2^{g}-1\equiv 0\pmod p.$ Note that $g\in\{1,7,11,13,77,91,143,1001\}.$

Possible ways of dealing with these are illustrated below.

If the g.c.d. is 7

$2^7-1=127$ and then $p=127$ is not a factor of $122180341$. The cases $1,11,13$ are similarly impossible.

If the g.c.d. is 1001

Then $p=2002k+1$ and, since $122180341\equiv 283\pmod {2002},$ there is a positive integer $l$ such that $$122180341=(2002k+1)(2002l+283)$$ Then we have $$61029=2002kl+283k+l$$ $$\frac{61029}{kl}=2002+\frac{283}{l}+\frac{1}{k}.$$ Then $27\le kl\le 30$ and the equation has no solution.

The cases $g\in\{77,91,143\}$ are (just about!) manageable by this method but considerably more involved. An efficient but not very elegant method which solves these cases on a pocket calculator is illustrated below for $g=77$.

$$\frac{2^{77}-1}{2^{11}-1}=1+(1+2^{33})(2^{11}+2^{22}+2^{33})$$ $$=1+37310723\times 41507074$$ (I split this product up manually) $$\equiv 26295054\pmod {122180341}.$$ Then, applying the Euclidean algorithm, g.c.d.$(26295054,122180341)=1)$ and therefore this case is not possible.