Proof of the Division Algorithm

In summary, the conversation discusses the well ordering principle (WOP) and its application in the proof of the division algorithm. The speaker questions whether the WOP can be applied to a subset of non-negative integers, to which the other person explains that it would mean any subset of the non-negative integers has a least element. The conversation ends with a lighthearted remark about living in "senior moments".
  • #1
matqkks
285
5
In many books on number theory they define the well ordering principle (WOP) as:
Every non- empty subset of positive integers has a least element.
Then they use this in the proof of the division algorithm by constructing non-negative integers and applying WOP to this construction. Is it possible to apply the WOP to a subset of non-negative integers? Am I being too pedantic?
 
Mathematics news on Phys.org
  • #2
It's rather obvious isn't it? "Applying the WOP to a subset of non-negative integers" would simply mean that, given X, a subset of the non-negative integers, any subset of X has a least member. And that is true because any subset of X is also a subset of the non-negative integers.

If that is not what you mean then please explain what you mean by "apply the WOP to a subset of non-negative integers".​
 
Last edited by a moderator:
  • #3
Yes of course. I just had a senior moment.
Thanks.
 
  • #4
There are those of use who live in "senior moments"! We are called "seniors".
 
Last edited by a moderator:

What is the Division Algorithm?

The Division Algorithm is a mathematical theorem that states that any two positive integers, a and b, can be divided in such a way that the remainder is always less than b. This theorem is used to prove the existence and uniqueness of the quotient and remainder when dividing two integers.

What is the proof of the Division Algorithm?

The proof of the Division Algorithm involves using the Well-Ordering Principle, which states that every non-empty set of positive integers has a least element. By using this principle, we can prove that there exists a unique quotient and remainder when dividing two positive integers.

Why is the Division Algorithm important?

The Division Algorithm is important because it provides a systematic way to divide two integers and obtain a unique quotient and remainder. This theorem is used in various mathematical concepts, such as Euclidean algorithm, greatest common divisor, and modular arithmetic.

Can the Division Algorithm be extended to other number systems?

Yes, the Division Algorithm can be extended to other number systems, such as rational numbers, real numbers, and complex numbers. The proof for these number systems may differ, but the concept remains the same.

Are there any limitations to the Division Algorithm?

Yes, the Division Algorithm only applies to positive integers. It cannot be used for negative numbers or fractions. Additionally, the remainder must always be less than the divisor, otherwise the algorithm cannot be applied.

Similar threads

I Proof of the Division Algorithm
    • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
I Is an algorithm for a proof required to halt?
    • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
I Is this a proof of the Collatz Conjecture?
    • General Math
Replies
8
Views
2K
I Is this proof of the least common multiple theorem in number theory valid?
    • General Math
Replies
1
Views
818
B Binomial Expansion with Negative/Rational Powers
    • General Math
Replies
25
Views
5K
Challenge: Find the minimum amount of draws possible for a list of integers
    • Programming and Computer Science
Replies
9
Views
1K
Prove every subset of countable set is either finite or else countable
    • Calculus and Beyond Homework Help
Replies
1
Views
509
I Fair distribution, minimizing envy
    • General Math
Replies
2
Views
965
B Doing proofs: Setting an expression as a variable
    • General Math
Replies
3
Views
819
Proof of irrationality of sqrt2 in Penroses Road to Reality
    • General Math
Replies
2
Views
1K

Hot Threads

Recent Insights

Back
Top