Vtyjkyuk

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.

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)=7cdot139$

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)=7cdot
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. $975to21to3$);




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




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




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

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

Therefore, on applying Fermat's Little Theorem

$(2^10)^97$ . $2^2$ $equiv(51)^97.2^2mod 973$ $notequiv1mod 973$

Hence, $973$ is not a prime number

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.