It was quite a while since I took logic, but shouldn't this work?
1 (1) ~(P & Q) Premise
(2) P v ~P LEM
3 (3) P Assumption
4 (4) Q Assumption
3,4 (5) P & Q 3,4 &I
1,3,4 (6) absurd 1,5 ~E
1,3 (7) ~Q...
p_1, \ldots, p_n are all the prime factors from both a and b. Note that if p_k is a prime factor in a but not in b, then f_k will be 0.
As for a link, I guess you could look at MathWorld, though I'm not sure it includes the details you seek. But I would encourage you to think about what hcf...
If
a = p_1^{e_1} \cdot p_2^{e_2} \cdots p_n^{e_n},
b = p_1^{f_1} \cdot p_2^{f_2} \cdots p_n^{f_n},
where p_i are unique prime numbers and e_i \ge 0, f_i \ge 0, then
\text{hcf}(a,b) = p_1^{\min(e_1,f_1)} \cdots p_n^{\min(e_n, f_n)},
\text{lcm}(a,b) = p_1^{\max(e_1,f_1)} \cdots...