4

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.

mika
  • 857
  • 6
    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 ... – Hagen von Eitzen Oct 25 '15 at 21:06
  • Do you know the Erathostene's sieve? – Emilio Novati Oct 25 '15 at 21:10
  • 1
    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
  • 1
    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. – Travis Willse 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
  • also, lets say a number is divisible by $2$, then it would have to be divisble by $4,6,8$, and so on...? – mika Oct 25 '15 at 23:57
  • @Did Since divisibility by 7 is the main issue here, I'll mention my favourite such test. Clip off the units digit of the n-digit number, double it and subtract it away from the new (n-1)-digit number remaining. Keep going either until you recognise either a multiple of seven (test passed) or a non-multiple of seven (test failed). E.g. 973 becomes 97 minus 32 = 91 (and here I stopped but you can keep going) which becomes 9 minus 12 = 7 (test passed). I like this method because it's easy to remember and execute and it reduces the number by an order of magnitude at each step. – Deepak Aug 24 '18 at 09:16
  • @mika: pure Erathostene by hand is not to be recommended. You'd have to start by writing $973$ numbers then strike out $486+ 324+194+139$ of them before you find the divisor $7$. –  Aug 24 '18 at 09:16
  • @Deepak: ordinary division by $7$ is not much different. $973\to273\to63$. –  Aug 24 '18 at 09:41
  • @Yves The algorithm seems easier when working without pen and paper. It may be a subjective preference. – Deepak Aug 24 '18 at 13:15

6 Answers6

4

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$

Oscar Lanzi
  • 39,403
  • 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. –  Aug 24 '18 at 10:01
0

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.

0

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$).

0

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

0

Another way, $973 = 910+63$

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

-1

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.

YoTengoUnLCD
  • 13,384
  • 2
    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. – Cataline Oct 25 '15 at 21:21