27
$\begingroup$

So with $1037 = 17 \cdot 61$, is there a fast method to deduce that it's not a prime number?

Say $1037 = 10^3+6^2+1$. Does $a^3 + b^2 + 1$ factorize in some way?

As part of their interviews, a company is asking whether a number is prime. I have never studied number theory, and I am not aware of a strategy for this apart from polynomial factorization.

I am guessing that for a number they give you, it would have to not be prime, as the only way to see that a number is a prime by hand is to test all primes below $\sqrt{N}$.

$\endgroup$
11
  • 5
    $\begingroup$ Considering all the numbers below $\sqrt{1037}\approx 32$, you can also exclude the even numbers, and exclude multiples of already checked numbers. So there is no need to check whether 9 divides 1037 if 3 is already checked. Removing these cases leaves about 10 numbers to check...which is still not good enough to work out in a minute, but better nonetheless. Not sure if there is a more clever way to do so $\endgroup$
    – Dylan Zammit
    May 21, 2018 at 9:11
  • 3
    $\begingroup$ $2^3+2^2+1=13$ which is prime. Similarly $2^3+8^2+1 = 73$ and $6^3+4^2+1 =233$ and others, so there is unlikely to be a general factorization of $a^3+b^2+1$ $\endgroup$
    – Henry
    May 21, 2018 at 12:49
  • 5
    $\begingroup$ @DylanZammit That's what OP said: '...to test all primes below root of N'. $\endgroup$
    – CiaPan
    May 21, 2018 at 13:17
  • 3
    $\begingroup$ Out of curiosity, interviews for what sort of position? $\endgroup$
    – Peter Phipps
    May 21, 2018 at 14:13
  • 4
    $\begingroup$ "Quick" can depend on one's mental arithmetic speed. But I rather doubt that's what an interviewer was interested in. $\endgroup$
    – Carl Witthoft
    May 21, 2018 at 15:40

11 Answers 11

Reset to default
21
$\begingroup$

$u\mid v$ is read as "$u$ divides $v$" and $u\nmid v$ is read as "$u$ does not divide $v$."

Obviously $2\nmid 1037$ since it has an odd last digit.

By the "Divisibility by $3$ Rule," it follows that $3\nmid 1037$ since $3\nmid 1+0+3+7=11$.

Obviously $5\nmid 1037$ since the last digit is not $0$ nor $5$.

If $7\mid 1037$ then $7\mid 1037-7=1030$ but $1030=103\times 10$, and $103$ is prime and $7\nmid 10$.

If $11\mid 1037$ then $11\mid 1037-77=960$ but $960=96\times 10$ and $11\mid 99$ so $11\nmid 96$ since it is off by a remainder of $3$ (and obviously $11\nmid 10$).

Try for $13$ this time, and then for $17$. You will see that it works for $17$, which indicates that $17\mid 1037$ and $1037$ is not prime.

You can try this method for all numbers, and you only need to try the first prime numbers less than the square root of the number you are testing with; for example, say you don't know if $61$ is a prime number. Then, apply this method.

Now, $64=8^2$ so $\sqrt{61}$ is pretty close to $8$. And since $7^2=49<61$, then all you need to do is see if $2,3,5$ or $7$ divide $61$. If they don't, then $61$ is prime (which it is).

This method does not have an official name, so it might as well be called a "trial divisibility check" by primes. Thanks to users that commented below who corrected me as I thought this method was the following.

A well known method is the "Sieve of Eratosthenes."

Tip:

A good number of primes to remember off the top of your head is all of the primes up to $127$. This has helped me, and $127$ is a pretty special number. There are many good properties about $127$; for example, $127$ is a Mersenne prime (a prime of the form $2^p-1$ for prime $p$), and it is the $31$st prime number, $31$ also being a Mersenne prime.

If you want to remember more prime numbers after $127$, you can. (I did all the way up to $383$, so it is possible.)

