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

Alumni Liaison

Abstract algebra continues the conceptual developments of linear algebra, on an even grander scale.

Dr. Paul Garrett