# If $f,g$ are $2$ onto homomorphisms, $\exists$ $y \neq e \in M$ such that $f(y)=g(y)$.

The below problem appeared in Schweitzer contest.

Let $M$ and $N$ be two groups of finite order and let $f,g : M \to N$ be $2$ onto but not injective group homomorphisms. Then prove that there exists $y \neq e \in M$ such that $f(y)=g(y)$.

A elaborate solution will be appreciated.

• The remark in the parenthetical seems too important to be in a parenthetical, imo. It made me very confused when I first read the problem -- I thought it was saying "not necessarily 1-1", which makes no sense. – Potato Oct 2 '14 at 14:51
• Do we need to assume that they not 1-1? – Yiorgos S. Smyrlis Oct 2 '14 at 14:53
• It is easy to see that without this assumption the claim is false. – Amitai Yuval Oct 2 '14 at 14:55
• Define an automorphism of $c_3$ by $1\mapsto 2$ – Amitai Yuval Oct 2 '14 at 14:55
• It is not necessarily true that $\operatorname{Ker}\:(f) \cap \operatorname{Ker}\:(g) \neq \{e\}$: let $G$ be a finite group and consider the two projections $G\times G\to G$. – Dejan Govc Oct 2 '14 at 15:10

Define a homomorphism $h:M\to N\times N$ by $h(x)=(f(x),g(x))$. If $h(x)=(e,e)$ for some $x\neq e$, we are done. Otherwise, $h$ is injective, i.e. an embedding. We may therefore identify $M$ with a subgroup of $N\times N$ via this embedding. Since $f$ and $g$ are surjective and not injective, this reduces the problem to:
Problem. Suppose $M\leq N\times N$ is a subgroup such that $|M|>|N|$ and $\pi_1(M)=\pi_2(M)=N$, where $\pi_1,\pi_2:N\times N\to N$ are the projections on the first and second factor, respectively. Then, $M$ contains an element of the form $(x,x)$ for some $x\neq e$.
To solve this, observe that $\Delta=\{(x,x)\mid x\in N\}$ is a subgroup of $N\times N$ and $|\Delta|=|N|$. We claim that $\Delta\cap M\neq\{e\}.$ Suppose not. Then $\Delta\cap M$ is trivial, implying that the product $\Delta M$ is a subset of $N\times N$ of cardinality $|N||M|>|N\times N|$, by the product formula. This is a contradiction.
• Perhaps I am missing the obvious, but how do you conclude that $|\Delta M|$ = $|\Delta||M|$? (That is, that different pairs from $\Delta \times M$ do not give the same product?) – Mees de Vries Oct 2 '14 at 19:04
• @MeesdeVries: this is true by the product formula, which I have linked to. This formula is proved for example in Rotman's book An Introduction to the Theory of Groups (4th edition, Theorem 2.20). The idea is to define a surjection $\phi:\Delta\times M\to\Delta M$ by $(x,y)\mapsto xy$. Then we may prove that $|\phi^{-1}(z)|=|\Delta\cap M|$, which in our case is equal to $1$, i.e. $\phi$ is a bijection. – Dejan Govc Oct 2 '14 at 19:11