Maths Olympiad Prep

Library / /25 of 48

Algebra Difficulty 5.7 AIME, harder Prove it Hong Kong

Find the total number of solutions to the following system of equations:
{a2+bca(mod37),b(a+d)b(mod37),c(a+d)c(mod37),bc+d2d(mod37),adbc1(mod37). \begin{cases} a^2 + bc \equiv a \pmod{37}, \\ b(a+d) \equiv b \pmod{37}, \\ c(a+d) \equiv c \pmod{37}, \\ bc + d^2 \equiv d \pmod{37}, \\ ad - bc \equiv 1 \pmod{37}. \end{cases}

Solution

There is only 1 solution modulo 3737.
The first four equations can be rewritten as (abcd)2=(abcd)\begin{pmatrix} a & b \\ c & d \end{pmatrix}^2 = \begin{pmatrix} a & b \\ c & d \end{pmatrix}, where the entries are taken modulo 3737. The last equation means abcd=1\begin{vmatrix} a & b \\ c & d \end{vmatrix} = 1. Therefore, we need to count the number of 2×22 \times 2 matrices AA with entries in F37\mathbb{F}_{37} such that A2=AA^2 = A and detA=1\det A = 1.
Since detA=10\det A = 1 \ne 0, AA is invertible. Thus, we multiply both sides of A2=AA^2 = A by A1A^{-1} to obtain A=IA = I. Clearly, the identity matrix II satisfies the conditions. So A=IA = I is the only solution. Equivalently, this means ad1(mod37)a \equiv d \equiv 1 \pmod{37} and bc0(mod37)b \equiv c \equiv 0 \pmod{37}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.