As a precursor to lessons on prime decomposition and reducing fractions, rules are generally presented for divisibility by 2, 3, 5, 9, and 10 and sometimes for those popular composites such as 4 and 25. In our experience students often ask: "What about the one for 7?" and we are loathe to simply state that there isn't one. We have yet to see a rule for divisibility by primes 7 or greater in any "standard" textbook. Maybe these are slightly more involved than the other divisibility rules, yet we find that they should be included, or at least mentioned, so as not to suggest to the student that such algorithms are only possible for a few special integers. "Divisibility criteria" are arithmetic methods that determine whether or not one integer divides another without having to actually carry out the division. These methods in question offer a simpler course than by performing the division itself to resolve the question of divisibility. We suggest that introducing some of these techniques into the algebra/precalculus curriculum might generate some interest in the "higher arithmetic."