Number Theory - The Division Algorithm

[jpanknin]

I'm going through Elementary Number Theory, 2E by Charles Vanden Eynden. In section 1.2 he discusses The Division Algorithm and then provides a proof (pic attached). He goes from [imath]b=aq+r[/imath] to [imath]b = aq' + r'[/imath], but gives no explanation for what [imath]q'[/imath] and [imath]r'[/imath] are. Can anyone explain what the q' and r' mean?

 

[Steven G]

The author said that q and r are unique.
The typical way of proving uniqueness is to assume otherwise and conclude that you were wrong.
As a result, you assume that there are q' and r' and then show that q' must equal q and r' must equal r. Then and only then will p and q be unique.

 

[jpanknin]

Ok, so it's just saying that r/r' and q/q' prime represent different numbers (integers in this case)? I saw another explanation that used r1 and r2 instead of r/r'. So that would make sense.

 

[Steven G]

r1 and r2 are assumed to be different just like r and r' are assumed to be different.
You can, if you like, use r and s and show that s=r to conclude r is unique. The name that you choose for the other r is up to you. Personally I like to choose harvey for the other r!

 

[jpanknin]

Ha! I'll use harvey or "steve_the_squirrel" as variable names from now on. Appreciate the replies and the clarification very much.

 

[JeffM]

I must say that the proof as given is not ideal. (This may not be true in the context of more of the text.)

Ignoring the trivial typo of “if” rather than “it,” lets follow the language of the proof.

[math]\text {Suppose the real number } b/a \text { is } q + \epsilon, \text { where } q \text { is an integer and } 0 \le \epsilon < 1.[/math]
OK. I choose as an example [imath]\dfrac{\pi}{e}[/imath], which is a real number, where q is the integer 1 and [imath]0 < 0.1557 < \epsilon < 0.1558 < 1.[/imath] So far, so good.

The proof does some simple algebra to show that [imath]b = aq + a \epsilon[/imath] and then states without proof that it
[imath] \text {follows that } a \epsilon \text { is an integer.}[/imath] But it is obvious from my example that the conclusion is false.

The conclusion is true of course if b/a is a rational number, but we are specifically told that b/a may be irrational.

 

[Dr.Peterson]

I must say that the proof as given is not ideal. (This may not be true in the context of more of the text.)

Ignoring the trivial typo of “if” rather than “it,” lets follow the language of the proof.

[math]\text {Suppose the real number } b/a \text { is } q + \epsilon, \text { where } q \text { is an integer and } 0 \le \epsilon < 1.[/math]
OK. I choose as an example [imath]\dfrac{\pi}{e}[/imath], which is a real number, where q is the integer 1 and [imath]0 < 0.1557 < \epsilon < 0.1558 < 1.[/imath] So far, so good.

The proof does some simple algebra to show that [imath]b = aq + a \epsilon[/imath] and then states without proof that it
[imath] \text {follows that } a \epsilon \text { is an integer.}[/imath] But it is obvious from my example that the conclusion is false.

The conclusion is true of course if b/a is a rational number, but we are specifically told that b/a may be irrational.

What's missing is a statement of what is being proved. I assume it said that a and b are integers. (I see no mention of anything being irrational.)

Here is a typical statement:

If a and b are integers and b>0 then there exist unique integers q and r satisfying the two conditions: a = bq + r and 0 ≤ r < b.​

 

[jpanknin]

What's missing is a statement of what is being proved. I assume it said that a and b are integers. (I see no mention of anything being irrational.)

Here is a typical statement:

If a and b are integers and b>0 then there exist unique integers q and r satisfying the two conditions: a = bq + r and 0 ≤ r < b.​

The theorem does state that a and be are integers. Attached are photos of the Theorem, the proof, and some examples.

 

[JeffM]

What's missing is a statement of what is being proved. I assume it said that a and b are integers. (I see no mention of anything being irrational.)

Here is a typical statement:

If a and b are integers and b>0 then there exist unique integers q and r satisfying the two conditions: a = bq + r and 0 ≤ r < b.​

When something is said to be “real,“, I do not read that as meaning “exclusively rational.“ In fact, whenever I see a statement that purports to be true of real numbers, I test it against irrational numbers. As I explicitly stated in my original post, however, context not supplied might be relevant.

If b and a are real (including irrational) and a is positive, a non-negative remainder less than a and an integer quotient exist and are unique, but then the theorem about the remainder being an integer is not generally true. The only thing needed for a more general proof about reals is [imath]0 \le a \epsilon < |a|.[/imath]

I still think that a proof saying “real number” when when what is meant is a rational number is not ideal. Mathematicians are supposed to be careful. But obviously if a and b are integers and a is positive, the proof given is valid.

 

[Dr.Peterson]

When something is said to be “real,“, I do not read that as meaning “exclusively rational.“ In fact, whenever I see a statement that purports to be true of real numbers, I test it against irrational numbers. As I explicitly stated in my original post, however, context not supplied might be relevant.

If b and a are real (including irrational) and a is positive, a non-negative remainder less than a and an integer quotient exist and are unique, but then the theorem about the remainder being an integer is not generally true. The only thing needed for a more general proof about reals is [imath]0 \le a \epsilon < |a|.[/imath]

I still think that a proof saying “real number” when when what is meant is a rational number is not ideal. Mathematicians are supposed to be careful. But obviously if a and b are integers and a is positive, the proof given is valid.

That's what I thought you might be thinking, because the context was missing. Having started without seeing the theorem in front of you, I think you misinterpreted what the proof is saying.

It is not just saying, "Suppose b/a is any real number, then ..."; it is saying, "Given that a and b are integers, b/a is a real number (that is, not necessarily an integer, but not implying it can be any real number), so we can suppose ...". I think the only reason they use the word "real" is that they are about to make statements that apply to a larger set than the integers; they are warning the reader to take off their "integer glasses".

They could have said "rational", but that is not the point they want to make. What immediately follows can be said of any real number, based on axioms for the real numbers. What is said subsequently is conditioned on the fact that a and b (and q and r) are integers.

I think they were being careful. The OP was not careful to include the context, which provides the basis for what is said here, and without which it might be confusing.

 

[JeffM]

That's what I thought you might be thinking, because the context was missing. Having started without seeing the theorem in front of you, I think you misinterpreted what the proof is saying.

It is not just saying, "Suppose b/a is any real number, then ..."; it is saying, "Given that a and b are integers, b/a is a real number (that is, not necessarily an integer, but not implying it can be any real number), so we can suppose ...". I think the only reason they use the word "real" is that they are about to make statements that apply to a larger set than the integers; they are warning the reader to take off their "integer glasses".

They could have said "rational", but that is not the point they want to make. What immediately follows can be said of any real number, based on axioms for the real numbers. What is said subsequently is conditioned on the fact that a and b (and q and r) are integers.

I think they were being careful. The OP was not careful to include the context, which provides the basis for what is said here, and without which it might be confusing.

I am not going to blame the OP because his question was about another issue entirely.

I was trying to follow the proof (recognizing that relevant context might be missing). Your formulation, “given that a and b are integers [and a is positive]“ makes the proof easy to follow.