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

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?

• $255255=255\cdot1001$. An oft recurring useful fact is that $1001=7\cdot11\cdot13$. Here, additionally, $255=2^8-1=(2^4-1)(2^4+1)=3\cdot5\cdot17$. That's a lot of potential prime factors excluded :-) – Jyrki Lahtonen Sep 18 '17 at 6:49

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.

• Why 21? What about the prime 19? – Robert Z Sep 18 '17 at 7:16
• Oh thanks for pointing out, i will change it now – neonpokharkar Sep 18 '17 at 7:21

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

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$.

• Heh @JonatanB.Bastos was one minute faster :) – Mr Pie Sep 18 '17 at 7:10
• @user477343 Well, actually, this is not true. Check it out! ;-) – Robert Z Sep 18 '17 at 7:14