Consider the two sets

$$A_r = \{x \in \mathbb{Z} \enspace | \enspace x \enspace = \enspace 5q + r, \enspace 0 \enspace \leq \enspace r \enspace < \enspace 5\}$$

$$\Lambda = \{A_r\}$$

We must show that $\Lambda$ is a partition of the set $\mathbb{Z}$.

I know that I must show that $\emptyset \notin \Lambda$, that two sets $A_r \cap A_k = \emptyset $ where $ 0 \leq k,r < 5$, which can be done by assuming that if $x \in A_r,A_k$, then $A_r = A_k$ where $k$ is an arbitrary integer; and, finally, the union of all the sets in $\Lambda$ is precisely the set $\mathbb{Z}$.

I am not allowed to use the division algorithm, which would make quick work of the first property of a partition. I assume that one plan of attack to show that the first property is fulfilled is by exhaustion; that is, for each $r$, we can find an integer $q$ where $x \in A_r$. Would this be right? Is there an alternative route?

As for the other two properties, I am not sure how to start. Any insights?

  • $\begingroup$ How do you mean 'you are not allowed to use the division algorithm'? The statement to prove translates as: for each integer $x$ there is exactly one integer $0\le r<5$ (this is the remainder mod $5$) such that $x=5q+r$ for some $q\in\Bbb Z$. $\endgroup$
    – Berci
    Sep 22, 2015 at 20:41
  • $\begingroup$ The proof appears in a chapter that precedes the chapter on the division algorithm, so I assumed that I couldn't use the division algorithm. In other words, since the proof appears before any mention of the division algorithm, there may be a way to prove the desired result without appealing to the division algorithm. $\endgroup$
    – J. Dunivin
    Sep 22, 2015 at 22:14

1 Answer 1


There's an alternative route, kind of, although it involves sneakily proving the division algorithm.

  • Everything in any of those sets is an integer. That's just obvious.

  • The sets do cover $\mathbb{Z}$. Indeed, suppose $n$ were the least nonnegative integer not in some $A_r$. Note that $n \geq 5$ since $n \in A_n$ for $n \in \{0, 1, 2, 3, 4 \}$.
    Now, $n-5$ is in some $A_r$ - say it's $5q+r$ - so $(n-5)+5$ is in the same $A_r$ (simply express it as $5(q+1)+r$). This is a contradiction, so all positive integers are in some $A_r$. Similar reasoning for the negatives.

  • The sets are all distinct. Indeed, suppose $x \in A_r$ and $x \in A_s$. Then $x = 5p+r = 5q+s$, so $5(p-q) = s-r$. But $r, s \in \{0, 1, 2, 3, 4 \}$, and the only way $s-r$ can be divisible by 5 if $r, s$ come from that list is if $s-r=0$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .