Prove $373$ is prime when $\gcd(255255, 373) = 1$

Question

I needed to find $\gcd(255255, 373)$ and then explain why that proves $373$ to be prime. I understand the first part, but not the prime part at all. Here is how I figured the first part out using the euclidean algorithm:

$255255 = 684(373)+123$

$373 = 3(123)+4$

$123 = 30(4)+3 $

$4 = 1(3)+1$

$3=3(1)+0$

I could say that obviously $373$ would have no even divisors, and now I know that any factor of $255255$ (other than 1) would not be a factor of $373$, so is that connected somehow?

Answer 1

we can write, $$255255=3.5.7.11.13.17$$ Therefore $373$ is not divisible by $3,5,7,11,13,17$

If $373$ is not prime, $$373= k×z$$ Such that $k,n\in \text{ co-prime to }3,7,5,11,13,17\text{ and } \gt 17$ The lowest values of $k,z$ are $19$, but $$19.19=361$$ so we try next lowest possibility. $$19.21=399\gt 373$$

All the next numbers will give us value $\gt 373$

Hence we cannot get any $k,z$ whose multiplication equals $373$ as all of them will be $\ge 399\gt 373$

Hence $373$ is prime.

Answer 2

Hint. Note that $255255=3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17$ therefore $\gcd(255255,373)=1$ implies that if $373$ is not a prime then it should be divisible by $pq$ where $p$ and $q$ are two primes such that $17< p\leq q$.

Answer 3

Hint:$$255255=3\cdot 5\cdot 7\cdot 11\cdot 13 \cdot 17.$$