How do people come up with divisibility tests? For example, the test for divisibility by $2$ is quite obvious. But I am quite intrigued by the others, particularly $3$, $7$ and $11$. Also I have come across tests for numbers as far as $50$. How do people even think of these? And consequently, how do they prove it?
 A: There are various methods for developing divisibility criteria. Here is a fairly general one:
Let's develop a divisibility criterion for example with $13$. Take any integer $n$ with digits $a_k,a_{k-1},...,a_2,a_1,a_0$ and write its decimal expansion:
$$n = (a_k \times 10^k) + (a_{k-1} \times 10^{k-1}) + .... + (a_2 \times 10^2) + (a_1 \times 10^1) + a_0$$ 
Notice the following congruences:
$$10^0 \equiv 1 \ \ mod 13 \\
10^1 \equiv 10 \ \ mod 13 \equiv (-3) \ \ mod 13 \\
10^2 \equiv 9 \ \ mod 13 \equiv (-4) \ \ mod 13  \\
10^3 \equiv 12 \ mod 13 \equiv (-1) \ \ mod 13  \\
10^4 \equiv 3 \ \ mod 13   \\
10^5 \equiv 4 \ \ mod 13  \\
10^6 \equiv 1 \ \ mod 13   \\
\vdots
$$
this means we get the $6$-step cycle: 
$$1,-3,-4,-1,\ 3,\ 4,\ 1,-3,...$$
thus:
$${\small
n\equiv\big(a_0+a_1\times(-3)+a_2\times (-4)+a_3\times(-1)+a_4\times 3+a_5 \times 4+a_6\times 1+a_7\times(-3)+...\big)\ \ mod 13}$$
Setting 
$${\small
m = a_0 + a_1 \times (-3) + a_2 \times (-4) + a_3 \times (-1) + a_4 \times 3 + a_5 \times 4 + a_6 \times 1 + a_7 \times (-3) + ...}$$
it is clear that:
$$n\equiv m \ \ mod 13$$
and that:
$$m<n$$ 
and thus it is easier to check if $m$ is divisible by $13$. 
Notice that 
$$m\mid 13 \Leftrightarrow n\mid 13$$
Repeat as many times as necessary.
The above method works for any integer, however it is not the only applicable method. There other criteria as well (for any integer) that can be developed either through systematic or heuristic methods. 
