18
$\begingroup$

Which of the following is not a prime number ?

$a.)\ 911 \ \ \ \ \ \ \ \ \ \ b.)\ 919 \\ \color{green}{c.)\ 943} \ \ \ \ \ \ \ \ \ \ d.)\ 947$

This was asked in my exam and the time given per question was $1-3\ \text{ min}$

If the time was $10\ \text{min}$ for this question I would have solved this comfortably but since the time was less i couldn't solve it with dividing every option with shorter primes .

I look for a simple and short way.

I have studied maths up to $12$th grade.

$\endgroup$
13
  • 6
    $\begingroup$ $23\cdot 41$ RIP $\endgroup$ – GPhys Jan 20 '16 at 6:24
  • 1
    $\begingroup$ No calculator I assume? $\endgroup$ – Matt Samuel Jan 20 '16 at 6:26
  • $\begingroup$ but 23 comes after $2,3,5,7,11,13,17,19$ dividing this by every options consumes time $\endgroup$ – R K Jan 20 '16 at 6:26
  • $\begingroup$ @MattSamuel: there is no calculator allowed. $\endgroup$ – R K Jan 20 '16 at 6:26
  • 6
    $\begingroup$ You can cut your time by a factor of $4$ if you only divide one (say option a) by primes in question and then note the differences between options. Using this and no other clever idea, it takes me approximately 2 minutes. For instance, as $13 * 7 = 91$, we know option a has remainder $1$ when divided by both $13$ and $7$. As $919$ is $8$ more, it has remainder $9$ when divided by $7$ and $13$ (or rather, it has remainder $2$ with $7$, but that's not important). And similarly for the others, without doing additional divisions. $\endgroup$ – davidlowryduda♦ Jan 20 '16 at 6:38
9
$\begingroup$

the smaller prime factor has to be less that $\sqrt{961} = 31$

Don't start at $2$ and work your way up. Start at $29$ and work your way down.

Four fails at $29$. In all four cases, the first digit of the quotient was $3$.

Two fails at $23$.

Then $943 = 23 \times 41$.

or

If they taught you the difference of two squares method...

\begin{array}{|c|rrrr|} \hline 31^2 & 961 & 961 & 961 & 961\\ n & 911 & 919 & 943 & 947\\ \hline 31^2 - n & 50 & 42 & 18 & 14\\ +(2\cdot 31 + 1) & +63 & +63 & +63 & +63\\ \hline 32^2 - n & 113 & 105 & \color{red}{81} \\ \hline \end{array}

So \begin{align} 32^2 - 943 &= 9^2\\ 32^2 - 9^2 &= 943\\ (32-9)(32+9) &= 943\\ 23 \times 41 &= 943 \end{align}

$\endgroup$
4
  • 9
    $\begingroup$ In hindsight it is clear that OP should have "worked your way down," but does that make sense as a general strategy? $\endgroup$ – Ryan Jan 24 '16 at 3:03
  • $\begingroup$ @ryan The first thing I did was check for $2, 3,5,7,11$, and $13$. Then I decided to try it from the other direction. In part because the numbers were so close together that I figured it would facilitate division by a two-digit number. I can't really justify this as I have no idea what the OP has been taught or is expected to know. I added the second solution only because I think it is interesting. I have no real notion that he was taught this method. $\endgroup$ – steven gregory Jan 24 '16 at 3:45
  • $\begingroup$ @StevenGregory what if number was $901$ instead of $943$? Fermat's method would take $4$ iterations, in comparison with $4$ calculations using trial division from $7$, and given there is a quick and dirty way to check if divisible by $7$, in this case, trial division would be faster. It is not clear this method is better in general. $\endgroup$ – martin Jan 29 '16 at 13:49
  • $\begingroup$ @martin 9 -Again, I tried 3,5,7,11, and 13 first. But it wasn't 901. Most test questions are trying to test something that the students learned. There is a reason why those particular four numbers were chosen. You have to figure out what that reason was. Not what methods works best in the "real" world $\endgroup$ – steven gregory Jan 29 '16 at 23:00
7
+50
$\begingroup$

Since you don't know what you're looking for, the most sensible strategy is to check the numbers to see if they're divisible by $2, 3, 5, 7, \dots, 29$ and stop when you find one that is. Obviously, this involves a lot of individual checks, so the problem is how to go fast. For $2, 3, 5, 11$ there are well-known criteria for divisibility, and you quickly determine that none of the four numbers are multiples of these.

Since the four numbers are all close together, it's easiest to simply list the multiples of $7, 13, 17, \dots$ that are close to the numbers.

The multiples of $7$ are: $910, 917, 924, 931, 938, 945, \dots$.

The multiples of $13$ are: $910, 923, 936, \dots$

The multiples of $17$ are: $901, 918, 935, \dots$

The multiples of $19$ are: $950, 931, 912, \dots$

The multiples of $23$ are: $920 - 23, 920, \mathbf{943}$.

$\endgroup$
8
  • $\begingroup$ Please note that this is precisely my answer. $\endgroup$ – zz20s Jan 24 '16 at 19:21
  • $\begingroup$ @zz20s Having now looked at your answer, which was written first, I agree that the ideas are similar. The differences are perhaps that I don't say $31$ needs to be tested, and that I don't suggest starting in the middle, but from whatever is convenient above or below the four numbers, especially a multiple of $10$ where possible. Also, I don't know what criterion for divisibility by $7$ is quick enough to be worth applying in the present circumstances. $\endgroup$ – David Jan 24 '16 at 20:52
  • $\begingroup$ I'm not saying to start in the middle, but you need to first find a way to generate multiples of $7$ around $900$, since I don't have my times tables memorized up until there :p $\endgroup$ – zz20s Jan 24 '16 at 21:04
  • $\begingroup$ @zz20s $130 \times 7 = 910$ is easy. A lot of people know $7 \times 13$. $\endgroup$ – David Jan 24 '16 at 21:11
  • $\begingroup$ I was just using 7 as an example. As the primes become larger, generating multiples around 900 becomes more difficult. Hence, doing a rough division of 930 by the possible factor is a good way to generate the multiples. $\endgroup$ – zz20s Jan 24 '16 at 21:20
3
$\begingroup$

First, note that you only need to test primes less than $31$, since $30^2=900$ and $31^2=961$, which is greater than any option. Thus, we only need to test $2,3,5,7,11,13,17,19,23,29$.

We can immediately eliminate $2,3,5,7,11$ from commonly known divisibility tests. I suggest memorizing the divisibility tests up to $15$ for competitions and tests.

Thus, we have it down to $13,17,19,23,29$.

Start by dividing $930$ by all these possible factors. This is because $930$ is about in the middle of the options. Then multiply all our possible factors by the whole number part of the quotient. Finally, start adding and subtracting the possible factors until you find an exact multiple. If you don't arrive at an exact multiple, move on to the next test number and repeat.

For example, $\frac{930}{13} \approx 71$ and $71 \cdot 13=923$.

The multiples of $13$ around $923$ are $910...923...936...949...$ Thus, no answer option has $13$ as a factor, and we can move on.

This method works very well for numbers $<1000$. It will take some practice and you must be able to do multiplication and division rather quickly. For larger numbers, this method becomes less effective in a short time span. I suggest practicing this method for quick tests of primes under $1000$ so that you become very quick and adept at it. It has worked for me in multiple competitions and tests.

$\endgroup$
2
$\begingroup$

As others have mentioned, you need to check divisibility only against prime numbers that are smaller than or equal to the square root of the dividend.

And since the square roots of all the dividends are smaller than $31$, you need to check divisibility of each dividend only by $2,3,5,7,11,13,17,19,23,29$.

Checking divisibility against $2,3,5$ is easy, so I'm not going to expand on it.

Checking divisibility against $7$ is easy in this case:

  • $911$ is not divisible by $7$ since $910$ is
  • $919$ is not divisible by $7$ since $910$ is
  • $943$ is not divisible by $7$ since $950$ would have to be
  • $947$ is not divisible by $7$ since $940$ would have to be

Checking divisibility against $11$ is easy in this case:

  • $911$ is not divisible by $11$ since $900$ would have to be
  • $919$ is not divisible by $11$ since $930$ would have to be
  • $943$ is not divisible by $11$ since $990-44=946$ is
  • $947$ is not divisible by $11$ since $990-44=946$ is

Checking divisibility against $13$ is easy in this case:

  • $911$ is not divisible by $13$ since $910$ is
  • $919$ is not divisible by $13$ since $910$ is
  • $943$ is not divisible by $13$ since $930$ would have to be
  • $947$ is not divisible by $13$ since $960$ would have to be

Checking divisibility against $17$ is partially easy in this case:

  • $911$ - $\color\red{\text{you'll have to do the math}}$
  • $919$ - $\color\red{\text{you'll have to do the math}}$
  • $943$ is not divisible by $17$ since $960$ would have to be
  • $947$ is not divisible by $17$ since $930$ would have to be

Checking divisibility against $19$ is easy in this case:

  • $911$ is not divisible by $19$ since $930$ would have to be
  • $919$ is not divisible by $19$ since $900$ would have to be
  • $943$ is not divisible by $19$ since $950$ is
  • $947$ is not divisible by $19$ since $950$ is

Checking divisibility against $23$ is easy in this case:

  • $911$ is not divisible by $23$ since $920$ is
  • $919$ is not divisible by $23$ since $920$ is
  • $943$ is divisible by $23$ since $920+23$ is
$\endgroup$
2
  • 2
    $\begingroup$ You can skip $11$ by using its divisibility criterion ($11\mid n$ if and only if $11$ divides the alternating sum of $n$'s digits.) $\endgroup$ – alex.jordan Jan 24 '16 at 9:27
  • $\begingroup$ @alex.jordan: Thanks. I initially thought about this, but it didn't quite work out for me with $979$, so I figured I was doing something wrong, and should refrain from using a method that I wasn't entirely sure about. Now I see that it DOES work with $979$ BTW!!! $\endgroup$ – barak manos Jan 24 '16 at 9:28
0
$\begingroup$

I might have think of it in this way: Let write the number in the form $$(20 + x) (40 + y)$$because all these numbers will be near that value. Write $911 , 919 , 943 , 947$ as $900 + 11$, etc.

Now, $$(20 + x)(40 + y) = 800 + 20 y + 40 x + xy$$ the $xy$ will be most likely the last number. Likely not necessarily trying and observing $xy = 3$ so $x = 3 ,y = 1$, just an guess $$800 + (20 \times 1) + (40 \times 3) + (3 \times 1) = 943$$ it can be a way of quick guessing and eleminating. The solution may seem long and complicated but is quite easy to guess that this way if you understand the concept behind this.

$\endgroup$
0

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