Question

Q: Would like assistance in understanding and solving this example on Modern Algebra with the steps of the solution to better understand, thanks.

a) Determine the gcd(474,147) and write it as a linear combination of 174 and 147.

b) Prove by math induction that 2+4+6+...+2n = n(n+1) for all positive integers n.

Answer 1

The gcd(474,147) = 3 and the linear combination is
`3=9\cdot 474 - 29\cdot 147` and the proof is below.

Explanation:

The greatest common divisor (GCD) of two whole numbers is the largest natural number that divides evenly into both without a remainder.

To find the GCD you can use the Euclidean algorithm which is an efficient method for computing the greatest common divisor (GCD) of two integers, without explicitly factoring the two integers. Here is an outline of the steps:

1. Let a=x, b=y
2. Given x,y, use the division algorithm to write x=yq + r
3. if r=0, stop and output y; this is the gcd of a,b
4. if r ≠ 0, replace (x,t) by (y,r): Go to step 2

To compute gcd(474,147), divide the larger number by the smaller number, using the division algorithm we have

`(474)/(147) \\= 474-147=327\\327-147=180\\180-147=33\\`

At this point, we cannot subtract 147 again. Hence 3 is the quotient ( we subtract 147 from 474 3 times) and 33 is the remainder. We can express this as a linear combination
`474 = 147*3+33`

Using the same reasoning and the steps of the Euclidean algorithm we have

`gcd(474,147) = \\474 =147\cdot 3+33\\147=33\cdot 4 +15\\33=15\cdot 2+3\\15=3\cdot 5+0`

To find the linear combination you need to use the Bezout's identity that says that the equation
`ax+by=gcd(a,b)` has solutions x, y. So we need to find the solution of the equation
`474x+147y=3`.

To find the values of x and y you can run the Euclidean Algorithm backward.

We know that

`33=15\cdot 2+3`

We can express 3 as linear combination

`3=33- 2\cdot15\\3=33-2\cdot(147-33*4)=9\cdot 33 -2\cdot147\\3=9\cdot 33 -2\cdot147=9\cdot (474-147\cdot 3)-2 \cdot 147\\3= 9\cdot 474-27 \cdot 147-2 \cdot 147\\3=9\cdot 474 - 29\cdot 147`

The gcd(474,147) = 3 and the linear combination is
`3=9\cdot 474 - 29\cdot 147`

The principle of mathematical induction is stated as follows:

Let n be a natural number and let P(n) be an statement that depends on n. If

1. P(1) is true, and
2. for all positive integer k, P(k+1) can be shown to be true if P(k) is assumed to be true,

Then P(n) is true for all natural numbers n.

Proposition: For all positive integers n, 2+4+6+...+2n = n(n+1).

Proof. Let's let P(n) be the statement "2+4+6+...+2n = n(n+1)" .The proof will now proceed in two steps: the initial step and the inductive step.

Initial step. We must verify that P(1) is true

`n=1\\2\cdot 1=1\cdot (1+1)`

which is clearly true. So we are done with the initial step.

Inductive step. We must prove the following assertion: "If there is a k such that P(k) is true, then (for this same k) P(k+1) is true." Thus, we assume there is a k such that 2+4+6+...+2k = k(k+1), this is called the inductive assumption. We must prove, for this same k, the formula P(k+1): 2+4+6+...+2k+2(k+1) = (k+1)(k+2)

To prove that P(k+1) holds, we will start with the expression on the left-hand side of P(k+1) and show that it is equal to the expression on the right-hand side.

`2+4+6+...+2k+2(k+1)`

we know that
`2+4+6+...+2k+2(k+1)=k(k+1)` for the inductive assumption

`k(k+1)+2(k+1)\\k^(2)+k+2k+2\\k^2+3k+2\\(k+1)(k+2)`

we see that the result
`(k+1)(k+2)`, is the expression on the right-hand side of P(k+1). Thus by mathematical induction P(n) is true for all natural numbers n.