By &quot;doesn&#x27;t use divisibility&quot; I assume the author means that the point of contradiction doesn&#x27;t rest on the &quot;divisibility properties&quot; of the integer, not that division is never used.  In particular, this proof doesn&#x27;t rely on the fundamental theorem of arithmetic.