HS22

Task 1

d) Injectivity, Surjectivity

There is always a simpler way. Contradiction was already good, but the easiest way to do it is: Suppose that $f(x)=f(y)$ for $x,y\in X$. Then $f(x)=f(y)⟹g(f(x))=g(f(y))$ (g well defined) and $g(f(x))=g(f(y))⟹f(g(f(x)))=f(g(f(y)))$ (f well defined) thus by injectivity of $f\circ g\circ f$ we have $x=y$. Thus $f$ is injective.

Task 2

a)

1.) Remeber to give the answer for $R_a$ questions as positive numbers!

b)

RSA: Since $\gcd (e,\phi (n))>1$ it is $\ne 1$ which means that the equation $e\cdot d{\equiv }_{\phi (n)}1$ does not necessarily have a solution by Bézout.

c)

Definition of $\gcd$ is that for any $x,y\in \mathbb{N}\setminus \{0\}$ there exist $u,v\in \mathbb{Z}$ such that $ux+vy=\gcd (x,y)$.

We then multiply out the two numbers and find that we can write $\gcd (a,b)\cdot \gcd (a,c)=a\cdot k+bc\cdot k^{\prime }$ for $k,k^{\prime }\in \mathbb{Z}$. As $\gcd (a,bc)$ by definition divides both $a$ and $bc$ it divides $ak+bc{k}^{\prime }$. Thus it divides the entire thing. Done!