Question 408264
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.


2n + 1 ≡ 5n + 3 (mod k), in addition (5n + 3) - (2n + 1) ≡ 0, so


3n + 2 ≡ 0 (mod k)


6n + 4 ≡ 0 (mod k)


This implies 6n + 4 ≡ 7n + 4 ≡ 0 (mod k) so n ≡ 0 (mod k). However, if n ≡ 0 (mod k), then 5n + 3 ≡ 3 (mod k) and 7n + 4 ≡ 4 (mod k) so this implies that 3 ≡ 4 (mod k), contradiction (unless k = 1). Hence, 5n + 3 and 7n + 4 are relatively prime (for all integers n).


I kinda feel like there's a shorter way to prove this...care to find another solution?