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$


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?

  • $\begingroup$ $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 :-) $\endgroup$ – Jyrki Lahtonen Sep 18 '17 at 6:49

we can write, $$255255=$$ 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.

  • $\begingroup$ Why 21? What about the prime 19? $\endgroup$ – Robert Z Sep 18 '17 at 7:16
  • $\begingroup$ Oh thanks for pointing out, i will change it now $\endgroup$ – 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.