0
$\begingroup$

Suppose there is some positive integer n that is four digits long and is relatively prime to 100! (meaning n and 100! have no common factors other than 1). n must be prime, but why?

100! is a composite number, but composite numbers can be relatively prime to other composite numbers, so that can't be the reason n is prime. n being four digits long and 100! having factors that are all less than four digits must have something to do with it, but I can't wrap my head around the exact reason.

So, why does n have to be prime in this situation?

$\endgroup$
1
  • 1
    $\begingroup$ Assume that $n$ is not prime and contains a prime factor $p > 100$. What can you say about $\frac{n}{p}$? $\endgroup$
    – Rushy
    Commented Sep 19, 2021 at 22:51

1 Answer 1

Reset to default
6
$\begingroup$

Hint: suppose some number $n$ is not prime, but $n$ has no prime factors less than 100. That is, $n$ is the product of at least two prime numbers greater than 100. What's the smallest that $n$ could be?

$\endgroup$
1
  • 2
    $\begingroup$ Ah ha! If n is composite but has no prime factors less than or equal to 100, the smallest n could be would be five digits, so it must be prime. Thank you! $\endgroup$
    – OngoGablogian
    Commented Sep 19, 2021 at 23:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .