2

Show that $f:\{1,2,...,n\}\times\{1,2,...,m\} \rightarrow \{1,2,...,nm\}$

given by $f(p,q)=(p-1)m+q$

is biyective.

My try:

Inyectivite:

Let $$f(p,q) = f(p´,q´)$$ $$(p-1)m + q = (p'-1)m+q'$$ $$mp+q=mp'+q'$$

Now let $p=0$, then $\quad q=q'$

Now let $q=0$, then $$mp=mp'$$ $$p=p'$$

So $f$ must be inyective.

Surjectivity:

So we need to find $s\in \{1,2,...,nm\}$ then exists $p,q$ such that $f(p,q)=s$

Let $p=1\quad$ and $\quad q =s\quad$ then $f(p,q)=(1-1)m+s=s$

Then $f$ must be surjetive.

Sofía Contreras
  • 1,476
  • Both parts are wrong. Why can you substitute $p=0$ (and implicitly also $p'=0$)? Also, $s\notin{1, 2,\dots, m}$ if $s>m$. – Berci Feb 12 '20 at 19:39
  • Thanks for the corrections. How would you argue intectivity then? Also I belive that $s\in {1,2,...,nm}$ but how do I argue that $s < mn$? – Sofía Contreras Feb 12 '20 at 20:10
  • Do you know the division theorem (about being able to divide integers by positive integers with remainder)? – darij grinberg Feb 12 '20 at 20:12
  • 1
    Now I see it! Then we could say that the representation of a division of two integers is unique(by the division theorem) then $p=p'$ and $q=q'$? – Sofía Contreras Feb 12 '20 at 20:27
  • @SofíaContreras Yes, that's much better. The easiest is to define the inverse function $s\mapsto (p,q)$ if $n$ divides $s-1$ by $p$ whole times, giving remainder $r-1$. – Berci Feb 12 '20 at 20:42

0 Answers0