[NumTh Expository] “Co-prime” as more basic than “Prime”

Introduction

     While mucking around with another problem, I used the above to argue and solve it.  If  a  is a factor (divisor) of  bk,  and  a  and  b  are co-prime (they do not have any common factor), then “obviously”  a  must divide  k.  I wanted to prove this by just using this definition of  a  and  b  being co-prime

          d | a  and  d | b   Þ   d | 1   Þ   d = 1  (since 1 | d  also)

The concept of being co-prime (or relatively prime) is more basic than the concept of prime numbers.  The prime number property

          p | ab  Þ   p | a  or  p | b

should be built on top of this common sense observation, instead of the other way round.  In advanced modern mathematics, the above prime number property is the definition of prime numbers.   By the way,  hcf  stands for highest common factor, which Americans call “greatest common divisor” or gcd.

     It turns out that “common sense” facts are harder to prove.  Furthermore, I wanted to tie one hand behind my back and still see if I could still do it.  I came up with three proofs.  In what follows, the notation  A | B | C  means  A | B  and  B | C  and by transitivity  A | C  and can be read as  “A  divides  B,  which divides  C”.

One more try ...

     I think the above proofs are correct as they stand, but I still have not achieved my objective of using just the concept of divisibility.  Proof #3 is short and sweet, but this borrows from the theory of Linear Diophantine Equations.  Looking back at proof  2a,  I decided to replace “prime number” with “smallest non-trivial divisor” and had a go at it again.  The observant reader will realise that the smallest non-trivial divisor is a prime number in disguise but “Shhhhhhh!  Don’t tell other people, OK?” 

Final Remark

     The key idea that makes this proof work is that the hcf is guaranteed to exist, and  hcf(A, B) always divides  AB  since it divides both  A  and  B.  Finally, I got the proof with the flavour that I wanted.  So how does the prime number property   p | ab  Þ   p | a  or  p | b    follow from the above theorem?  Easy: If  p  is a prime that does not divide  a,  then  hcf(p, a) = 1  i.e.  p  and  a  are coprime.  Then  p | b.  ©