12
$\begingroup$

If I don't have a computer at hand (or an app), how can I know that $1637$ is a prime number?

I factored the number $99857$ as $1637\times 61$ and the computer told me that $1637$ is a prime. So would it be easy at all to know this without it?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ What do you want to know? How to factor 99857 or how to recognize that 1637 is prime? $\endgroup$ – zar Jun 6 '18 at 7:49
  • 5
    $\begingroup$ Check the divisors until the integer part of $\sqrt{1637}$. $\endgroup$ – Riccardo Ceccon Jun 6 '18 at 7:50
  • 6
    $\begingroup$ $40^2<1637<41^2$ so checking for prime factors less than $41$ will do it with mental arithmetic alone. You may be able to rule out some primes as factors with the aid of suitable quadratic residues. I didn't check whether that speeds up the process at in this case. If you use the same small primes many times, you may benefit from using this divisibility test. Modular arithmetic offers other ways easing the load. $\endgroup$ – Jyrki Lahtonen Jun 6 '18 at 7:51
  • 5
    $\begingroup$ If you want to prove "by hand" that $1637$ is prime, you just need to show it's not divisible by any primes $\le \sqrt{1637}$, i.e. $\le 40$. There are just $12$ of them. $\endgroup$ – Robert Israel Jun 6 '18 at 7:52
  • 2
    $\begingroup$ Related, possible duplicate: math.stackexchange.com/questions/1676996/… $\endgroup$ – Ethan Bolker Jun 6 '18 at 12:37
31
$\begingroup$

If it was not prime, it would have a prime factor smaller than or equal to its square root. Since$$40^2=1\,600<1\,637$$and$$41^2-40^2=(41-40)\times(41+40)=81,$$it is clear that $40<\sqrt{1\,637}<41$. So, all you have to do is to check whether $1\,637$ is a multiple of one of the twelve numbers $2,3,5,\ldots,37$.

Improve this answer
$\endgroup$
  • 2
    $\begingroup$ Which leads to the question; if I don't have a computer at hand, how can I know the primes up to 40? $\endgroup$ – JollyJoker Jun 6 '18 at 10:52
  • 12
    $\begingroup$ I don't know about you, but I knew all primes up to $40$ long before I started dealing with computers. $\endgroup$ – José Carlos Santos Jun 6 '18 at 10:58
  • 5
    $\begingroup$ Iif you want to know the primes from 2 to 40 you can use the sieve of Eratosthenes. en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes $\endgroup$ – Walter Mitty Jun 6 '18 at 11:04
  • 3
    $\begingroup$ @JoséCarlosSantos I suspect most people would have trouble listing the primes up to 40 if asked out of the blue, but few of those would be wondering if 1637 is prime, so... $\endgroup$ – JollyJoker Jun 6 '18 at 11:12
  • 2
    $\begingroup$ @JollyJoker If you simply know the 1-digit multiplication table (surely that is still taught in elementary school) then you implicitly know the primes which are less that 40 with no need to memorize any additional fact. If you don't recognize a number in that range as one of your known products -- it is prime. $\endgroup$ – John Coleman Jun 6 '18 at 12:45
7
$\begingroup$

For a given number $n$ and candidate divisor $d \in \mathbb{P}$, d | n (read "d divides n") iff d | (n + kd).

This trick can be used to speed up the mental calculations you are trying to do. For example, let $n = 1637$ and $d = 17$. The goal is to reduce the statement d | n into a more intuitively true or false statement.

If 17 | 1637, then 17 | (1637 +(-1)*17)
17 | 1620
17 | 162*10
17 | 162
17 | (162 + 17)
17 | 179
17 | (170 + 9)
17 | 9,

Which is false, so 17 does not divide 1637.

Rinse and repeat. (Fun!)

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ Or the other way around 17|1700 => 17|1700 - 17*4 => 17 | 1632 => 17 !| 1637 $\endgroup$ – Tibos Jun 6 '18 at 14:12
6
$\begingroup$

Full answer: this is quite tedious. Shows how useful calculators are!

As others have mentioned, $1637<41^2$ so just check whether it is divisible by $$2,3,5,7,11,13,17,19,23,29,31,37.$$ We can rule out

  • $2$ as $1637$ is odd

  • $3$ as the sum of the digits of $1637$ is $17$ which is not divisible by $3$

  • $5$ as $1637$ does not end in $0$ or $5$

  • $11$ as the alternating sum is $1-6+3-7=-9$ which is not divisible by $11$.

Time for congruences. By brute force,

  • $1637\equiv1400+210+28-1\equiv-1\pmod7$ so reject $7$.

  • $1637\equiv1300+260+78-1\equiv-1\pmod{13}$ so reject $13$.

  • $1637\equiv1700-68+5\equiv5\pmod{17}$ so reject $17$.

  • $1637\equiv1900-380+117\equiv117\equiv3\pmod{19}$ so reject $19$.

  • $1637\equiv1840-184-19\equiv-19\equiv4\pmod{23}$ so reject $23$.

  • $1637\equiv1740-174-71\equiv-71\equiv13\pmod{29}$ so reject $29$.

  • $1637\equiv1550+93-7\equiv-7\pmod{31}$ so reject $31$.

  • $1637\equiv1850-185-28\equiv-28\pmod{37}$ so reject $37$.

DONE!

