Thread: Tricky induction proof

I just can't see to figure this out.

Consider function as follows:




Prove by induction that for all that and are relatively prime.

Originally Posted by VENI

I just can't see to figure this out.

Consider function as follows:




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.