Hint to puzzle 83: Divisibility

For n > 1, consider p, the smallest prime factor of n.  Note that n and p − 1 are relatively prime, and hence there exist integers s and t such that ns + (p − 1)t = 1.  Use this equation to construct a reductio ad absurdum proof.