2
$\begingroup$

$f:\mathbb Z\times \mathbb Z\rightarrow\mathbb Z$, $f((m,n))=3n-4m$

Hi everyone, I am having some trouble trying to prove that this is subjective.

I know that it is not injective: For example, consider $f(0,-4)=f(3,0)=-12$. We can see that $f(0,-4)=f(3,0)$ but $(0,-4)\neq (4,0)$. Thus, $f$ is not injective.

For subjective, I know I need to show that for some $b\in\mathbb{Z}$, $f(x,y)=b$ for some pair of integers $(x,y)$. I'm not sure where to go from here. Any help would be appreciated. Thank you.

$\endgroup$
2

3 Answers 3

6
$\begingroup$

It is enough to see that $ f(2,3)=1$ and therefore every integer $b$ can be obtained using $f(2b,3b)$.

$\endgroup$
0
1
$\begingroup$

Set $n:=m+1$;

$f(n,m)=3(m+1)-4m=3 -m$;

Surjective.

$\endgroup$
0
$\begingroup$

The linear Diophantine equation $ax+by=c$ has a solution if and only if $\gcd(a,b)=d$ divides $c$. Hence we may write $a=de$, $b=df$, where $\gcd(e,f)=1$. If $x_0$, $y_0$ and $x_1$, $y_1$ are two integer solutions then $$ax_0+by_0=ax_1+by_1=c$$ or equivalently $$ex_0+fy_0=ex_1+fy_1=\frac{c}{d}$$ Hence $d\mid c$ since the LHS are integers and $$e(x_0-x_1)=f(y_1-y_0)$$ Now $e\nmid f$ since they are coprime, so $e\mid (y_1-y_0)$, and by the same reason $f\mid (x_0-x_1)$. So $x_0-x_1=fg$, and $y_1-y_0=eg$, for some integer $g$. \begin{align} x_0&=x_1+fg=x_1+\frac{b}{d}\cdot g\\ y_0&=y_1-eg=y_1-\frac{a}{d}\cdot g \end{align} Hence \begin{align} ax_0+by_0&=a\left(x_1+\frac{b}{d}\cdot g\right)+ b\left(y_1-\frac{a}{d}\cdot g\right)\\ &=ax_1+by_1+a\left(\frac{b}{d}\cdot g\right)- b\left(\frac{a}{d}\cdot g\right)=c \end{align} where the last two terms cancel, and so we may choose any integer for $g$ to form an infinite number of solutions.

Since in $3n-4m=k$, $\gcd(3,4)=1$, $1$ divides every integer, and so $k$ takes every value in $\mathbb{Z}$ proving $f$ is surjective.

$\endgroup$

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.