HW1, Chapter 0, Problem 14, MA453, Fall 2008, Prof. Walther

Problem Statement

Show that $ 5*n + 3 $ and $ 7*n + 4 $ are relatively prime.

Discussion

Show that $ 5*n + 3 $ and $ 7*n + 4 $ are relatively prime.

$ 7*n + 4 = 5*n + 3 + 2*n + 1 $

$ 5*n + 3 = 2*(2*n + 1) + n + 1 $

$ 2*n + 1 = 1*(n + 1) + n $

$ n + 1 = 1*n + 1 $

After constant long division we get to the base equation where there is still a remainder of 1. Therefore $ 5*n + 3 $ and $ 7*n + 4 $ are relatively prime.

Even easier would be to use the Euclidean Algorithm

$ gcd(5*n + 3, 7*n + 4) = gcd(5*n + 3, 2*n + 1) $ $ = gcd(3*n + 2, 2*n + 1) $ $ = gcd(n + 1, 2*n + 1) $ $ = gcd(n + 1, n) $ $ = gcd(1, n) $ $ = 1 $

Since the GCD of the two expressions is one for all n, they are relatively prime.

Back to HW1

Back to MA453 Fall 2008 Prof. Walther