Question

Show that 5n+3 and 7n+4 are relatively prime for all n.

Answer 1

Suppose that there exists some k such that 5n + 3 ≡ 7n + 4 ≡ 0 (mod k). If this is the case, then the difference between 7n + 4 and 5n + 3 must also be 0 mod k, i.e.

Answer 2

Use the fact about gcd:
d=(a,b) if and only if there exist integer p, q such that
pa + qb = d.
Hence, (a,b) = 1 if and only if there exist integer p, q such that
pa + qb = 1.

Now, 3(5n+3)-2(7n+ 4) = 15n + 9 -14n- 8 = 1
So, (5n+3, 7n+ 4) = 1 ie (5n+3 ) and (7n+ 4) are relative prime for all n.

Answer 3

hope that helps