Re: A Possible (or not) Proof for the Eudoxius' Theorem - Number Theory - Help

In article
<59ff165a-efa1-4220-a6c6-24175e8c54fe@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"cezar.schroeder" <cezar.schroeder@xxxxxxxxx> wrote:

Hi! The Eudoxius' Theorem is essencial to correctly understand the
proof of the existence and uniqueness of the remainder and the
quotient of division, everybody knows it. But I'm reading a book that
mentions this theorem, but does not present a proof for it. So I
searched on the Internet a proof for this theorem, but I did not find
it. So I tried to write a proof by myself. But I'm still a student,
not a professor, so I ask you all to help me with this task, saying
where I'm wrong and suggesting some improvements or corrections. I
really want to thank you. Below is the theorem and its possible proof
that I wrote. And if someone has a more elegant proof for this
theorem, please say it to me. Thanks.

Eudoxius' Theorem: Given a and b integers with b != (different) 0 then
a is a multiple of b or is between two consecutive multiples of b, it
means, for each integers pair a and b, with b != 0, there is another
integer q such as, for b > 0,

q*b <= a < (q + 1)*b

and for b < 0,

q*b <= a < (q - 1)*b

I'm sorry, I can't follow your proof in detail, but the way it's usually
done is by invoking well-ordering. Let S be the intersection of the set
of all numbers of the form a - s b, s running through the integers,
with the non-negative integers. By well-ordering, S has a least element,
call that element r, so r = a - q b for some q. It follows (in the b > 0
case) that a - (q + 1) b < 0, and you're pretty much done.

Proof: Given a and b satisfying the hypotheses of the theorem, or b|a
(b divides a) or b does not divide a. In case that b divides a we know
that a is a multiple of b, in the other side, in case that b does not
divide a, we know that a is not a multiple of b. So we divide the
proof in two cases, one case considering that a is multiple of b, and
in another case considering that a is not a multiple of b.

(1) a is multiple of b. (b divides a)

It means that b|a and that a = q*b, for some q. It demonstrates the
first case of the theorem.

(2) a is not a multiple of b. (b does not divide a)

If b does not divide a, then we have that a < k*b, it means, a must be
minor than one multiple of b, for some k. And more, q*b < a, it means,
a must must be greater than one multiple of b for some q, with k and q
integers. Then we have that a is between two multiples of b. It's
possible to say this because the set of integers has some properties
that guarantees it. So we have,

q*b < a < k*b

What we have to prove now is that k = q + 1 for b > 0, and k = q - 1
for b < 0. In other words, we need to show that a is between two
consecutive multiples of b. We'll prove for the case b > 0, but the
case b < 0 is on the same way. Let, by contradiction, k != 0. Then k >
q + 1. We know that q*b < a < k*b, it means that a can assume any
values in this interval, so we have that a can be equal to (q + 1)*b
and then a = (q + 1)*b means that a can be a multiple of b, wich
contradicts the hypothesis of the part (2) of the proof of this
theorem. Then, k must be equal to (q + 1) and then q*b < a < (q +
1)*b.

Gathering parts (1) and (2) of our proof, we have the final result of
the theorem,

q*b <= a < (q + 1)*b, for b > 0.

As we said, the proof of this theorem for the case b < 0 is very
similar to this one presented. The only thing you have to do is let,
by contradiction that k != q - 1, it means that k > q - 1, and you'll
have,

q*b <= a < (q - 1)*b.

It completes the proof. [ ]

I have the sensation at this moment that I'm considering the result of
the theorem to prove the result of the theorem, but I'm not sure about
it. I'm still a student, and a not smart one. That's why I'm asking
you all to help me on this task. Thanks a lot.

--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)
.

Relevant Pages

  • Re: JSH: Without a trace
    ... given a multiple of a polynomial it has been well ... > and it is true that you can divide 5 from that factorizaton giving ... > without leaving a trace. ... > In my case I have precedent from thousands of years of mathematics ...
    (sci.math)
  • Re: Periodicity of a^n mod c
    ... divisor of 2^. ... and then take the least common multiple of these orders. ... possible exponent m = m, ... and the exponent of a will divide the resulting quotient ...
    (sci.math)
  • Re: 64-bits is not necessarily faster ?
    ... Add and subtract are twice as fast, multiple and divide tens of times. ... Memory pointers, file index/pointers, nano-sec timers, more ... Great for algorithmic functions and function calls. ...
    (borland.public.delphi.non-technical)
  • A Possible (or not) Proof for the Eudoxius Theorem - Number Theory - Help
    ... The Eudoxius' Theorem is essencial to correctly understand the ... where I'm wrong and suggesting some improvements or corrections. ... a is a multiple of b or is between two consecutive multiples of b, ... divide a, we know that a is not a multiple of b. ...
    (sci.math)
Quantcast