4
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ 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 ... $\endgroup$ – Hagen von Eitzen Oct 25 '15 at 21:06
  • $\begingroup$ Do you know the Erathostene's sieve? $\endgroup$ – Emilio Novati Oct 25 '15 at 21:10
  • 1
    $\begingroup$ 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). $\endgroup$ – Did Oct 25 '15 at 21:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Travis Oct 25 '15 at 21:38
  • $\begingroup$ @EmilioNovati, if i had to guess Erathostene's sieve would go hand in hand with hagenvoneitzen point $\endgroup$ – mika Oct 25 '15 at 23:54
4
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yves Daoust Aug 24 '18 at 10:01
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

Another way, $973 = 910+63$

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

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Cataline Oct 25 '15 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.