Back to problem set

Disclaimer: these are my personal solutions; they have not been reviewed, so be careful relying on them as there might be errors. Some competitions may have official solutions from the contest publishers which you may wish to refer to instead if you’re looking for verified solutions.

Problem 5

Two elements AA, BB in a group GG have the property ABA−1B=1ABA^{-1}B = 1, where 11 denotes the identity element in GG.

  1. Show that AB2=B−2AA B^2 = B^{-2} A.
  2. Show that ABn=B−nAA B^n = B^{-n} A for any integer nn.
  3. Find uu and vv so that (BaAb)(BcAd)=BuAv(B^a A^b)(B^c A^d) = B^u A^v.

Hints

Hint #1 for (a)

This may require a multi-step process; first, try solving for AA and see where you get to.

Hint #2 for (a)

First, try to prove the initial case AB=B−1AAB = B^{-1}A. Then, combine it with the result from hint #1 above and see where that leads.

Hint for (b)

Can you use the result from part (a) to help you extend it to arbitrary nn?

Hint for (c)

Use the result from part (b) as well as the hint #1 from part (a) and see if you can apply both of them. You may need to apply a property of groups to rearrange the equation to help you make these transformations.

Solution for (a)

Open to see the solution; try solving it first or see the hints above!

The goal is to show that AB2=B−2AAB^2 = B^{-2}A. Let’s start with the given equation, find a way to simplify it to compute AA, and then see what we can do with that.

ABA−1B=1givenABA−1BB−1=B−1right-multiply by B−1ABA−1=B−1simplifyABA−1A=B−1Aright-multiply by AAB=B−1Asimplify (1)ABB−1=B−1AB−1right-multiply by B−1A=B−1AB−1simplify (2) \begin{align*} A B A^{-1} B & = 1 & \quad \text{given} \\ A B A^{-1} B B^{-1} & = B^{-1} & \quad \text{right-multiply by $B^{-1}$} \\ A B A^{-1} & = B^{-1} & \quad \text{simplify} \\ A B A^{-1} A & = B^{-1} A & \quad \text{right-multiply by $A$} \\ A B & = B^{-1} A & \quad \text{simplify (1)} \\ A B B^{-1} & = B^{-1} A B^{-1} & \quad \text{right-multiply by $B^{-1}$} \\ A & = B^{-1} A B^{-1} & \quad \text{simplify (2)} \\ \end{align*}

Now, let’s substitute the value for AA from eq. (2)(2) into the right side of eq. (1)(1):

AB=B−1Aeq. (1) aboveAB=B−1B−1AB−1substitute A in rhs from eq. (2)AB=B−2AB−1simplifyABB=B−2AB−1Bright-multiply by BAB2=B−2Asimplify■ \begin{align*} AB & = B^{-1} A & \quad \text{eq. $(1)$ above} \\ AB & = B^{-1} B^{-1} A B^{-1} & \quad\text{substitute $A$ in rhs from eq. $(2)$} \\ AB & = B^{-2} A B^{-1} & \quad\text{simplify} \\ ABB & = B^{-2} A B^{-1} B & \quad\text{right-multiply by $B$} \\ AB^2 & = B^{-2} A & \quad\text{simplify} \quad \blacksquare \\ \end{align*}

Solution for (b)

Open to see the solution; try solving it first or see the hints above!

In part (a), we showed that AB2=B−2AAB^2 = B^{-2}A, and we showed it by first finding that AB=B−1AAB = B^{-1}A and then extending it by substituting AA on the right-hand side. We can easily extend this to AB3AB^3, etc. manually, but what we need to do here is to prove the general case for any nn.

Thus, we will prove it by induction:

  • first, we will prove this for a base case, e.g., n=1n = 1;
  • then we will assume that this holds for some arbitrary nn, and given that, we will prove it for n+1n+1.

Let’s start with n=1n=1, which takes the form AB=B−1AAB = B^{-1}A. This was already proven in part (a), so we’re done.

ABn=B−nAassumption to prove inductive caseABn=B−nB−1AB−1substitute for A from eq. (2) in part (a)ABnB=B−nB−1AB−1Bright-multiply by BABn+1=B−(n+1)Asimplify■ \begin{align*} A B^n & = B^{-n} A & \quad \text{assumption to prove inductive case} \\ A B^n & = B^{-n} B^{-1} A B^{-1} & \quad \text{substitute for $A$ from eq. $(2)$ in part (a)} \\ A B^n B & = B^{-n} B^{-1} A B^{-1} B & \quad \text{right-multiply by $B$} \\ A B^{n+1} & = B^{-(n+1)} A & \quad \text{simplify} \quad \blacksquare \\ \end{align*}

Solution for (c)

Open to see the solution; try solving it first or see the hints above! (BaAb)(BcAd)=BuAvgivenBa(AbBc)Ad=BuAvreassociateBa(Ab−1ABc)Ad=BuAvfactor out ABa(Ab−1B−cA)Ad=BuAvusing result from part (b)Ba(Ab−2AB−cA)Ad=BuAvfactor out another ABa(Ab−2BcA2)Ad=BuAvusing result from part (b) \begin{align*} (B^a A^b)(B^c A^d) & = B^u A^v & \quad \text{given} \\ B^a (A^b B^c) A^d & = B^u A^v & \quad \text{reassociate} \\ B^a (A^{b-1} A B^c) A^d & = B^u A^v & \quad \text{factor out $A$} \\ B^a (A^{b-1} B^{-c} A) A^d & = B^u A^v & \quad \text{using result from part (b)} \\ B^a (A^{b-2} A B^{-c} A) A^d & = B^u A^v & \quad \text{factor out another $A$} \\ B^a (A^{b-2} B^{c} A^2) A^d & = B^u A^v & \quad \text{using result from part (b)} \\ \end{align*}

At this point, we see a curious pattern: we can keep factoring out an AA term from AbA^b and transfer it to the right side of the B±cB^{\pm c} term, but each time we do, the sign of the exponent of BB changes! Thus, if bb is even, it remains as BcB^c, but if bb is odd, it becomes B−cB^{-c}.

Hence, let’s define

c′={cif bmod  2≡0−cif bmod  2≡1 \begin{align*} c' = \begin{cases} c & \text{if $b \mod 2 \equiv 0$} \\ -c & \text{if $b \mod 2 \equiv 1$} \end{cases} \end{align*}

The exponent of AA will move over as-is, so the end result will be:

BaBc’AbAd=BuAv B^a B^{c’} A^b A^d = B^u A^v

which can be simplified to:

Ba+c’Ab+d=BuAv B^{a + c’} A^{b + d} = B^u A^v

so we have

u=a+c’,v=b+dwith c’=±c as defined above.■ \boxed{u = a + c’, \quad v = b + d} \quad \text{with $c’ = \pm c$ as defined above.} \quad \blacksquare