Question

Prove that if \(m\) and \(n\) are both even, then gcd \((m, n)=2 \operatorname{gcd}(m / 2, n / 2)\).

Short answer

The statement that if \(m\) and \(n\) are both even, then gcd(\(m, n\))=2gcd(\(m/2, n/2\)) is true.

Step-by-step solution

Establishing the integers

Given that \(m\) and \(n\) are even, then we can always express them as \(m = 2m'\) and \(n = 2n'\) respectively where both \(m'\) and \(n'\) are integers.

Stating the property of gcd

gcd(a, b) is numerically equal to gcd(b, a mod b), and gcd(a, 0) = a. Also, if 'k' is a non-zero integer, then gcd(ka, kb) = |k| gcd(a, b).

Applying the gcd property

Therefore, gcd(\(m, n\)) = gcd(\(2m'\, 2n'\)) = 2gcd(\(m', n'\)) = 2gcd(\(m/2, n/2\)). Hence proved.

Key concepts

Even Integers

Even integers are the building blocks of our problem statement. Essentially, an 'even integer' is any number that can be precisely divided by two without leaving a remainder. We can denote an even integer by the mathematical representation of 2 times another integer, expressed as

\( 2k \),

where \((k)\) is any integer. This fundamental characteristic is at the heart of the exercise, as it allows us to explore properties of the greatest common divisor (gcd) when dealing with pairs of even numbers. For instance, if \((m)\) and \((n)\) are both even integers, we can denote them as \((m = 2m')\) and \((n = 2n')\), where \((m')\) and \((n')\) are integers, making our first step in the gcd calculation.

Properties of GCD

Understanding the properties of the greatest common divisor (gcd) is essential in solving our given exercise. The gcd of two integers \((a)\) and \((b)\) is the largest positive integer that divides both \((a)\) and \((b)\) without any remainder. A key property we use in our solution is that the gcd of two numbers remains unchanged if the same non-zero integer is multiplied to both numbers. In mathematical terms, this is written as

\( \text{gcd}(ka, kb) = |k| \cdot \text{gcd}(a, b)\),

where \((k)\) is a non-zero integer. This property profoundly simplifies the original exercise, as we can factor out the common \((2)\) from even integers \((m)\) and \((n)\) to achieve \((\text{gcd}(m, n) = 2 \text{gcd}(m/2, n/2))\). Additionally, the property gcd(\((a, 0)\)) = \((a)\) is essential in concluding that the gcd does not change when dealing with a multiplication factor of two—critical in the solution process.

Proof Techniques in Mathematics

Proof techniques are the tools mathematicians use to verify the truth of mathematical assertions. In our exercise, we've employed a direct proof, which is a straightforward method used to show the truth of a statement by a logical sequence of assertions. Starting with known facts and utilizing defined operations or previously proven properties, we reach the conclusion.

For instance, in step one, we define \((m)\) and \((n)\) based on their even integer property. In step two, we state the proper gcd properties relevant to our problem. Finally, in step three, we directly apply these properties to demonstrate that \((\text{gcd}(m, n) = 2 \text{gcd}(m/2, n/2)\)). This demonstrates a successful application of a proof technique that brings clarity and confirmation to our mathematical assertion.