Answer:
The gcd(474,147) = 3 and the linear combination is
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:
- Let a=x, b=y
- Given x,y, use the division algorithm to write x=yq + r
- if r=0, stop and output y; this is the gcd of a,b
- 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

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

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

To find the linear combination you need to use the Bezout's identity that says that the equation
has solutions x, y. So we need to find the solution of the equation
.
To find the values of x and y you can run the Euclidean Algorithm backward.
We know that

We can express 3 as linear combination

The gcd(474,147) = 3 and the linear combination is

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
- P(1) is true, and
- 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

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.

we know that
for the inductive assumption

we see that the result
, 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.