Apologies if this answer is primarily opinion-based.

$\endgroup$
18
  • 17
    $\begingroup$ The rule for $7$ is to subtract twice the last digit from the rest. So $103 - 2*7 = 89$ and $8 - 2 * 9 = -10$. $-10$ is not divisible by $7$. Contrast with the results on 1036 (7) and 1043 (-7). The test for 11 was already given. Separately, this is not the Sieve of Eratosthenes but trial division by primes. In a sieve, you produce all the primes up to a number. $\endgroup$
    – Brythan
    May 21, 2018 at 14:54
  • 5
    $\begingroup$ What Brythan said above. Please correct your answer, this has nothing to do with the sieve of Eratoshenes. It's a good method though, I often practice it while driving, factoring random 4-digit numbers from car plates. $\endgroup$
    – ypercubeᵀᴹ
    May 21, 2018 at 18:37
  • 3
    $\begingroup$ @Brythan actually not really trial division (as you don't necessarily get the quotient), just "trial divisibility check" by primes. (I'm doing it quite similar sometimes when trying to sleep.) $\endgroup$
    – Paŭlo Ebermann
    May 21, 2018 at 19:54
  • $\begingroup$ @Brythan ok, thank you very much. $\endgroup$
    – Mr Pie
    May 21, 2018 at 23:24
  • $\begingroup$ @ypercubeᵀᴹ thank you very much as well :) $\endgroup$
    – Mr Pie
    May 21, 2018 at 23:25
20
$\begingroup$

There are various methods for deciding primality, some probabilistic (the result is not sure but the more you run the algorithm the more securely you know the answer) and there are deterministic methods (they decide for sure). Altough all of these working efficiently on numbers that are way greater than $1037$.

With numbers of this size checking all numbers seems to be the most efficient way. There of course are some special cases but if you get a number of this size you should go about checking if it is even (easy), divisible by $3$ (the digitsum is divisible by $3$) by $5$ (ends with $0$ or $5$) and so on. If you have a calculator at hand it wouldn't take longer than a minute since $\sqrt{1037}\approx 32$ so you only have to check primes up to $31$.

They surely do not mean tests like these but I would like to add some links for the sake of completeness

Probablilistic test is the so called Miller-Rabin test.

And for deterministic Pollards $p-1$ and Lenstras elliptic curve factorisation is a fast and efficient one.

Even difference of squares can work fine:

$N$ is to be factored, find a $b^2$ such that $N+b^2$ is a square, say $a^2$ and then

$$ N+b^2=a^2 $$ so $$ N=a^2-b^2=(a-b)(a+b) $$

$\endgroup$
5
  • 1
    $\begingroup$ Cool, that is awesome, I guess you are right with only primes up to 31 to try, that is what they would expect, and see how quickly you can divide, in your head. $\endgroup$
    – JimSi
    May 21, 2018 at 9:39
  • 3
    $\begingroup$ And the primes less than $31$ are easy to find; the $6n\pm 1$ rule works really well that early in the number line. $\endgroup$
    – hmakholm left over Monica
    May 21, 2018 at 13:47
  • $\begingroup$ From powershell command line 3,5,7,11,13,17,19,23,29,31|?{!(1037%$_)} will print 17, which would mean that 17 is a divider for 1037 Even googling Is 1037 prime will give you the answer in under a minute, if you are allowed to use it of course. $\endgroup$
    – Andrew Savinykh
    May 22, 2018 at 4:47
  • 3
    $\begingroup$ Since someone mentioned command-line, I want to add that if you are using any *nix OS, running factor 1037 gives you 1037: 17 61. $\endgroup$
    – Alex Vong
    May 22, 2018 at 5:00
  • $\begingroup$ It is almost zero work to test for divisibility by 2,3,5,7, and 11. (from Savinykh's list above). Also, see that 1037 is to close to 1024 for 31 to be a divisor. That leaves 13, 17, 19, 23, and 29 to be tested. You can do it on a calculator. For this kind of work, see the book "Dead Reckoning". Every page you read will increase your personal computing power. To test for divisibility by 7: add double the first two digits to the last two. You have preserved the remainder under division by 7 because 100 = 2 (mod 7). $\endgroup$
    – richard1941
    May 23, 2018 at 1:58
12
$\begingroup$

I suspect the interviewer is more interested in your approach to answering the question than in the speed of your mental arithmetic. As a practical approach, I would rule out 2,3 and 5 as factors immediately and then use the calculator on my phone to check divisibility by other small primes. For 1037 you only need to check primes up to 31. But the most impotant thing is to talk through what you are doing and why you are doing it.

$\endgroup$
1
  • 2
    $\begingroup$ It is this way with all other questions, from Fermat equation to fast powers of 10-digit numbers. Have my upvote. $\endgroup$
    – Oleg Lobachev
    May 21, 2018 at 21:27
9
$\begingroup$

As others have noted, you only need to check primes up to 31. Of course that'll take a while if you have to do it by long division - here's a few shortcuts.

2: The last digit isn't even, so obviously 1037 isn't divisible by 2.

3: The sum of the digits is 11, which isn't divisible by 3, so 1037 isn't divisible by 3.

5: The last digit isn't 5 or 0, so 1037 isn't divisible by 5.

7: If 1037 were divisible by 7, so would 1030. If 1030 were divisible by 7, 103 would be too. If 103 were divisible by 7, so would 110, which is $2 \cdot 5 \cdot 11$ and is therefore not divisible by 7. So 1037 isn't divisible by 7.

11: $1 - 0 + 3 - 7 = -3$, which is not divisible by 11, so 1037 isn't divisible by 11.

13: If 1037 were divisible by 13, then $1050 = 1037 + 13$ would also be. If $1050$ were divisible by 13, $105$ would be too. But $105 = 3 \cdot 5 \cdot 7$, so it isn't divisible by 13, so neither is 1037.

17: 1037 is divisible by 17 only if $1037 - 17 = 1020$ is. 1020 is divisible by 17 only if $102$ is. $102 = 2 \cdot 51 = 2 \cdot 3 \cdot 17$, so it is divisible by 17, so 1037 is divisible by 17, so 1037 isn't prime.

Note: These approaches don't do a good job of factoring - it's a bit tricky to unwind that last argument to figure out what $1037/17$ is. But if the question is just "is it prime", this should work fine.

$\endgroup$
1
  • 4
    $\begingroup$ What a cool trick, adding multiples of a possible factor to reach a multiple of 10. $\endgroup$
    – arp
    May 21, 2018 at 23:15
7
$\begingroup$

You're not likely to get even a moderately large random number to factor. In addition to the tests in the other answers, it might help (and it's cool to know) the test for $11$ - calculate the alternating sum of the digits and look for $0$.

At the next level, the fact that $1001 = 7 \times 11 \times 13$ means you can test for divisibility for all of those by calculating the alternating sum of three digit blocks, then just testing the three digit result.

Finally, $91$ is the only number less than $100$ that "looks like a prime" but isn't. That's because the evens, multiples of $3$ and $5$, $77$ and $49$ are clearly composite. The others are the numbers that look like primes.

$\endgroup$
3
  • 8
    $\begingroup$ Legend has it that $57$ "looks like a prime" to at least some rather smart people ... $\endgroup$
    – hmakholm left over Monica
    May 21, 2018 at 13:40
  • 1
    $\begingroup$ But $5+7=12=3\times 4$ so $3\mid 57$ and my guess is, $57=3\times 19$. Actually, my guess is right because $57+3=60$ which is obviously $20\times 3$... but hahaha I used to think $91$ was a prime number all the time... $\endgroup$
    – Mr Pie
    May 21, 2018 at 23:27
  • $\begingroup$ @HenningMakholm or, if you know your powers very well, you would know that $3^5=243$ and also $243+57=300$ :) $\endgroup$
    – Mr Pie
    May 22, 2018 at 11:05
