| (2 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| + | =[[HW1_MA453Fall2008walther|HW1]], Chapter 0, Problem 14, [[MA453]], Fall 2008, [[user:walther|Prof. Walther]]= | ||
| + | ==Problem Statement== | ||
Show that <math> 5*n + 3 </math> and <math> 7*n + 4 </math> are relatively prime. | Show that <math> 5*n + 3 </math> and <math> 7*n + 4 </math> are relatively prime. | ||
| − | <math> | + | |
| − | 7*n + 4 = 5*n + 3 + 2*n + 1< | + | ---- |
| − | 5*n + 3 = 2*(2*n + 1) + n + 1 | + | ==Discussion== |
| − | 2*n + 1 = 1*(n + 1) + n | + | |
| − | n + 1 = 1*n + 1 | + | Show that <math> 5*n + 3 </math> and <math> 7*n + 4 </math> are relatively prime. |
| − | </math> | + | |
| + | <math>7*n + 4 = 5*n + 3 + 2*n + 1</math> | ||
| + | |||
| + | <math>5*n + 3 = 2*(2*n + 1) + n + 1</math> | ||
| + | |||
| + | <math>2*n + 1 = 1*(n + 1) + n</math> | ||
| + | |||
| + | <math>n + 1 = 1*n + 1</math> | ||
| + | |||
After constant long division we get to the base equation where there is still a remainder of 1. | After constant long division we get to the base equation where there is still a remainder of 1. | ||
Therefore <math> 5*n + 3 </math> and <math> 7*n + 4 </math> are relatively prime. | Therefore <math> 5*n + 3 </math> and <math> 7*n + 4 </math> are relatively prime. | ||
| + | |||
| + | == Even easier would be to use the Euclidean Algorithm == | ||
| + | <math>gcd(5*n + 3, 7*n + 4) = gcd(5*n + 3, 2*n + 1)</math> | ||
| + | <math> = gcd(3*n + 2, 2*n + 1)</math> | ||
| + | <math> = gcd(n + 1, 2*n + 1)</math> | ||
| + | <math> = gcd(n + 1, n)</math> | ||
| + | <math> = gcd(1, n)</math> | ||
| + | <math> = 1</math> | ||
| + | |||
| + | Since the GCD of the two expressions is one for all n, they are relatively prime. | ||
| + | ---- | ||
| + | [[HW1_MA453Fall2008walther|Back to HW1]] | ||
| + | |||
| + | [[Main_Page_MA453Fall2008walther|Back to MA453 Fall 2008 Prof. Walther]] | ||
Latest revision as of 16:49, 22 October 2010
Contents
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.
