Useful lemma about monoids and an application

It's a bit annoying to see the same thumbnail over and over on the front page of the blog, so I decided to change it a little bit. My apologies for the small text. I think I used the website hatchful for this one, while the other logo was made with logojoy.

Yesterday, while going through Olympiads, I found two problems that were eerily similar: one from the District Olympiad 2017 and one from the National Olympiad 2011. I shall solve the problem from 2011, while using the problem from 2017 as a lemma.

Let \((A,+,*)\) be a finite ring with the property that \(x^{n+1}+x=0\) has only two roots, 0 and 1. Prove that A is a field.

Solution:

First of all, let us note that, for \(x=1\), \(1+1=0\), so A has characteristic 2. Thus, the order of any element of \(x\) in the additive group \((A,+)\) is either 2 or 1, which implies that the cardinal of A, let's call it n, is a power of 2. Now, let us prove the following lemma:

Lemma:  Let (M,*) be a finite monoid and \(p\) be a natural number bigger than 2, such that \(a^p\) is different from \(a\), for every element \(a\) in M different than the identity element, \(e\). Prove that (M,*) is a group.

Proof: Let us consider such an \(a\). Since M is finite, there will be an \(i\) and a \(k\) , both natural numbers, such that \(a^i=a^{i+k}\). By continuously multiplying with \(k\), we get that \(a^i=a^{i+mk}\), for every \(m\). Thus, for every \(m\), by multiplying with \(a^{mk-i}\), we get that \(a^{mk}=a^{2mk}=a^{pmk}\), so \(a^{pmk}=a^{mk}\), and, thus, \(a^{mk}=e\), so \(a\) is invertible and (M,*) is a group.

Now it's time to apply the lemma to our problem. For any element \(x\) other than 1 and 0, \(x^{n+1}\) is different from \(-x=x\), because the characteristic is 2. By using the proof of the lemma on the monoid (A,*), we get two possibilities: either \(x^i=0\) or \(x^i=1\). All we have to prove now is that 0 is the only nilpotent element of the ring, because all the non-nilpotent elements are invertible.

If \(x\) is a nilpotent element, then let \(i\) be the rank of nilpotence. Thus, \(x^i=0\), while \(x^{i-1}\) is different than 0. By doing calculations, \((x^{i-1}+1)^{n+1}=x^{i-1}+1\) (keep in mind, n is a power of 2, and that is why the expansion is this. If n weren't a power of 2, the result wouldn't hold). Thus, \(x^{i-1}=1\) or \(x^{i-1}=0\), both contradicting the choice of \(x\), which leads to the fact that 0 is the only nilpotent element, which concludes the problem.

The monoid lemma is very useful in abstract algebra. I wonder who proposed the problems, since their similarity is very interesting. You can see, however, that the one from the NMO required a bit more thought, in order to prove that there's only one nilpotent element. Tune in next time, when I will finally post an inequality solved with Lagrange Multipliers. I already have it on paper, but partial derivatives are a bit harder to write than ring theory.

Cris.