Prove by induction that for all that and are relatively prime.
If give you a hint to get you started. Say that and where not relatively prime then there is a prime so that divides . However, and so would divide . Which means that a common factor for . Thus, we have shown is that if are relatively prime then must be relatively prime.