2

Let $a, b \in ℤ$. Consider the following function: $f : ℤ \times ℤ \to ℤ$ such that for any $(x,y)∈ ℤ \times ℤ, f(x,y) = ax + by.$

Fill in the blank in the following proposition with a simple condition on a and b, and then prove the proposition.

Proposition 1. The function f is onto if and only if _____.

Would I get full marks for this answer?

Iff $a$ and $b$ are relatively prime (or coprime, or gcd$(a,b) =1$).

Then there exist $x$ and $y$ in $\Bbb Z$ so that $ax + by = 1$. From this we can generate all of Z to get an onto function.

I'm just wondering because my teacher said it was challenging but it seems straightforward.

learner
  • 6,726
user127340
  • 21

2 Answers2

1

Almost. You've shown that if $a$ and $b$ are relatively prime, then the map is onto. What if the map is onto? Are $a$ and $b$ relatively prime? You might want to include a word about why, if this is indeed the case.

Nick
  • 1,670
  • Is there more than one answer to this question? Like I'm able to put more than one thing for the blank? – user127340 Mar 03 '14 at 05:57
  • Well, your proposed answer is that $f$ is onto if and only if $a$ and $b$ are relatively prime. To show that your answer is correct, you need to show the "if" and the "only if". You've shown the "if", so what's left is to show the "only if". – Nick Mar 03 '14 at 06:00
  • How would I go about trying to show the "only if" part? What does the hint above mean? – user127340 Mar 03 '14 at 06:03
  • To show the "only if" part, you need to show that if $f$ is onto, then $a$ and $b$ are relatively prime. What can you say about the existence of solutions to the equation $ax+by=1$ if $f$ is onto? – Nick Mar 03 '14 at 06:05
  • No, $x$ and $y$ are both integers, not sets. We say $f$ is onto if, for any $z \in \mathbb{Z}$, there exists $(x,y)\in\mathbb{Z}\times\mathbb{Z}$ such that $f(x,y)=z$. Does that help? – Nick Mar 03 '14 at 06:17
  • Yeah sort of. I think I would need more practice to familiarize myself with it. – user127340 Mar 03 '14 at 06:25
1

Hint $$f(x,y)=ax+by=\gcd(a,b)(\frac{a}{\gcd(a,b)}x+\frac{b}{\gcd(a,b)}y)$$

If $\gcd(a,b)\ne 1$, then there must be $\gcd(a,b)|f(x,y)$. So $f$ is not onto.

The case $\gcd(a,b)=1$ is your proof.

Community
  • 1
gaoxinge
  • 4,434