How can I use NAND gates to divide (5bit) binary inputs by an integer (say 5)?
Since you are dividing by a constant this is a trivial 5-bit -> 4-bit (actually 5-bit -> 3-bit as @OlinLathrop points out) combinational circuit.

If you are feeling too lazy to work the 5-variable Karnaugh maps by hand then get yourself a copy of the Espresso heuristic logic minimizer.  (If you google "espresso logic minimizer" you may be able to find a precompiled binary (prefer the ones from .edu sites.)

Type in the truth table and run it through the tool.  It will probably give you the results in sum of products form.  The conversion to nand gates with 4 or fewer inputs is a trivial exercise.