Determine whether 177 is a prime.

Question

The question is pretty straight forward... Determine if 177 is prime using the prime number theory.

I am confused what type of answer to give. The question doesn't seem to be asking for you to explore all $n < \sqrt{177}$ and check the gcd. This is the only way I know to assert a number is prime.

What other options are there?

Answer 1

There are some divisibility criteria that you can apply.

For example, an integer is divisible by $2$ if it ends with an even digit, and it is divisible by $3$ if the sum of digits is divisible by three, and it is divisible by $5$ if it ends with a $5$ or a $0.$

In this case you have $1+7+7=15,$ which is divisible by three, so $177$ is not prime.

Answer 2

$$177=100+70+7=(\text{multiple of $3$}+1)+(\text{multiple of $3$}+1)+(\text{multiple of $3$}+1)=\text{multiple of $3$}$$

Answer 3

A number is divisible by 3 if the sum of its digits is divisible by 3. 1+7+7=15 which is divisible by 3, so 177 is divisible by 3 and therefore not prime.

Answer 4

As others have pointed out, it's easy enough to see that $3\mid177$. But just for fun, here's a complicated way to show that $177$ is not a prime.

Since $177\equiv1$ mod $4$, the sum-of-two squares theorem says that if it were a prime, then it could be written as the sum of two squares, $177=a^2+b^2$. Letting $a=2m$ and $b=2n-1$ (one of them must be even, the other odd), we find $4m^2+4n^2+4n+1=177$, which simplifies to

$$m^2+n(n+1)=44$$

Now $n(n+1)$ is even, so $m$ must be even, which means $n(n+1)=44-m^2$ is a multiple of $4$, which means either $4\mid n$ or $4\mid(n+1)$. But clearly we must have $n\lt7$ (since $7\cdot8=56\gt44$), so it suffices to check whether $44-n(n+1)$ is a square for $n=4$ or $n=3$. But neither $44-4\cdot5=24$ nor $44-3\cdot4=32$ is a square. So $177$ is not a prime.