# Determining if $973$ is prime

Without a calculator, determine if $973$ is prime or not

I was given this question to solve. I know $973$ is not prime. I was told a strategy to solve whether a number is prime or not is to test all the numbers less than the square root of $973$

So I would have to test till $32$

and i find $1,7,139$ and $973$ are factors of this number. Basically, what I want to find out is are there any other strategies to solve this question? then i wouldn't have to check till 1-32 to see if any of the numbers are factors.

• It suffices to try primes below $\sqrt n$, so here you need only test $2,3,5,7$ and the fourth test already succeeds. If $n$ were prime, you'd only go on testing $11,13,17,19,23,29,31$, so only $11$ instead of $32$ trial divisions ... Oct 25 '15 at 21:06
• Do you know the Erathostene's sieve? Oct 25 '15 at 21:10
• And since the non divisibilities by 2, 3 and 5 are trivial, you are left with checking the divisibility by 7, which reduces successively to testing 973, 273 (take 700 away), 63 (take 210 away), bingo (table of 7).
– Did
Oct 25 '15 at 21:25
• One should test all of the primes less than or equal to the square root of the number. Otherwise we would wrongly conclude, e.g., that $9$ is prime. Oct 25 '15 at 21:38
• @EmilioNovati, if i had to guess Erathostene's sieve would go hand in hand with hagenvoneitzen point
– mika
Oct 25 '15 at 23:54

Another method is $973 = 1000-27$ which can be represented as $(10)^3-(3)^3$

Therefore, applying the identity that $(a)^3-(b)^3=(a-b)(a^2+b^2+ab)$, we see that

$973=(10)^3-(3)^3=(10-3)(100+9+30)=7\cdot139$

• Well found, but in practice that's about the only application case of $10^3-a^3$. In general, finding factorizable expressions can take a lot of work.
– user65203
Aug 24 '18 at 10:01

Not a clean method though but I used Fermat's factorization to find that,

$(31)^2<973<(32)^2$

Now applying the fact that a perfect square should end only in 0,1,4,5,6,9 , concentrate only on those numbers the difference of whose square and $973$ give these digits in the last place. Therefore concentrate only on those number whose last digit is either $2,3,7$ as the difference of squares of such numbers and 973 would end in numbers whose digits either end with $1$ or $9$.

Concentrating on such numbers and with a little bit of trial, we find that $(73)^2 - 973 = 5329 - 973 = 4356 = (66)^2$

Therefore, $973=(73-66)(73+66)=7\cdot 139$

Hence $973$ is not a prime.

For small numbers, there is no much better strategy than trying all prime divisors up to the square root.

Use divisibility criteria for the tiny divisors.

• $2$: check the last digit even;

• $3$: compute the sum of the digits (e.g. $975\to21\to3$);

• $5$: last digit must be $0$ or $5$;

• $7$: subtract twice the unit digits from the rest of the number (e.g. $973\to91\to7$);

• $11$: subtract the unit digits from the rest of the number (e.g. $2585\to253\to22$).

Alternatively, we can apply Fermat's Little Theorem where in if $p$ is a prime number and $a$ is any integer not divisible by $p$ then

$a^{p-1} \equiv1 \mod p$

In this case, we can chose $a$ to be $2$ so as to keep things simple.

It's not hard to see that $(2)^{10}= 1024 \equiv51\mod973$

Therefore, on applying Fermat's Little Theorem

$(2^{10})^{97}$ . $2^2$ $\equiv(51)^{97}.2^2\mod 973$ $\not\equiv1\mod 973$

Hence, $973$ is not a prime number

Another way, $$973 = 910+63$$

This gives $$973 = 7.(130+9) = 7 . 139$$

If you're good at arithmetic, you can try this without a calculator $:)$

Wilson's theorem:

$p$ prime $\iff$ $(p-1)! \equiv -1 \pmod p$.

Else, pocklington's test could be fast.

• It's $\mod p$, not $\mod p-1$. Also how exactly is someone supposed to calculate $972!$ in their head? If you know of some faster trick using Wilson's theorem, an explanation should be given. Oct 25 '15 at 21:21