Scribd
Upload
11 views4 pages

Sample Theorem Environment (1)

Uploaded by

DhananjayareddyThanakanti
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views4 pages

Sample Theorem Environment (1)

Uploaded by

DhananjayareddyThanakanti
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

sample theorem environment

dhananjayareddyt
December 2024

The argument you’ve presented is a direct application of the Division Algorithm along with the Well-
Ordering Principle. Let’s go through it carefully to clarify the reasoning and formalize the steps.
Step-by-Step Explanation:
1. Setting Up the Problem: You are given integers a and b such that a > b ≥ 1. The goal is to show
that there exists an integer q (the quotient) and an integer r (the remainder) such that:

a = qb + r where 0 ≤ r < b.

2. Using the Well-Ordering Principle: The Well-Ordering Principle states that any non-empty
subset of the positive integers has a least element. We will use this principle to find the least possible
remainder r when dividing a by b.
To divide a by b, we are interested in the multiples of b that are less than or equal to a. These multiples
form the set:
{0, b, 2b, 3b, . . . }
Among these multiples, there must be a least multiple of b that is greater than a, i.e., (q + 1)b > a, where q
is the largest integer such that qb ≤ a.
Hence, we can conclude that there exists an integer q such that:

qb ≤ a < (q + 1)b.

This means a is between two consecutive multiples of b, so a can be written as:

a = qb + r

where r is the remainder when dividing a by b.


3. Properties of the Remainder: From the inequality qb ≤ a < (q + 1)b, we can derive the following
properties of r:
- Since qb ≤ a, we know that r = a − qb ≥ 0. This gives 0 ≤ r. - From a < (q + 1)b, we know that
r = a − qb < b. This gives r < b.
Therefore, the remainder r satisfies:
0 ≤ r < b.
4. Conclusion: We have shown that there exists an integer q such that:

a = qb + r

where 0 ≤ r < b. This is the Division Algorithm, which provides a way to express any integer a as a multiple
of b plus a remainder r that is strictly less than b.

1
Euclidean Algorithm Process:
1. Start with two integers a and b, where a > b.
2. Divide a by b, and find the quotient q and remainder r, such that:

a = bq + r

where 0 ≤ r < b. This is the equation you referred to as equation (1.1).


3. If r = 0, the algorithm terminates, and the GCD is b, since there is no remainder.
4. If r ̸= 0, repeat the process using b and r in place of a and b, respectively. That is, apply the algorithm
to:
a = b, b = r
and repeat the division process.

5. The algorithm will terminate when the remainder becomes zero, and the last non-zero remainder is
the GCD of a and b.
Key points:

• Each step reduces the value of the remainder, ensuring the process eventually terminates.
• The Euclidean algorithm is guaranteed to find the GCD after a finite number of steps because the
remainder decreases with each division.
• The process can be repeated as long as r ̸= 0, and the final remainder when r = 0 gives the greatest
common divisor.

2
The greatest common divisor (sometimes called the highest common factor) of two positive integers a
and b is defined to be the positive integer d such that
1. d divides both a and b, and
2. if c is any other factor of a and b, then c divides d.

The notation d = (a, b) is often used. If (a, b) = 1, then a and b are said to be coprime or relatively prime.
Hence, 21 and 16 are coprime.
Repeated use of the Euclidean algorithm provides the greatest common divisor as the last non-zero
remainder (in almost all cases, but why is the statement not quite true?). Thus, (893, 705) = 47. The
claim that 47 is the highest common factor arises from the following argument, which makes repeated use
of Theorem 1.1.2:
1. First, 47 divides 141 and hence divides 188. Since it divides both 141 and 188, it divides 705. It divides
188 and 705, and so it divides 893. Therefore, 47 is a factor of 705 and 893.
2. Secondly, working the other way around, if c divides both 893 and 705, it must divide 188. Since c
divides both 705 and 188, it must divide 141, and hence it must divide 47. Therefore, 47 satisfies both
property (i) and property (ii) of the above definition and is the greatest common divisor.
The (slightly damaged) argument that repeated use of the Euclidean algorithm always provides the greatest
common divisor as the last non-zero remainder follows precisely the same form as that used for 893 and 705.
To write the argument out in detail using letters rather than numbers provides no further insight and so is
omitted.

3
If a | m and b | m, then m is a common multiple of a and b. If m has the properties
1. that it is a common multiple of a and b, and
2. m | n whenever n is a common multiple of a and b,
then m is called the least common multiple of a and b.
The notation m = [a, b] is often used.
The least common multiple of 893 and 705 is 13395.
In the exercises below, you should not express integers as products of their prime factors since we have
not yet shown that such factorizations are unique. You should only use the concepts we have covered so far.

You might also like