I'm a very newbie, even if I studied some math at college... Now I'm trying to study "Contemporary Abstract Algebra", by J.A. Gallian but I'm already facing some difficulties trying to understand the proof of the very first theorem (0.1) about division algorithm.

The theorem says:

Let a and b be integers with $b > 0$. Then there exist unique integers q and r with the property that $a=bq + r$, where $0\le r\le b$

The proof starts in this way:

We begin with the existence portion of the theorem.

Ok, what does that mean? Moreover:

Consider the set S = {$a - bk | k$ is an integer and $a - bk\ge 0$}.

Ok, what are we talking about? What is k? Why doesn't he use q? What kind of set is this? Is a set with just this "difference" between a and bk? Why?

Shall I ever be able to understand this?

Thanks a lot

  • $\begingroup$ The statement of the theorem makes two claims: (i) that there exists such a representation (ii) that the representation is unique. So the existence portion asks you to show such a representation exists. The set S consists of all remainders of a after taking out b factors of k. He doesn't use q in the definition because q is just one instance of the possible values of q $\endgroup$ – User0112358 Oct 21 '15 at 11:15
  • $\begingroup$ The notation$$\{a-bk\mid k\text{ is an integer and }a-bk\ge0\}$$means, the set ("collection") of nonnegative numbers that can be written in the form $a-bk$. That is, it's $\{a-b,a-2b,a-3b,\dots\}$; or, at least, the set of nonnegative numbers in that. $\endgroup$ – Akiva Weinberger Oct 21 '15 at 13:39
  • $\begingroup$ I believe this is called "set-builder notation." $\endgroup$ – Akiva Weinberger Oct 21 '15 at 13:41

Theorem itself makes two statements at first

  • Our numbers $q$ and $r$ always exists regardless of choice of $a$ and b
  • That these two numbers are unique such that we cannot find any other $p$ and $s$ that satesfies the same equality without us having $q=p$ and $r=s$

It is commonly done so that one starts with existence in such broad theorems because the existence is often the most important, so we know it does exist somehow. And once it exists we want to show it is unique and not multiple ones exist. This is important because in many branches of mathematics the objects satesfying a certain criteria is not necciserly a singular object but a whole collection of them, often infinitely many.

Consider the set S = {$a - bk | k$ is an integer and $a - bk\ge 0$}.

What this mean is that we construct a set of elements $c\in\mathbb{Z}$ such that we have that $c>0$ and $c=a-bk$ for some $k\in\mathbb{Z}$, why he doesn't use $q$ is because the $q$ is what we wish to find, while here we are constructing a general set to argue from using known properties about the integers and it's subsets, for example for positive integer subsets there is a smallest integer. Often you wish to do this in order to reach some kind of contradiction where an element is in the set, yet cannot be in the set, and as such, depending on the arguement, we get that the element must satesfy the contrapositive statement of what is assumed.


Let's take the questions one at a time:

First the theorem states that there exist unique integers $q$ and $r$.

Thus we have in some sense two parts to prove:

  • First that such $q$ and $r$ exist
  • Second that such $q$ and $r$ are unique

These two parts can be proven completely independently (You can show that any such $q$ and $r$ are unique without showing that they exist, this might seem a bit strange at first).

$k$ is any integer. $q$ is not used since it is supposed to be the specific integer which has the properties described in the theorem statement. As for what set that is I'm not sure what you are asking. The definition of the set will be apparent as you proceed further into the proof since its properties will (presumably) be used.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.