Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is my problem:

For every couple of integers $(a,b)\in\mathbb{Z}\times(\mathbb{Z}\backslash\{0\})$ we denote with $r(a,b)$ the remainder of the division between $a$ and $b$. Consider the application $$f:(a,b)\in\mathbb{Z}\times(\mathbb{Z}\backslash\{0\})\rightarrow r(a,b)\in\mathbb{N}$$

  1. Talk about injectivity and surjectivity
  2. Considering in $\mathbb{Z}\times(\mathbb{Z}\backslash\{0\})$ the following relation $$(a,b)\varphi(c,t)\Leftrightarrow r(a,b)=r(c,t)$$ $$(a,b)\pi(c,t)\Leftrightarrow(a,b)=(c,t)\quad OR\quad r(a,b)<r(c,t)$$ 2.1 Prove that $\varphi$ is equivalence relation in $\mathbb{Z}\times(\mathbb{Z}\backslash\{0\})$, and show the equivalence class of $(6,3)$

    2.2 Prove that $\pi$ is an order relation in $\mathbb{Z}\times(\mathbb{Z}\backslash\{0\})$. Is this total? In the ordered structure $(\mathbb{Z}\times(\mathbb{Z}\backslash\{0\}),\pi)$ find min, max, minimal and maximal element.

On first point, the function is not injective, cause exists at least two couple of integer that broke injection definition. (E.g. $10/3$ and $11/10$ has the same remainder). Is surjective 'cause every division between two integer number gave a remainder in $\mathbb{N}$.

For the point 2.1, a given binary relation on a set A is said to be an equivalence relation if and only if it is reflexive, symmetric and transitive. In our case:

  • reflexive: cause if $r(a,b)$ is equal to $r(a,b)$ this will be true for every element $(a,b)\in\mathbb{Z}\times(\mathbb{Z}\backslash\{0\})$
  • symmetric: if $r(a,b)$ is equal to $r(b,c)$ symmetricaly $r(b,c)$ will be equal to $r(a,b)$ and this will be true for every $(a,b)$ and $(b,c)$ in $\mathbb{Z}\times(\mathbb{Z}\backslash\{0\})$
  • transitive: cause if $r(a,b)=r(c,t)$ and if $r(c,t)=r(p,q)$ then $r(a,b)=r(p,q)$ for every $(a,b),(c,t),(p,q)\in\mathbb{Z}\times(\mathbb{Z}\backslash\{0\})$

So this is an equivalence relation. About equivalence class of (6,3) it should be 0 cause, 6/3 get a remainder of 0. Is my resolution right???

How can I resolve 2.2????

Best Regards MC

share|cite|improve this question
Note that lhf's and Bill's answer to this question are more general versions of your question 2.1. – Martin Sleziak Jan 10 '12 at 15:00
You have two questions with almost identical titles. Could you change at least one of them to something else which would make the contents of the question clearer? – Asaf Karagila Jan 10 '12 at 15:00
1. I assume that by $\mathbb{N}$ you mean the non-negative integers. This is not quite standard. Proof of surjectivity is incomplete. Show that $n\ge 0$ is in the range by observing that $n=r(n,n+1)$. 2. The equivalence class of $(6,3)$ is the set of all ordered pairs $(xy,y)$ such that $x$ and $y$ are integers, with $y \ne 0$, or equivalently the set of all $(z,y)$ where $y\ne 0$ and $y$ divides $z$. 3. No space for answer. Order axioms easy to check. Not total, look at $(3,7)$ and $(3,8)$. No maximal element, for $r(a,b) <r(|a|+1,|a|+2)$. – André Nicolas Jan 10 '12 at 16:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.