If I don't have a computer at hand (or an app), how can I know that $1637$ is prime?
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?
Solution 1:
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$.
Solution 2:
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!)
Solution 3:
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.