4
$\begingroup$

If you are confident with powers of 2, note that:

$$1037=2^{10}+13=2^{10}+2^4-3$$

If we are to have an expansion of the form $(a+b)(c+d)$, we can be sure that a 1 and 3 are involved, with one of them negative, that $2^4$ is involved and by extension $2^6$ to multiply together to make $2^{10}$.

The trick is to notice that:

$$ 2^6 = 2^22^4=4\cdot2^4 $$

and so

$$ 2^6-3\cdot2^4=2^4 $$

From which we can deduce that:

$$ 1037 = (2^6-3)(2^4+1) = 61\cdot17 $$

This can be extended into the general relation:

$$ 2^a + 2^b -3 = (2^{a-b}-3)(2^b+1) $$

when $a-2b=2$

$\endgroup$
3
$\begingroup$

Without using rarely taught divisibility tricks...

"If it were divisible by $2$ or $5$ we would see that immediately and it isn't. Dividing by $3$: leaves $13$, leaves $17$, which is not divisible by $3$. Dividing by $7$: leaves $3$, leaves $-2$, leaves $13$, which is not divisible by $7$. Dividing by $11$: Well, $99$ leaves $4$, $47$ is not divisible by $11$. Dividing by $13$: Hmm... $8$ times $13$ is $80+24 = 104$ and $-10+7 = -3$ is not divisible by $13$. Dividing by $17$: Try $6$: $17 \cdot 6 = 60+42 = 102$, leaving $17$, which is divisible by $17$, so $1037$ is not prime. Also, $17$'s cofactor is $61$."

Explanation:

"Dividing by $3$: leaves $13$, leaves $17$, which is not divisible by $3$." $10/3$ has remainder $1$, now append the next digit, $13$. $13/3$ leaves remainder $1$, now append the next digit, $17$, not a multiple of $3$.

"Dividing by $7$: leaves $3$, leaves $-2$, leaves $13$, which is not divisible by $7$." $10/7$ leaves remainder $3$, appending gives $33$ which is $2$ less that $35$, a multiple of $7$, then $-20+7 = 13$, not divisible by $7$.

"Dividing by $11$: Well, $99$ leaves $4$, $47$ is not divisible by $11$." Rather than go at the first two digits, go at the first three. $103$ is barely larger than $11 \cdot 9$, leaving remainder $4$. Appending the next digit, we have $47$, which is not divisible by $11$.

"Dividing by $13$: Hmm... $8$ times $13$ is $80+24 104$ and $-10+7 = -3$ is not divisible by $13$." Again go after the first three digits. Since one-eighth is between $0.12$ and $0.13$, $13\cdot 8 = 80 + 24 = 104$ should be a little over $100$. We overshoot by $1$, meaning $1040$ is divisible by $13$. Then the gap between $1040$ and $1037$, $-3$ is not divisible by $11$.

An entirely different way to go on $13$: A deck of cards is $52$ cards in $4$ suits of $13$ cards, so $52$ is a multiple of $13$ and $5$ nearly evenly divides $103$, $20$ times ($100/5 = 20$, which is usually a well-known currency fact). Then $52 \cdot 20$ = $1040$ ("${}\cdot 20$" means double, then append a zero), which is $3$ too large, but $-3$ is not divisible by $13$.

"Dividing by $17$: Try $6$: $17 \cdot 6 = 60+42 = 102$, leaving $17$, which is divisible by $17$, so $1037$ is not prime. Also, $17$'s cofactor is $61$." It helps to know $1/6 = 0.16666\dots$, so $6\cdot 16$ and $6 \cdot 17$ are around $100$. Then $17 \cdot 6 = 60 = 42 = 102$. From the first three digits, $103 - 102 = 1$, append the last digit, and see $17$, which is definitely divisible by $17$.

