$Set problem. Need it well written...$

Question

$Set problem. Need it well written...$

We have $k,m \in \N^*$. Define two sets U and V by:

U = {$a \in \Z | 1 \leq a \leq m, gcd(a,m) = 1$}
V = {$a \in \Z | 1 \leq a \leq km, gcd(a,km) = k$}

a. We have $a \in U$. Show that $ka \in V$
b. Thanks to (a.) we can define a function $f: U \to V$ by $a \to ka$. Show that f is a bijection.
You can use, without proof, the solution: for $k,x,y \in \Z, gcd(kx,ky) = |k|gcd(x,y)$

Set Theory

Stan Chan

17

Report

Answer

The answer is accepted.

Join Matchmaticians Affiliate Marketing Program to earn up to a 50% commission on every question that your affiliated users ask or answer.

Answer 1

Answers can only be viewed under the following conditions:

The questioner was satisfied with and accepted the answer, or
The answer was evaluated as being 100% correct by the judge.

View the answer

I mean, the problem is mostly solved already, but I'll try to be formal.

a. Let $a \in U$, so $gcd(a, m) = 1$. We have that $ka \in V \iff \gcd(ka,km)=k$. But, since $k > 0$, \[ \gcd(ka, km) = k \cdot \gcd(a, m) = k \cdot \gcd(a, m) = k \cdot 1 = k \] and so $ka \in V$, as desired.

b. The map $a \mapsto ka$ defines a function $f \colon U \rightarrow V$. We want to show it is bijective. It is obviously injective: if $a, b \in U$ and $a \neq b$, then $ka \neq kb$. To show it is surjective, we need to check that every $c \in V$ is of the form $ka$ for some $a \in U$.

Let $c \in V$. For every $z \in \mathbb{Z}$, by definition of the greatest common divisor, $\gcd(c, z) \mid c$. In particular, $\gcd(c,km) = k \mid c$, so we can write $c = ka$ for some $a \in \mathbb{Z}$. We want to show that $a \in U$. We have that \[ k \cdot \gcd(a, m) = \gcd(ka, km) = \gcd(c, km) = k \] so dividing by $k$ we get $\gcd(a, m) = 1$, that is, $a \in U$, and so we can write $c = f(a)$. Hence $f$ is surjective, and so it is a bijection, cvd.

Alessandro Iraci

1.7K

Stan Chan

0

perfect. I was struggling to word a solution like you did. Thanks a lot.

$Set problem. Need it well written...$

Answer

Related Questions

Search