The trick is to start with the number closest to $1637$ that is divisible by the prime you're working modulo.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ $7$ and $37$ can be ruled out quite easily by combining the following obvious rules: (1) Subtracting a multiple of $p$ doesn't change divisibility, (2) For $p\ne 2,5$, dividing by $10$ doesn't change divisibility. Combining both means that you can remove any multiple of $p$ from the end of the number. For $p=7$, we note that $1637$ ends in $7$, so we remove that, leaving $163$. But that ends in $63$, which again is a multiple of $7$, so remove that, too, leaving us with $1$, which obviously isn't a multiple of $7$. For $37$, it's even quicker: $1637$ ends in $37$, leaving $16$. $\endgroup$ – celtschk Jun 6 '18 at 17:58
  • 2
    $\begingroup$ You can get very creative with these an learn to do them in your head very quickly. $1637$ by $23$ (note that adding $3$ to $7$ gives me $10$ so $1637+23\to 1660\to 166$. ($\gcd(23,2)=1$ so we can divide by $2$ without a hitch. $166\to 83$. Subtract $23$. $83\to 60$ and divide by $10$ to get $6$ and well, that's that. $6$ is not divisible by $23$. So neither is $1637$. $\endgroup$ – fleablood Jun 6 '18 at 19:47
  • 1
    $\begingroup$ If you can compartmentalize in your head. For $13$, $1637 = 1600 + 37 = 2600 - 1000 + 39 -2\to -1002\to 1002\to 501 \to 501 + 39=540\to 54\to 27 \to 1.$ No good. $\endgroup$ – fleablood Jun 6 '18 at 19:57
  • $\begingroup$ Actually for $13$, it is useful to know the nice relation $7\cdot 11\cdot 13=1001$. This reduces $1637$ to $636$ in one step (indeed, you get an alternating sum in three-digit-blocks, the same way as you get in single digits for $11$). Once you have three digits $abc$, you just calculate $c-3b-4a$. For $636$, it's $6-3\cdot 3-4\cdot 6 = -27$, clearly not a multiple of $13$. Of course a sign change doesn't affect divisibility, so you might prefer $4a+3b-c$, which typically stays positive. $\endgroup$ – celtschk Jun 6 '18 at 20:24
4
$\begingroup$

If you have a number less than a million or so, the Miller-Rabin primality test will perfectly identify primality with $a=2$ or $a=3$. This is pretty easy to execute by hand. Edit: Just tried to actually execute this by hand, and calculating these large powers mod 409 is pretty laborious. I think this is still doable, not not as simple as I remember.

https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

Improve this answer
$\endgroup$
  • $\begingroup$ Yes, this works up to n=1,373,653. $\endgroup$ – Kelly Lowder Jun 6 '18 at 13:00
  • 5
    $\begingroup$ If it's so easy to do by hand, how about writing it into the post? :) $\endgroup$ – Asaf Karagila♦ Jun 6 '18 at 13:18
  • $\begingroup$ @AsafKaragila I can only justify spending so much time procrastinating marking these calculus papers... Maybe later. $\endgroup$ – Steven Gubkin Jun 6 '18 at 14:06
  • $\begingroup$ Well, that's depressing. $\endgroup$ – Asaf Karagila♦ Jun 6 '18 at 14:07
  • $\begingroup$ @AsafKaragila Got done with my grading and tried the algorithm. Harder than I remembered. Still possible by hand I think (I gave up part way through), but involves calculating some large powers of 2 mod 1637. Certainly more laborious in this case than just checking all the possible prime factors less than $sqrt(1637)$. $\endgroup$ – Steven Gubkin Jun 6 '18 at 15:50
3
$\begingroup$

If we can show that $1637$ has exactly one representation as a sum of two squares, then we know it's prime.

If there is a representation it must be of the form $1637=(2m-1)^2+(2n)^2$, which implies

$$m^2-m+n^2=409$$

Since $m^2-m=m(m-1)$ is even, we must have $n$ odd, in which case $8\mid(409-n^2)$, so that either $8\mid m$ or $8\mid m-1$, i.e., either $m=8h$ or $m=8h+1$ for some $h$. Writing $n=2k-1$, we find either $64h^2-8h+4k^2-4k+1=409$ or $64h^2+8h+4k^2-4k+1=409$, which reduces to

$$16h^2\pm2h+k^2-k=102$$

with $m=8h$ if the negative sign is used and $m=8h-1$ is the plus sign is used.

It's clear that $16h^2\pm2h+k^2-k\gt102$ if $h\ge3$, so we need only check the values $h=0$, $1$ and $2$.

For $h=0$, the equation $k(k-1)=102=53\cdot2$ has no solutions.

For $h=1$, the equations $k(k-1)=102-(16+2)=84=12\cdot7$ and $k(k-1)=102-(16-2)=88=11\cdot8$ have no solutions.

For $h=2$, the equation $k(k-1)=102-(64+4)=34=17\cdot2$ has no solutions, but the equation $k(k-1)=102-(64-4)=42=7\cdot6$ has a unique (positive) solution.

Unraveling this, we have $n=2k-1=13$ and $m=8h=16$, so that $(2m-1)^2+(2n)^2=31^2+26^2$ is the unique representation of $1637$ as the sum of two squares. Hence $1637$ is prime.

Improve this answer
$\endgroup$
3
$\begingroup$

It depends. Some numbers can be what you might consider very large and yet be easy to factor. Numbers like $8575000000000000000000000$. The main difficulty with that one would be to make sure you have correctly counted how many zeroes it has after "$8575$".

Of course either $8574999999999999999999999$ or $8575000000000000000000001$ would be a bit more difficult without the help of some kind of calculator.

Even though $99857$ is quite small, it's actually a little bit more difficult to factor by hand than the first number I mentioned. Obviously it's an odd number, so it's not divisible by $2$.

$9 + 9 + 8 + 5 + 7 = 38$ and $3 + 8 = 11$ and $1 + 1 = 2$, so it's not divisible by $3$ either. Its last digit is not $5$, so it's not divisible by $5$.

Remember that $\sqrt{10} \approx \pi$, which means $\sqrt{10^5}$ is about $314$, and consequently if $99857$ is composite, it's divisible by some prime less than $314$. I've only memorized the primes up to $199$, so this might present some difficulties for me.

At this point I would start to wonder if I really don't have some kind of calculator I can use. Let's say I stuck it out and discovered that $99857$ is divisible by $61$. Assuming I made no silly arithmetic mistakes, I would have $61 \times 1637 = 99857$.

Is it possible that $1637$ might not be prime? No, because if $1637$ is divisible by some prime from $2$ to $59$, I should have discovered it while trial dividing $99857$. The smallest possible prime factor of $1637$ at this point is $61$.

But since $60^2 = 3600$ and $61^2$ is obviously more than that, I now know that $1637$ is not divisible by any prime from $2$ to $61$ and therefore not divisible by any prime from $67$ to whatever is the largest prime less than $1637$.

Improve this answer
$\endgroup$
1
$\begingroup$

$1637$. Confession I find it hard.

But $1600=40^2 < 1637$ and $41^2 = 1600 + 80 + 1 > 1637$ so only need to check if it has prime factor $\le 40$.

The usual "doesn't end in an even number" "sum of digits isn't a multiple of 3" and "$1+3 \not \equiv 6+7 \mod 11$" show it is not divisible by $2$, $3$ or $11$.

Those are the only tricks I ever specifically memorized. Other wise I rely on "casting out".

To see if a number is divisible by $p$ add and subtract multiples of $p$ in your head. If you get a multiple of a number relatively primed to $p$ (usually a multiple of $10$) you can divide the result by that number. If you end up with anything but a multiple of $p$ then $p$ does not divide then number.

So, for example to see if $1637$ is divisible by $7$. I subtract $7$ and get $1630$. I divide by $10$ and get $163$. I subtract $9*7 = 63$ to get $100$. I divide by $10$ twice to get $1$. Had $1637$ ben divisible by $7$ all the numbers I would have gotten on the way would have been divisible by $7$ to and I wouldn't have gotten $1$. So $1637$ is not divisible by $7$.

(Down side: If I want to know $1637 \equiv x\mod 7$ this will not tell me anything.)

For $13$. $1637 = 1300 + 337$. $337 = 260 + 77$. ANd $7 = 7*11$ so it is not divisible by $13$.

For $17$. $1637 = 1620 + 17$. $162 = 81*2$. $81 -17=64$. $64 =2^6$ so no go.

For $19$. $1637 = 1618 + 19$. $1618 = 809*2$. $809 = 790 + 19$. $790 = 79*10$. $79-19 = 60 = 6*10$. $6$?. No go.

For $23$, $1637 = 2300 - 600 + 23 + 14$. $-600 + 690 + 14 = 104$. $4*23 = 100 -8$ so $104 = 4*23 + 8 + 4$. No go.

For $29$ $1637 = 1608 + 29$. Wait, let try something different. $1637 -3*29 = 1637 - 3*20 - 27 = 1610 - 60 = 155$. And $5*29 = 5*(30-1) = 145$. $155-145 = 10$ so no go.

$31$: $1637+ 93 = 1730$. $173 - 93 = 80$. No go.

$37$: $1637 = 1600 + 37$. and $16= 2^4$. No go.

It's not divisible by any prime less than $41$. It is less than $41^2$ so it is not divisible by any prime greater than $41$ (other than itself). SO it is prime.

Improve this answer
$\endgroup$
  • $\begingroup$ I think this raises the question of whether there are similar tricks to "is the sum of the numbers divisible by $3$?" but for the numbers $7,13,\ldots$. $\endgroup$ – Jam Jun 11 '18 at 14:37
  • 1
    $\begingroup$ Not really. 3 is a divisor of 10 - 1 and 11 is 10+1 so that's why tricks exist for 3,9 and 11. Whatever tricks one makes up for the others (and some complicated trick for 7 is fairly well known but I can never remember it) will not be as simple. "tossing out" always works (and the cost of losing modulo equivalence) and dividing multiplying by relative prime does too. $\endgroup$ – fleablood Jun 11 '18 at 15:07

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.