Show that any positive integer is in the form of ,, for some integer
Euclid's division lemma:
Let us consider a positive integer . We apply here Euclid's division algorithm (where is dividend is divisor , is the quotient and is remainder). We have and .
Since (because remainder cannot be greater than the divisor). Possible remainders in this case are , and .
So, three cases arises according to Eucild's division Lemma
First case: When ,
⇒
Second case:When ,
Third case:When ,
Thus,any positive integer is in the form of ,, for some integer.