One thing that happened a couple of times and that is useful to know. You can be a little sloppy in your divisions. You don't have to get each of them exactly right, you just need to leave a remainder small enough to work with.

For instance, suppose for divisibility by $17$ we tried $7$ first. $17 \cdot 7 = 70 + 49 = 119$, overshooting by $16$. Either we notice that $16 $ is large enough that starting with $6$ would leave the smallest remainder, or we stick with it. We have $-16$ and the next digit is $7$, so we want to know if $-160+7 = -153$ is divisible by $17$. Adding $170$, which is close to the right magnitude and will make things small and positive, we get $17$, and are done again.

$\endgroup$
2
$\begingroup$

Yes, as suggested we could check the primes up to $\sqrt{n}$. The rest is just luck. For example, the primes up to $\sqrt{1037}\approx 32.2$ are: $$3,5,7,11,13,17,19,23,29,31.$$ Note that the factor $17$ is almost equidistant from the two ends, though checking from the left is indeed easier and faster.

Now consider $1081=23\cdot 47$. The primes up to $\sqrt{1081}\approx 32.9$ are the same: $$3,5,7,11,13,17,19,23,29,31.$$ This time it is easier and faster to start checking from the right.

Question: Is $2021$ prime? Hint: Try right hand approach.

$\endgroup$
2
  • 3
    $\begingroup$ $2021+2^2=45^2$. $\endgroup$
    – Michael Hoppe
    May 22, 2018 at 21:06
  • 2
    $\begingroup$ or $40^2+40\cdot (3+7)+3\cdot 7$. $\endgroup$
    – farruhota
    May 23, 2018 at 4:36
1
$\begingroup$

As others pointed out, you really have to check divisibility by primes between 7 and 31. These are 7, 11, 13, 17, 19, 23, 29, 31. If I were to check divisibility of a number around 1000 by these primes by hand as fast as possible, I would try that directly for the lower ones:

7*150 = 1050, 1050 - 1037 = 13, 13 mod 7 != 0

11*100 = 1100, 1100 - 1037 = 63, 63 mod 11 != 0

13*100 = 1300, 1300 - 1037 = 263, 263 mod 13 != 0 (260 mod 13 = 0)

And then look for a suitable candidates for the larger ones. Suitable candidate must be a prime or a product of primes larger than 5:

17*y = 1037 => last digit of y must be 1 => candicates are: 61,71 -> bingo

(the following is not necessary for 1037, but has to be done for a similar number like 1087)

19*y = 1037 => last digit of y must be 3 => candicates are: 53 -> (53*20 - 53 = 1007) too small

23*y = 1037 => last digit of y must be 9 => candicates are: 49(7x7) -> (23*50 - 23) too large

29*y = 1037 => last digit of y must be 3 => candicates are: 43 -> (43*29 > 40*30 = 1200) too large

31*y = 1037 => last digit of y must be 7 => candicates are: 37 -> (31*37 > 30*38 = 1140) too large

$\endgroup$
1
$\begingroup$

It's not divisible by $2$ (last digit), $3$ (digit sum) or $5$ (last digit).

It's divisible by $7$ iff $(1037-7)/10=103$ is, so iff $(103+7)/10=11$ is, so it's not divisible by $7$.

It's not divisible by $11$ (sum of even digits $\neq$ sum of odd digits).

It's divisible by $13$ iff $(1037+13)/50=21$ is, i.e. it isn't.

It's divisible by $17$ iff $(1037-17)/20=51$ is. $51=3\times 17$, so we have a winner.

$\endgroup$
1
$\begingroup$

Clearly 2 and 5 do not divide 1037. To check non divisibility by 7, 11 and 13 note 037 -1 = 36 is not divisible by any of thesee. The smallest number to check by long division is 17 It works

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .