This should be taught after students are comfortable substituting expressions for numbers. For example, students should know they can represent an odd number \(n\) as \(2k + 1,\) where k is some integer.
The divisibility test for \(7\) is to double the last digit, then subtract the result from the number formed by the other digits. If it's difficult to tell whether the difference is divisible by \(7,\) we can repeat the procedure as long as we desire. Why does this rule work? Any number can be written as \(10a + b,\) where \(a\) is consists of all digits but the rightmost digit, and \(b\) is the rightmost digit alone. If \(7\) divides \(10a + b,\) then \(7\) must also divide \(10a + b - 21b.\) Simplifying a bit gives us$$10a + b - 21b = 10a - 20b = 10(a - 2b)$$
We know \(7\) must divide at least one factor. Since \(7\) does not divide \(10,\) it must divide \(a - 2b.\) This is precisely our divisibility rule for \(7.\) We know we can whittle down the number repeatedly, because \(a - 2b\) is some integer. Thus we could write \(a - 2b\) as \(10c + d\) and repeat as long as we desire.
Similar reasoning can be used for 13. If \(13\) divides \(10a + b,\) then \(13\) must also divide \(10a + b + 39b.\) Simplifying gives us$$10a + b + 39b = 10a + 40b = 10(a + 4b)$$
From this we know the rule for \(13\) is quadruple the last digit, then add the result to the number formed by the other digits. We can repeat as long as necessary, following the argument previously stated.
Further, this reasoning applies for any prime. Have students try finding the divisibility rules for 31 and 19.
TODO: What other prime divisibility rules should students find?
Note: The idea for how to teach these rules came from here, though I don't recommend watching that video, as the audio quality is extremely low.