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? 
 A: 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!)
A: 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
A: 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$.
A: 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.
A: 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$.
